我听说过我的学位课程，如果新的密钥条目与另一个条目相冲突，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