HashTables如何处理冲突?

我听说在我的学位课程中,如果新的密钥条目与另一个条目相冲突,则HashTable会将新条目放入“下一个可用”存储桶中。

如果在使用碰撞键调用一个背面时发生碰撞, HashTable将如何返回正确的值?

我假设KeysStringtypes,并且hashCode()返回通过说Java产生的默认值。

如果我实现自己的散列函数并将其用作查找表(即HashMapDictionary )的一部分,那么处理冲突的策略是什么?

我甚至看到有关素数的笔记! 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了一个空的槽。 另外在开放寻址技术中,当一个物品从一个槽中移出时,我们把一个墓碑表明这个物品从这里被移除,这就是为什么它是空的。

取自http://coder2design.com/hashing/

我听说在我的学位课程中,如果新的密钥条目与另一个条目相冲突,则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)); } }