0
스택 오버플로에 대한 두 번째 시간이므로 세부 정보가 누락 되었다면 알려주세요. 내 질문에 형식이 올바르지 않으면 죄송합니다.이 사이트를 계속 사용하지는 않습니다.해시 테이블의 키가 때로는 자신과 충돌하는 것이 정상입니까?
내 질문이있다 : 내 코드를 실행하면이 출력으로 다시 인쇄 해야하는 :
가득 해시 테이블의 비율
총 누적 충돌,
충돌의 총 개수 및
위스콘신 충돌되는 키의 이름 열쇠를 해시 테이블에 삽입 할 때.
모든의는 삽입되는 키의 같은 이름을 출력하고, 그가에 해야하는 경우 내가 확실하지 않다 때때로 충돌되는 키의 이름을 인쇄 할 때를 제외하고 잘 나온다 해시 테이블에서 발생했는지 여부 문제가 발생하는 위치의
/** Container class for a key-value pair */
class KVpair<Key, E> {
private Key k;
private E e;
/** Constructors */
KVpair()
{ k = null; e = null; }
KVpair(Key kval, E eval)
{ k = kval; e = eval; }
/** Data member access functions */
public Key key() { return k; }
public E value() { return e; }
}
public class HashTable<Key extends Comparable<? super Key>, E> {
private int M;
private KVpair<Key, E>[] HT;
private int collisionSum = 0;
private int h(Key key) {
HashFunction hf = new HashFunction();
return hf.sfold((String) key, M);
}
private int p(Key key, int slot) {
return slot;
}
@SuppressWarnings("unchecked") // Generic array allocation
HashTable(int m) {
M = m;
HT = (KVpair<Key, E>[]) new KVpair[M];
}
/** Insert record r with key k into HT */
void hashInsert(Key k, E r) {
int home; // Home position for r
int pos = home = h(k); // Initial position
int AccumulatedSum = 0;
for (int i = 1; HT[pos] != null; i++) {
collisionSum++;
AccumulatedSum++;
if (HT[pos].key().compareTo(k) != 0)
System.out.println("Collided with key " + HT[pos].key());
pos = (home + p(k, i)) % M; // Next probe slot
assert HT[pos].key().compareTo(k) != 0 : "Duplicates not allowed";
}
HT[pos] = new KVpair<Key, E>(k, r); // Insert R
System.out.printf("Accumulated collisions: %d\n", AccumulatedSum);
System.out.printf("Total number of Collisions %d\n", collisionSum);
}
/** Search in hash table HT for the record with key k */
E hashSearch(Key k) {
int home; // Home position for k
int pos = home = h(k); // Initial position
for (int i = 1; (HT[pos] != null) && (HT[pos].key().compareTo(k) != 0); i++) {
pos = (home + p(k, i)) % M; // Next probe position
if (i == M) {
return null;
}
System.out.println(pos);
}
return HT[pos].value(); // Found it
}
}
import java.io.*;
import java.math.*;
// This is the hashFunction that will be used in the hashtable
// for linear probing of indexes when collisions happen.
//where s is the String key being passed and M is the size of the hashTable
public class HashFunction
{
int sfold(String s, int M) {
int intLength = s.length()/4;
int sum = 0;
for (int j = 0; j < intLength; j++) {
char c[] = s.substring(j*4,(j*4)+4).toCharArray();
int mult = 1;
for (int k = 0; k < c.length; k++) {
sum += c[k] * mult;
mult *= 256;
}
}
char c[] = s.substring(intLength * 4).toCharArray();
int mult = 1;
for (int k = 0; k < c.length; k++) {
sum += c[k] * mult;
mult *= 256;
}
return(Math.abs(sum) % M);
}
int h(String x, int M) {
char ch[];
ch = x.toCharArray();
int xlength = x.length();
int i, sum;
for (sum=0, i=0; i < xlength; i++)
sum += ch[i];
return sum % M;
}
int h(int x) {
return(x % 16);
}
}
import java.util.Arrays;
import java.util.Random;
public class randHashTableDriver {
public static void main(String[] args) {
int htLength = 128; // HashTable Size
HashTable<String, String> hashT = new HashTable<>(htLength);
HashTable<String, String> hashT2= new HashTable<>(htLength);
fillHashTable(hashT, htLength, 0.4);
fillHashTable(hashT2, htLength, 0.6);
}
// Generates a String array filled with words of 8 letters in length with no
// duplicates
static String[] randomWordGen(int wordCount) {
int wordLength = 8;
String[] words = new String[wordCount];
Arrays.fill(words, "");
Random r = new Random();
for (int i = 0; i < wordCount; i++) {
String s = "";
for (int t = 0; t < wordLength; t++) {
char c = (char) (r.nextInt(26) + 65);
s += c;
}
if (Arrays.asList(words).contains(s)) {
i--;
continue;
}
words[i] += s;
}
return words;
}
// Creates the HashTable and Fills it with indexes until it reaches the
// Percent specified
static void fillHashTable(HashTable<String, String> h, int size, double fillPercentage) {
int indexes = (int) Math.ceil(size * fillPercentage);
String[] words = randomWordGen(indexes);
System.out.println("\n\n------Filling HashTable------");
for (int i = 0; i < indexes; i++) {
h.hashInsert(words[i], words[i]);
System.out.printf("\nInserting Word: %s , FillPercentage: %.2f\n", words[i], ((i+1d) /size) * 100);
}
}
}
예 출력 (출력이보다 실제로 더 이상) :
------Filling HashTable------
Accumulated collisions: 0
Total number of Collisions 0
Inserting Word: KPUWLEYG , FillPercentage: 0.78
Accumulated collisions: 0
Total number of Collisions 0
Inserting Word: CVJLHZTS , FillPercentage: 1.56
Accumulated collisions: 0
Total number of Collisions 0
Inserting Word: PHTMMRDF , FillPercentage: 2.34
Collided with key PHTMMRDF
Accumulated collisions: 1
Total number of Collisions 1
Inserting Word: LBHTQOZT , FillPercentage: 3.13
Accumulated collisions: 0
Total number of Collisions 1
Inserting Word: JJIRZFEU , FillPercentage: 3.91
Accumulated collisions: 0
Total number of Collisions 1
Inserting Word: ETWYECDW , FillPercentage: 4.69
Accumulated collisions: 0
Total number of Collisions 1
Inserting Word: PEKVFYWK , FillPercentage: 5.47
Collided with key PHTMMRDF
Collided with key LBHTQOZT
Accumulated collisions: 2
Total number of Collisions 3
Inserting Word: LSRKQZWI , FillPercentage: 6.25
Accumulated collisions: 0
Total number of Collisions 3
Inserting Word: QVVHNKKY , FillPercentage: 7.03
Accumulated collisions: 0
Total number of Collisions 3
Inserting Word: AWNKDWPU , FillPercentage: 7.81
Accumulated collisions: 0
Total number of Collisions 3
Inserting Word: BCLQXGGZ , FillPercentage: 8.59
Accumulated collisions: 0
Total number of Collisions 3
Inserting Word: NWCLTWVW , FillPercentage: 9.38
Accumulated collisions: 0
Total number of Collisions 3
Inserting Word: EZMHLCRT , FillPercentage: 10.16
Accumulated collisions: 0
Total number of Collisions 3
Inserting Word: AKOREOMM , FillPercentage: 10.94
Accumulated collisions: 0
Total number of Collisions 3
Inserting Word: TFFDJHDM , FillPercentage: 11.72
Accumulated collisions: 0
Total number of Collisions 3
Inserting Word: CVLWLOMC , FillPercentage: 12.50
Collided with key PEKVFYWK
Accumulated collisions: 1
Total number of Collisions 4
Inserting Word: JHTDLBBU , FillPercentage: 13.28
Accumulated collisions: 0
Total number of Collisions 4
Inserting Word: DSQRNEFA , FillPercentage: 14.06
Accumulated collisions: 0
Total number of Collisions 4
Inserting Word: FOBTANHC , FillPercentage: 14.84
Collided with key QVVHNKKY
Collided with key TFFDJHDM
Collided with key PHTMMRDF
Collided with key LBHTQOZT
Collided with key LSRKQZWI
Collided with key BCLQXGGZ
Accumulated collisions: 6
Total number of Collisions 10
Inserting Word: MLJVRHMQ , FillPercentage: 15.63
Collided with key MLJVRHMQ
Accumulated collisions: 1
Total number of Collisions 11
해시 함수가 결정적이라는 점을 감안할 때 분명히 주어진 키가 "충돌"할 것이라고 분명하지 않습니다. –
당신이 묻는 것을 이해한다면, 그렇습니다. [비둘기 원리] (https://en.wikipedia.org/wiki/Pigeonhole_principle) 때문에. –
내가 물어 보는 것은 해시 테이블에 키를 삽입 할 때 키 자체가 충돌하는 것이 일반적이다. – RedRocket