我聽說過我的學位課程，如果新的密鑰條目與另一個條目相沖突，HashTable會將新條目放入「下一個可用」存儲桶中。HashTables如何處理碰撞？
如果在使用碰撞鍵調用一個背面時發生碰撞，HashTable仍然會返回正確的值？
我假設Keys是String類型，並且hashCode()返回通過說Java產生的默認值。
如果我實現自己的散列函數，並把它作爲一個查找表的一部分（即一個HashMap或Dictionary），用於處理衝突存在什麼樣的戰略？
我甚至見過有關素數的筆記！ Google搜索中的信息不太清楚。
哈希表以兩種方式之一處理碰撞。
選項1：通過讓每個存儲桶包含散列到該存儲桶的元素的鏈接列表。這就是爲什麼一個糟糕的散列函數會使散列表中的查找非常慢。
選項2：如果哈希表項都滿了哈希表可以增加桶，它已經然後重新分配表中的所有元素的個數。散列函數返回一個整數，並且散列表必須將散列函數的結果與該表的大小進行相對應的修改，以確保它能夠進行存儲。因此，通過增加尺寸，它將重新運行並運行模運算，如果幸運的話可以將對象發送到不同的桶。
Java在其哈希表實現中同時使用了選項1和2。
它將使用equals方法來查看密鑰是否存在，特別是如果同一個存儲桶中存在多個元素。
我聽說在我的學位課程，如果新 鍵盤輸入與另一個發生碰撞 哈希表將放入一個新的進入 的「下一個可用的」桶。
這實際上是不正確的，至少爲Oracle JDK（它是一個實現細節可以在API的不同實現之間變化）。相反，每個存儲桶都包含一個鏈接的條目列表。
那麼如何將哈希表仍然 如果要求一個 回來的碰撞鍵時，就會出現此 碰撞返回正確的值？
它使用equals()來查找實際匹配的條目。
如果我實現我自己的散列函數 並把它作爲一個查表 （即一個HashMap或字典）的一部分，用於處理 碰撞存在哪些 策略？
有各種不同的優勢和缺點的碰撞處理策略。 Wikipedia's entry on hash tables給出了一個很好的概述。
我強烈建議你閱讀這篇博客，其出現在HackerNews最近： How HashMap works in Java
總之，答案是
如果兩個不同的 HashMap的主要對象有相同 會發生什麼哈希碼？
它們將被存儲在同一個存儲桶中，但是 沒有下一個鏈接列表的節點。並且 等於（）方法將用於 在 HashMap中標識正確的鍵值對。
由於有一些混淆的算法Java的HashMap的是使用（在Sun /甲骨文/ OpenJDK的實現），這裏的相關的源代碼段（從OpenJDK的，1.6.0_20，在Ubuntu）：
/**
* Returns the entry associated with the specified key in the
* HashMap. Returns null if the HashMap contains no mapping
* for the key.
*/
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
在查找表中的一個條目時，例如從get(),containsKey()和其他一些條目中調用此方法（引用來自第355行至第371行）。這裏的for循環遍歷入口對象形成的鏈表。
這裏進入對象的代碼（行691-705 + 759）：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
// (methods left away, they are straight-forward implementations of Map.Entry)
}
以後這個權利來了addEntry()方法：
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
這增加了在前面的新條目的條目，鏈接到舊的條目的第一個條目（如果沒有這樣的條目，則爲null）。類似地，removeEntryForKey()方法遍歷列表並負責僅刪除一個條目，讓列表的其餘部分保持不變。
因此，這裏是每個存儲桶的鏈接條目列表，我非常懷疑這從_20更改爲_22，因爲它從1.2開始就是這樣。 （代碼爲（c）1997-2007 Sun Microsystems，並且可以在GPL下使用，但是可以更好地使用原始文件，該文件包含在Sun/Oracle的每個JDK的src.zip中，以及OpenJDK中）。
這是java中一個非常簡單的哈希表實現。在只實現put()和get()，但你可以很容易地添加你喜歡的任何東西。它依賴於由所有對象實現的java方法hashCode()。你可以很容易地創建自己的界面，
interface Hashable {
int getHash();
}
，並迫使其通過按鍵，如果你喜歡可以實現。
public class Hashtable<K, V> {
private static class Entry<K,V> {
private final K key;
private final V val;
Entry(K key, V val) {
this.key = key;
this.val = val;
}
}
private static int BUCKET_COUNT = 13;
@SuppressWarnings("unchecked")
private List<Entry>[] buckets = new List[BUCKET_COUNT];
public Hashtable() {
for (int i = 0, l = buckets.length; i < l; i++) {
buckets[i] = new ArrayList<Entry<K,V>>();
}
}
public V get(K key) {
int b = key.hashCode() % BUCKET_COUNT;
List<Entry> entries = buckets[b];
for (Entry e: entries) {
if (e.key.equals(key)) {
return e.val;
}
}
return null;
}
public void put(K key, V val) {
int b = key.hashCode() % BUCKET_COUNT;
List<Entry> entries = buckets[b];
entries.add(new Entry<K,V>(key, val));
}
}
有他們的碰撞resolution.Some各種方法分離鏈，開放尋址，羅賓漢哈希散列杜鵑等
Java使用分離鏈解決衝突的哈希tables.Here是一個偉大的鏈接到它是如何發生的： http://javapapers.com/core-java/java-hashtable/
當你談到「如果新的鍵盤輸入撞到了另一輛車哈希表將放入一個新進入‘下一個可用的’桶」，你所談論的開放尋址策略散列表的碰撞解析的。
散列表有幾種解決衝突的策略。
第一種大方法的需要，所述鍵（或指向它們的指針）被存儲在表中，與相關聯的值，其中，還包括一起：
來處理衝突是動態調整，其還具有幾個方面另一個重要的方法：
編輯：以上是從wiki_hash_table，你應該去看看，以獲得更多信息借來的。
有多種技術可用於處理碰撞。我將解釋其中的一些
鏈接： 在鏈接中，我們使用數組索引來存儲值。如果第二個值的散列碼也指向相同的索引，那麼我們用鏈表替換該索引值，並且指向該索引的所有值都存儲在鏈表中，並且實際數組索引指向鏈表的頭部。 但是，如果只有一個哈希碼指向數組的索引，則該值將直接存儲在該索引中。檢索值時應用相同的邏輯。這用於Java HashMap/Hashtable以避免衝突。
線性探測：當我們在表中有更多的索引，然後是要存儲的值時，使用這種技術。線性探測技術的工作原理是保持增量直到找到空槽。僞代碼如下所示..
指數= H（K）
而（VAL（索引）被佔用）
指數=（索引+ 1）模N
雙散列技術：在這種技術中，我們使用兩個散列函數h1（k）和h2（k）。如果h1（k）處的時隙被佔用，則第二散列函數h2（k）用於增加索引。僞代碼如下所示..
指數= H1（k）的
而（VAL（索引）被佔用）
指數=（索引+ H 2（k））的模N
線性探測和雙重散列技術是開放尋址技術的一部分，只有當可用插槽數多於要添加的項數時才能使用。由於在這裏沒有使用額外的結構，因此需要較少的內存鏈接，但由於大量移動發生，所以直到我們找到一個空插槽時才緩慢。同樣在開放尋址技術中，當一個物品從槽中移除時，我們放置一個墓碑來指示物品從這裏被移除，這就是爲什麼它是空的。
這是真的採取了由Sun /甲骨文在JDK 1.6.0_22兩者`Hashtable`和`HashMap`。 – 2011-02-12 21:42:04
@Nikita：不確定Hashtable，我現在無法訪問源代碼，但我100％確定HashMap在我的調試器中看到過的每個版本中都使用鏈接而不是線性探測。 – 2011-02-12 21:45:34
@Michael那麼，我現在正在查看HashMap的`public V get（Object key）'的源碼（與上面的版本相同）。如果你確實在這些鏈表出現的地方找到了精確的版本，我很有興趣知道。 – 2011-02-12 21:51:52