HashTables如何处理冲突？
我听说在我的学位课程中，如果新的密钥条目与另一个条目相冲突，则HashTable会将新条目放入“下一个可用”存储桶中。
如果在使用碰撞键调用一个背面时发生碰撞， HashTable将如何返回正确的值？
我假设Keys是Stringtypes，并且hashCode()返回通过说Java产生的默认值。
如果我实现自己的散列函数并将其用作查找表（即HashMap或Dictionary ）的一部分，那么处理冲突的策略是什么？
我甚至看到有关素数的笔记！ Googlesearch中的信息不太清楚。
哈希表以两种方式之一处理碰撞。
选项1：通过让每个存储桶包含散列到该存储桶的元素的链接列表。 这就是为什么一个糟糕的哈希函数可以使哈希表中的查找非常慢。
选项2：如果散列表项全部满，那么散列表可以增加它所具有的桶的数量，然后重新分配表中的所有元素。 散列函数返回一个整数，散列表必须将散列函数的结果与该表的大小进行相对应的修改，以确保它可以进行存储。 因此，通过增加尺寸，它将重新运行并运行模运算，如果幸运的话可以将对象发送到不同的桶。
Java在其哈希表实现中同时使用了选项1和2。
当你谈到“如果新的密钥条目与另一个密钥条目相冲突，哈希表将把一个新的条目放入'下一个可用的存储桶'”，你正在谈论散列表的冲突解决scheme的开放寻址策略 。
有几个散列表的策略来解决冲突。
第一种大的方法要求键（或指向它们的指针）和关联的值一起存储在表中，其中还包括：
- 单独的链接
- 开放寻址
- 合并哈希
- 杜鹃哈希
- 罗宾汉哈希
- 2select性哈希
- 跳房子哈希
处理碰撞的另一个重要方法是dynamicresize ，它还有几个方法：
- 通过复制所有条目来resize
- 增量resize
- 单调的密钥
编辑 ：上面是从wiki_hash_table借用，你应该去看看获得更多的信息。
我强烈build议你阅读最近出现在HackerNews上的博客文章： HashMap是如何在Java中工作的
总之，答案是
如果两个不同的HashMap密钥对象具有相同的哈希码会发生什么？
它们将被存储在同一个桶中，但是没有下一个节点的链表。 而equals（）方法将用于在HashMap中识别正确的键值对。
有多种技术可以处理碰撞。 我会解释其中的一些
链接：在链接中，我们使用数组索引来存储值。 如果第二个值的散列码也指向相同的索引，那么我们用一个链表replace该索引值，并且指向该索引的所有值都存储在链表中，并且实际的数组索引指向链表的头部。 但是，如果只有一个哈希码指向数组的索引，那么该值将直接存储在该索引中。 检索值时应用相同的逻辑。 这用于Java HashMap / Hashtable以避免冲突。
线性探测：当我们有更多的索引在表中，然后将存储的值使用这种技术。 线性探测技术的工作原理是保持增量，直到find空槽。 伪代码看起来像这样..
index = h（k）
而（val（索引）被占用）
index =（index + 1）mod n
双重哈希技术：在这个技术中，我们使用两个哈希函数h1（k）和h2（k）。 如果h1（k）处的时隙被占用，则第二散列函数h2（k）用于增加索引。 伪代码看起来像这样..
index = h1（k）
而（val（索引）被占用）
index =（index + h2（k））mod n
线性探测和双重哈希技术是开放寻址技术的一部分，只有在可用时隙超过要添加的项目数时才能使用。 因为这里没有使用额外的结构，所以它占用的内存less了，但是由于大量的移动发生，所以我们find了一个空的槽。 另外在开放寻址技术中，当一个物品从一个槽中移出时，我们把一个墓碑表明这个物品从这里被移除，这就是为什么它是空的。
我听说在我的学位课程中，如果新的密钥条目与另一个条目相冲突，则HashTable会将新条目放入“下一个可用”存储桶中。
实际上这不是真的，至less对于Oracle JDK来说（这是一个实现细节，可能会因API的不同实现而有所不同）。 相反，每个存储桶都包含一个链接的条目列表。
那么如果在使用碰撞键调用一个后面时发生这个碰撞，那么HashTable将如何返回正确的值呢？
它使用equals()来查找实际匹配的条目。
如果我实现自己的散列函数并将其用作查找表（即HashMap或Dictionary）的一部分，那么处理冲突的策略是什么？
有各种各样的优点和缺点的碰撞处理策略。 维基百科的哈希表条目给出了一个很好的概述。
它将使用equals方法来查看密钥是否存在，尤其是在同一个桶中有多个元素的情况下。
由于对Java的HashMap使用的algorithm（在Sun / Oracle / OpenJDK实现中）存在一些困惑，下面是相关的源代码片断（来自Ubuntu上的OpenJDK，1.6.0_20）：
/** * 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; }
这个方法（引用来自第355到第371行）在查找表中的条目时被调用，例如从get() ， containsKey()和其他一些条目中查找。 这里的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()方法遍历列表，并负责删除只有一个条目，让列表的其余部分保持不变。
所以，这里是每个桶的链接条目列表，我很怀疑这个从_22变到了_22 ，因为从1.2开始就是这样。
（这个代码是（c）1997-2007 Sun Microsystems，并且可以在GPL下使用，但是为了更好地复制原始文件，包含在Sun / Oracle的每个JDK的src.zip中，以及OpenJDK中。
有多种解决冲突的方法，其中有一些是单独链接，开放寻址，罗宾汉散列，杜鹃散列等。
Java使用单独的链接来解决哈希表中的冲突。下面是链接发生的一个很好的链接： http ://javapapers.com/core-java/java-hashtable/
在java中这是一个非常简单的哈希表实现。 在只有执行put()和get() ，但你可以很容易地添加你喜欢的任何东西。 它依赖于由所有对象实现的java的hashCode()方法。 你可以轻松地创build自己的界面，
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)); } }
