0

我读了很多次，在哈希表中，当发生冲突时，一个键具有多个值，它存储在链表中，然后它会进行 equals 调用以检查哪些键映射到所需的值，但我看到哈希表的代码它没有任何链表代码一个 put 方法或 get 方法。它使用 Entry[] 数组，我不明白这将如何用作链表。

for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
        V old = e.value;
        e.value = value;
        return old;
        }
    }

请指导并消除我的疑问。

4

1 回答 1

2

我认为 JVM 之间的实现可能不同，但据我了解，使用了链表（但不是必需的 java.util.LinkedList）。这就是我使用的 JVM 中的 HashTable 中“put”的实现方式：

public Object put(Object key, Object value) {
    // Make sure the value is not null
    if (value == null) throw new NullPointerException();

    // Makes sure the key is not already in the hashtable.
    HashtableEntry e;
    HashtableEntry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;

    for (e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
        Object old = e.value;
        e.value = value;
        return old;
        }
    }

此版本与您发布的版本之间存在一些差异，但我认为它们背后的逻辑是相同的。HashtableEntry 如下所示：

class HashtableEntry {
    int hash;
    Object key;
    Object value;
    HashtableEntry next;
(...)

“HashtableEntry next”引用确实使 HashtableEntry 成为链表（链表是一种结构，其中每个元素都引用另一个相同类型的元素，除非它是列表中的最后一个元素）。我认为您正在寻找的是 java.util.LinkedList 但 HastTable 以自己的方式实现链表结构。

于 2012-12-08T16:43:07.557 回答