java - 难以理解链式哈希表的实现

Question

我正在研究java中链式哈希表的实现。麻烦是关于get()方法。索引值由key.hashCode() % table.length确定。 。假设表大小为10 key.hashCode() 是 124所以索引被发现为 4 。在每个循环中table[index]从 table[4] 开始，据我所知索引正在一一递增4,5,6,7... so on 。但指数 0,1,2,3 又如何呢？ ？他们被检查了吗？ (我认为不会)是否有可能在其中一个索引上出现 key ？ (我想是的)。另一个问题是null检查但最初没有任何 null key 的分配和value 。那么检查如何进行呢？是null尽快分配 private LinkedList<Entry<K, V>>[] table已声明？

// 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

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

另一个重要的一点是给定键的哈希码不应更改，因此它将始终映射到表中的相同索引。

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

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();
     }
 }