0
これは私の2回目のスタックオーバーフローですので、もし私の質問が適切に書式化されていない場合は、私は詳細を見落としていると私に教えてください、私はこのサイトを絶えず使用していません。ハッシュテーブル内のキーが時々自分自身と衝突することはありますか？
私の質問は：私は私のコードを実行すると、出力としてバックプリントになっています：
満たされているハッシュテーブルの割合、
累計衝突、
衝突の総数、および
のWiを衝突されているキーの名前キーをハッシュテーブルに挿入するときに使用します。
すべてのは、それが挿入されるキーの同じ名前を出力し、それがになっていた場合、私はわからない、時には、と衝突しているキーの名前をプリントアウトする場合を除き、罰金出てきますハッシュテーブルで起こるかどうか？問題が発生した場合の
/** 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