HashTable
会将新条目放入“下一个可用”的桶中。如果在使用冲突键调用时发生冲突,
HashTable
如何返回正确的值?我假设
Keys
是String
类型,并且hashCode()
返回由Java生成的默认值。如果我实现自己的哈希函数并将其用作查找表的一部分(例如
HashMap
或Dictionary
),存在哪些处理冲突的策略?我甚至看到了与质数相关的注释!这些信息在谷歌搜索中并不清楚。
哈希表处理冲突的方式有两种。
选项1:每个桶都包含一个链接列表,其中存储了散列到该桶的元素。这就是为什么糟糕的哈希函数会使哈希表查找变得非常慢。
选项2:如果哈希表条目已全部满,则哈希表可以增加它拥有的桶数,然后重新分配表中所有元素。哈希函数返回一个整数,哈希表必须将哈希函数的结果与表的大小进行模运算,以确保它能够到达正确的桶。因此,通过增加大小,将重新计算哈希并执行模运算,如果幸运的话,可能会将对象发送到不同的桶中。
Java在其哈希表实现中同时使用选项1和2。
处理冲突的方法有多种,我将解释其中一些。
链表法: 在链表法中,我们使用数组索引来存储值。如果第二个值的哈希码也指向相同的索引,则我们用一个链接列表替换该索引值,并将指向该索引的所有值存储在链接列表中,实际的数组索引指向链接列表的头部。 但是,如果只有一个哈希码指向数组的一个索引,那么该值就直接存储在该索引中。检索值时应用相同的逻辑。这被用于Java HashMap/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
线性探测和双重哈希技术是开放地址技术的一部分,只有在可用插槽的数量大于要添加的项数时才能使用。它比链接更节省内存,因为这里没有使用额外的结构,但由于需要进行许多移动直到找到空插槽,所以它很慢。此外,在开放地址技术中,当从插槽中删除一个项目时,我们会放置一个墓碑来指示该项目已经从此处删除,这就是为什么它是空的。
欲了解更多信息,请参见此网站。
我强烈建议您阅读最近在HackerNews上出现的博客文章: Java中HashMap的工作原理
简而言之,答案是:
如果两个不同的HashMap键对象具有相同的哈希码,会发生什么情况?
它们将存储在同一个桶中,但没有链表的下一个节点。HashMap将使用keys equals()方法来识别正确的键值对。
public V get(Object key)
(与上面相同的版本)。如果您找到确切的版本,其中包含这些链接列表,我会很感兴趣知道。 - Nikita Rybake = e.next
不是 ++index
。+1 - Nikita RybakJava 7中添加的备用String哈希函数已被删除。
包含大量冲突键的桶在达到一定阈值后将在平衡树中而不是链表中存储它们的条目。
由于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;
}
get()
、containsKey()
和其他一些方法。这里的for循环遍历由条目对象形成的链表。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);
}
它将使用equals方法来检查键是否存在,特别是在同一个桶中有多个元素的情况下。
这是一个非常简单的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/