难以理解哈希 table 与链接的实现

Question

我正在研究散列 table 并通过其实现在 java 中进行链接。麻烦是关于 get() 方法。索引值由 key.hashCode() % table.length 确定。假设 table 大小为 10 并且 key.hashCode() 为 124，因此找到的索引为 4。对于每个循环 table[index] 从 table[4] 开始，AFAIK 索引正在一个一个递增 4,5,6,7... so on。但是索引 0,1,2,3 呢？他们被检查了吗？（我认为不）是否有可能在其中一个索引上出现 key ？（我想是的）。另一个问题是 null 检查，但最初 key 和 value 没有任何 null 分配。那么检查如何工作呢？是否在声明 private LinkedList<Entry<K, V>>[] table 后立即分配 null？

// Data Structures: Abstraction and Design Using Java, Koffman, Wolfgang

package KW.CH07;

import java.util.AbstractMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.StringJoiner;

/**
 * Hash table implementation using chaining.
 * @param <K> The key type
 * @param <V> The value type
 * @author Koffman and Wolfgang
 **/
public class HashtableChain<K, V> 
// Insert solution to programming project 7, chapter -1 here
    implements KWHashMap<K, V> {

    /** The table */
    private LinkedList<Entry<K, V>>[] table;
    /** The number of keys */
    private int numKeys;
    /** The capacity */
    private static final int CAPACITY = 101;
    /** The maximum load factor */
    private static final double LOAD_THRESHOLD = 3.0;

    // Note this is equivalent to java.util.AbstractMap.SimpleEntry
    /** Contains key-value pairs for a hash table. 
        @param <K> the key type
        @param <V> the value type
     */
    public static class Entry<K, V> 
// Insert solution to programming project 6, chapter -1 here
    {

        /** The key */
        private final K key;
        /** The value */
        private V value;

        /**
         * Creates a new key-value pair.
         * @param key The key
         * @param value The value
         */
        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        /**
         * Retrieves the key.
         * @return The key
         */
        @Override
        public K getKey() {
            return key;
        }

        /**
         * Retrieves the value.
         * @return The value
         */
        @Override
        public V getValue() {
            return value;
        }

        /**
         * Sets the value.
         * @param val The new value
         * @return The old value
         */
        @Override
        public V setValue(V val) {
            V oldVal = value;
            value = val;
            return oldVal;
        }

// Insert solution to programming exercise 3, section 4, chapter 7 here
    }

    // Constructor
    public HashtableChain() {
        table = new LinkedList[CAPACITY];
    }

    // Constructor for test purposes
    HashtableChain(int capacity) {
        table = new LinkedList[capacity];
    }

    /**
     * Method get for class HashtableChain.
     * @param key The key being sought
     * @return The value associated with this key if found;
     *         otherwise, null
     */
    @Override
    public V get(Object key) {
        int index = key.hashCode() % table.length;
        if (index < 0) {
            index += table.length;
        }
        if (table[index] == null) {
            return null; // key is not in the table.
        }
        // Search the list at table[index] to find the key.
        for (Entry<K, V> nextItem : table[index]) {
            if (nextItem.getKey().equals(key)) {
                return nextItem.getValue();
            }
        }

        // assert: key is not in the table.
        return null;
    }

    /**
     * Method put for class HashtableChain.
     * @post This key-value pair is inserted in the
     *       table and numKeys is incremented. If the key is already
     *       in the table, its value is changed to the argument
     *       value and numKeys is not changed.
     * @param key The key of item being inserted
     * @param value The value for this key
     * @return The old value associated with this key if
     *         found; otherwise, null
     */
    @Override
    public V put(K key, V value) {
        int index = key.hashCode() % table.length;
        if (index < 0) {
            index += table.length;
        }
        if (table[index] == null) {
            // Create a new linked list at table[index].
            table[index] = new LinkedList<>();
        }

        // Search the list at table[index] to find the key.
        for (Entry<K, V> nextItem : table[index]) {
            // If the search is successful, replace the old value.
            if (nextItem.getKey().equals(key)) {
                // Replace value for this key.
                V oldVal = nextItem.getValue();
                nextItem.setValue(value);
                return oldVal;
            }
        }

        // assert: key is not in the table, add new item.
        table[index].addFirst(new Entry<>(key, value));
        numKeys++;
        if (numKeys > (LOAD_THRESHOLD * table.length)) {
            rehash();
        }
        return null;
    }

    /** Returns true if empty 
        @return true if empty
     */
    @Override
    public boolean isEmpty() {
        return numKeys == 0;
    }

}

Answer 1

我认为您没有完全正确地想象您的哈希 table。哈希有两个同样好的简单实现 table.

方法 1 使用链表：链表的数组（实际上是 Vector）。

给定一个 "key"，您可以得出该键 (*) 的哈希值。您取该哈希值相对于向量当前大小的余数，我们称其为 "x"。然后依次搜索 vector[x] 指向的链表以匹配您的密钥。

(*) 您希望散列值合理分布。有复杂的算法可以做到这一点。希望您的 HashCode 的 JVM 实现在这方面做得很好。

方法 2 避免使用链表：创建一个 Vector 并计算 Vector 的索引（如上所述）。然后你看看 Vector.get(x)。如果那是您想要的键，您的 return 对应的值。让我们假设不是。然后你看Vector.get(x+1)，Vector.get(x+2)等等，最终会出现以下三种情况之一：

a) 你找到了你要找的钥匙。然后你return对应的值。 b) 你发现一个空条目（key == null）。 Return null 或您选择表示 "this isn't the droid you're looking for" 的任何值。 c) 您已经检查了 Vector 中的每个条目。同样，return null 或其他。

检查 (c) 是一种预防措施，因此如果哈希 Table 恰好已满，您将不会永远循环。如果散列 table 即将满（您可以计算已使用的条目数），您应该重新分配一个更大的散列 table。理想情况下，您希望保持散列 table 足够稀疏，以至于您永远无法到达任何地方 near 搜索整个 table：这破坏了散列的整个目的 table——你可以在比线性时间少得多的时间内搜索它，理想情况下是顺序 1（即比较次数 <= 一个小常数）。我建议您分配的 Vector 至少是您希望放入其中的条目数的 10 倍。

在你的问题中使用 "chaining" 这个词向我暗示你想要实现第二种类型的哈希 table。

顺便说一句，你不应该使用 10 作为散列的大小 table。大小应该是素数。

希望对您有所帮助。

Answer 2

Assume that the table size is 10 and key.hashCode() is 124 so index is found as 4. In for each loop table[index] is started from table[4]

正确。

there are null checks but initially there is no any null assignment for key and value. So how can the checking work?

初始化对象数组时，所有值都设置为null。

index is being incremented one by one 4,5,6,7... so on. But what about indices 0,1,2,3? Are they been checked? (I think no) Isn't there any possibility that occurring of key on one of the indices? (I think yes).

看来这里有些误会。首先，考虑这样的数据结构（已经添加了数据）：

table:
[0] -> null
[1] -> LinkedList -> item 1 -> item 2 -> item 3
[2] -> LinkedList -> item 1
[3] -> null
[4] -> LinkedList -> item 1 -> item 2
[5] -> LinkedList -> item 1 -> item 2 -> item 3 -> item 4
[6] -> null

另一个重要的一点是给定 key 的哈希码不应该改变，因此它将始终映射到 table.

中的相同索引

假设我们用一个值调用 get，哈希码将其映射到 3，那么我们知道它不在 table:

中

if (table[index] == null) {
    return null; // key is not in the table.
}

如果另一个键映射到 1，现在我们需要迭代 LinkedList：

 // LinkedList<Entry<K, V>> list = table[index]
 for (Entry<K, V> nextItem : table[index]) {
     // iterate over item 1, item 2, item 3 until we find one that is equal.
     if (nextItem.getKey().equals(key)) {
         return nextItem.getValue();
     }
 }

难以理解哈希 table 与链接的实现

trouble understanding implementation of hash table with chaining

java

hashtable

chaining

data-structures