哈希表：在碰撞

Hashtable ht = new Hashtable(); 
    for (int i = 0; i < 100; i++) { 
     ht.put(i%10, i); 
    } 

    Enumeration< Integer> eles = ht.elements(); 
    while(eles.hasMoreElements()) 
     System.out.println(eles.nextElement());

上面的代碼片段的情況下，打印99，98，90 .......哈希表：在碰撞

但我想打印所有的100個元素。如何獲得數字清單，如... 99,89,79,69，... 19,9 98,88,78,68 .... 18,8 97,87,77,67 .... 17,7 .. .. 91,81,71,61 .... 11,1

基本上所有的碰撞列表。

來源

2014-09-19 Vrijendra Kumar Singh

您可以將列表存儲爲值。 – talex 2014-09-19 13:50:40

請注意，現在'HashMap'通常比'Hashtable'更受歡迎。 – Wyzard 2014-09-19 13:56:29

您目前正在使用i % 10作爲哈希映射鍵，它只有十個值（0-9）。因此，只有最後十個值存儲在您的地圖中，所有其他值都被覆蓋。

如果您需要在每個存儲桶中存儲多個項目，請使用列表類型作爲您的值。例如：

Hashtable<Integer, List<Integer>> ht = new Hashtable<>(); 
for (int i = 0; i < 100; i++) { 
    int key = i % 10; 
    List<Integer> list = ht.get(key); 
    if (list == null) { 
    list = new ArrayList<>(); 
    ht.put(key, list); 
    } 
    list.add(i);  
} 

Enumeration<List<Integer>> eles = ht.elements(); 
while (eles.hasMoreElements()) { 
    System.out.println(Arrays.toString(eles.nextElement().toArray())); 
}

輸出：

 
[9, 19, 29, 39, 49, 59, 69, 79, 89, 99] 
[8, 18, 28, 38, 48, 58, 68, 78, 88, 98] 
[7, 17, 27, 37, 47, 57, 67, 77, 87, 97] 
[6, 16, 26, 36, 46, 56, 66, 76, 86, 96] 
[5, 15, 25, 35, 45, 55, 65, 75, 85, 95] 
[4, 14, 24, 34, 44, 54, 64, 74, 84, 94] 
[3, 13, 23, 33, 43, 53, 63, 73, 83, 93] 
[2, 12, 22, 32, 42, 52, 62, 72, 82, 92] 
[1, 11, 21, 31, 41, 51, 61, 71, 81, 91] 
[0, 10, 20, 30, 40, 50, 60, 70, 80, 90]

來源

2014-09-19 13:51:18

但是在碰撞的情況下，如果我沒有錯，它應該存儲在桶中。一切都應該自動工作。任何人都可以用例子來解釋我可以如何存儲這些值並將每個桶作爲列表。請（新來的Java） – 2014-09-19 14:07:06

非常感謝鄧肯。 – 2014-09-19 14:16:46

@VrijendraKumarSingh只需檢查次要更新。我不小心把'ht.put'放在'if'語句之外，這是不必要的。 – 2014-09-19 14:23:57

你在你的例子觀察什麼是沒有碰撞效果。這是正常的元素替換。迭代100次後，Hashtable中只有10個元素。

您使用數字i％10（0,1，...，9）作爲鍵。所以，你只有10個不同的鍵。例如：在for循環中，您爲key = 5（i = 5，i = 15，i = 95）放置10個值，並且每個放置（5，val）替換與key = 5相關聯的舊值。

碰撞列表是不同的概念。

對於每個關鍵散列表計算一些散列值並使用此散列來選擇其內部存儲桶表中的索引。接下來在該索引下放置{key，value}。衝突是兩個不同的鍵已經計算出相同的桶索引的情況。

例如：

table index | map.entry 
0    | {0, "A"} 
1    | {3, "B"} 
2    | {2, "A"} -> {4, "C"} 
3    | {1, "D"} -> {5, "A} -> {6, "F}

在這個例子中你有4元件內部表哈希表。此哈希表包括7個元件（7個不同的密鑰），但是：

鍵2和3被放置到同一桶中（它們具有在哈希值計算的相同的索引）鍵1，5，6被放置到相同的桶。

所以我們可以說，key = 2和key = 3之間以及1,5,6之間存在碰撞。換言之，密鑰2和3位於同一個衝突列表中。鍵1,5,6相同。

您不能得到哈希表等collistion列表，因爲它是Hashtable的內部實現標記爲私人：

/** 
* Hashtable bucket collision list entry 
*/ 
private static class Entry<K,V> implements Map.Entry<K,V> { 

int hash; 
final K key; 
V value; 
Entry<K,V> next; 

protected Entry(int hash, K key, V value, Entry<K,V> next) { 
    this.hash = hash; 
    this.key = key; 
    this.value = value; 
    this.next = next; 
} 

... 

public V setValue(V value) { 
    if (value == null) 
     throw new NullPointerException(); 

    V oldValue = this.value; 
    this.value = value; 
    return oldValue; 
} 

... 

public int hashCode() { 
    return hash^value.hashCode(); 
} 

...

}

和Hashtable有其內部桶表定義爲：

/** 
* The hash table data. 
*/ 
private transient Entry<K,V>[] table;

希望這有助於弄清散列表行爲。

來源

2014-09-19 14:56:00

哈希表：在碰撞

回答

相關問題