HashTable 如何处理冲突？

小开

它将使用 equals 方法查看键是否存在，特别是在同一个 bucket 中是否有多个元素。

小开

我在学位课上听说 HashTable 将在下一个可用的桶，如果新的键入与另一个键入发生冲突。

这实际上是不正确的，至少对于 Oracle JDK (它的是是一个实现细节，在 API 的不同实现之间可能有所不同)。相反，每个 bucket 包含 Java8之前的条目的链接列表，以及 Java8或更高版本的平衡树。

then how would the HashTable still return the correct Value if this 当调用一个时发生冲突 back with the collision key?

It uses the equals() to find the actually matching entry.

如果我实现自己的散列函数 and use it as part of a look-up table (例如 HashMap 或 Dictionary) ，什么是存在处理 collisions?

有各种各样的冲突处理策略，有不同的优点和缺点。 Wikipedia 关于哈希表的条目给出了一个很好的概述。

小开

我强烈建议你阅读这篇最近出现在 HackerNews 上的博客文章: HashMap 在 Java 中是如何工作的

简而言之，答案是

如果两个不同的 HashMap 键对象具有相同的散列码？

它们会被存放在同一个桶里，但是没有链表的下一个节点。和键方法将用于 identify correct key value pair in HashMap.

小开

最佳答案

哈希表以两种方式之一处理冲突。

选项1: 通过让每个 bucket 包含散列到该 bucket 的元素的链接列表。这就是为什么错误的散列函数会使散列表中的查找非常慢。

选项2: 如果散列表条目都已满，那么散列表可以增加存储桶的数量，然后重新分配表中的所有元素。散列函数返回一个整数，散列表必须获取散列函数的结果，并根据表的大小对其进行修改，这样才能确保它将到达 bucket。因此，通过增加大小，它将重新散列和运行模计算，如果你幸运的话，可能会发送对象到不同的桶。

Java 在其散列表实现中同时使用选项1和选项2。

小开

关于 Java 的 HashMap 使用的算法有些混乱(在 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;
}

This method (cite is from lines 355 to 371) is called when looking up an entry in the table, for example from get(), containsKey() and some others. The for loop here goes through the linked list formed by the entry objects.

这里是条目对象的代码(第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);
}

这将在 bucket 的前面添加新的 Entry，并带有到旧的第一条目的链接(如果没有这样的链接，则为 null)。类似地，removeEntryForKey()方法遍历列表，只负责删除一个条目，让列表的其余部分保持不变。

因此，这里有一个每个桶的链接条目列表，我非常怀疑它从 _20变成了 _22，因为它从1.2开始就是这样的。

小开

这里有一个非常简单的 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));
}
}

小开

解决冲突的方法有很多种，有分离链接法、开放式寻址法、罗宾汉散列法、布谷鸟散列法等。

Java 使用分离链接来解决哈希表中的冲突: http://javapapers.com/core-java/java-hashtable/

小开

When you talked about "Hash Table will place a new entry into the 'next available' bucket if the new Key entry collides with another.", you are talking about the Open addressing strategy of Collision resolution of hash table.

哈希表有几种解决冲突的策略。

First kind of big method require that the keys (or pointers to them) be stored in the table, together with the associated values, which further includes:

单独链接

enter image description here

公开演讲

enter image description here

聚合散列
布谷鸟杂碎
罗宾汉
二选一散列
跳房子哈希

Another important method to handle collision is by 动态调整大小, which further has several ways:

通过复制所有条目来调整大小
递增调整大小
单调的琴键

编辑 : 以上是从 Wiki _ hash _ table借来的，你应该去看看，以获得更多的信息。

小开

There are multiple techniques available to handle collision. I will explain some of them

链接: 在链接中，我们使用数组索引来存储值。如果第二个值的散列码也指向同一个索引，那么我们将该索引值替换为一个链表，所有指向该索引的值都存储在链表中，实际的数组索引指向链表的头部。但是如果只有一个哈希代码指向数组的索引，那么该值将直接存储在该索引中。在检索值时应用相同的逻辑。这在 JavaHashMap/Hashtable 中用于避免冲突。

线性探测: 当表中的索引多于要存储的值时，就会使用这种技术。线性探测技术的工作原理是不断增加，直到找到一个空槽。伪代码如下:

index = h(k)


while( val(index) is occupied)


index = (index+1) mod n

双散列技术: 在这种技术中，我们使用两个散列函数 h1(k)和 h2(k)。如果 h1(k)处的槽被占用，那么第二个散列函数 h2(k)用于递增索引。伪代码如下:

index = h1(k)


while( val(index) is occupied)


index = (index + h2(k)) mod n

线性探测和双散列技术是开放式寻址技术的一部分，只有当可用的插槽数大于要添加的项数时才能使用。它比链接占用更少的内存，因为这里没有使用额外的结构，但是它的速度很慢，因为大量的运动会发生，直到我们找到一个空的插槽。同样在开放寻址技术中，当一个项目从插槽中移除时，我们放置一个墓碑来表明该项目从这里被移除，这就是为什么它是空的。

有关详细信息，请参阅 this site。

小开

从 Java 8开始的更新: Java 8使用一个自平衡树进行冲突处理，将最坏的情况从 O (n)改进为 O (log n)进行查找。自平衡树的使用是在 Java 8中引入的，作为链接(一直使用到 Java 7)的改进，后者使用链表，最糟糕的情况是 O (n)用于查找(因为它需要遍历链表)

为了回答你问题的第二部分，插入是通过将给定的元素映射到散列映射的底层数组中的给定索引来完成的，然而，当发生冲突时，所有元素仍然必须保留(存储在辅助数据结构中，而不仅仅是在底层数组中替换)。这通常是通过将每个数组组件(槽)作为辅助数据结构(又名 bucket)来完成的，并将元素添加到驻留在给定数组索引上的 bucket 中(如果 bucket 中不存在键，则替换它)。

在查找过程中，键被散列到相应的数组索引中，然后搜索与给定 bucket 中的(精确的)键匹配的元素。由于 bucket 不需要处理冲突(直接比较键) ，这解决了冲突问题，但是代价是必须在辅助数据结构上执行插入和查找。关键的一点是，在散列表中，键和值都被存储，因此即使散列冲突，键也会直接进行比较以获得相等性(在 bucket 中) ，因此可以在 bucket 中唯一地标识。

在没有冲突处理的情况下，冲突处理使 O (1)的插入和查找性能降低到链接的 O (n)(链表用作辅助数据结构)和自平衡树的 O (log n)。

References:

Java8对 HashMap 进行了以下改进/更改高碰撞情况下的物体。

Java7中添加的替代 String 散列函数已被删除。

包含大量碰撞键的桶将把它们的条目存储在一个平衡树中，而不是存储在后面的链表中达到某个临界点。

以上更改确保了 O (log (n))在最坏情况下的性能 (https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8)