java - HashMap 如何识别内部数组中的哪些位置包含元素？

Question

出于学习目的，我正在尝试用 Java 构建 HashMap 类的简单实现。我知道重新散列的工作原理 ( Rehashing process in hashmap or hashtable )。

重新散列时，内部数组中存在的所有元素都会被识别，并且可以通过基于新散列函数重新计算它们的散列来确定它们在新数组中的位置。但是，如何识别数组中存在的所有元素？

是否有某种机制可以跟踪所有键，或者是否有一种机制可以跟踪包含元素的内部数组中的索引？

备选方案(我在实现中使用的)是扫描整个数组以查找元素。然而，这可能效率低下，因为扫描空桶会浪费大量时间。有没有更好的办法？

这是我的实现。这里的重点是 rehash(int) 函数。

public class HashMap<T, U> {
    private static final int MIN_CAPACITY = 16; 
    private static final double LOAD_FACTOR = 0.75; 
    private int mCount = 0; 
    private HashMapItem<T, U>[] mArray = (HashMapItem<T, U>[]) new HashMapItem[MIN_CAPACITY]; 

    public HashMap() {
    }

    private void rehash(int newCapacity) {
        HashMapItem<T, U>[] newArray = (HashMapItem<T, U>[]) new HashMapItem[newCapacity]; 
        for (HashMapItem<T, U> hashMapItem : mArray) {
            if (hashMapItem != null) {
                HashMapItem<T, U> currentNode = hashMapItem; 
                while (currentNode != null) {
                    putInArray(currentNode.key, currentNode.value, newArray); 
                    currentNode = currentNode.next; 
                }
            }
        }
        mArray = newArray; 
    }

    private int hashFunction(T key, int arrayCapacity) {
        return Math.abs(key.hashCode()) % arrayCapacity; 
    }

    private boolean putInArray(T key, U value, HashMapItem<T, U>[] array) {
        boolean duplicateKey = false; 
        int index = hashFunction(key, array.length); 
        HashMapItem<T, U> hashMapItem = array[index]; 
        if (hashMapItem == null) array[index] = new HashMapItem<T, U>(key, value); 
        else {
            HashMapItem<T, U> currentNode = hashMapItem; 
            while (true) {
                if (currentNode.key.equals(key)) {
                    currentNode.value = value; 
                    duplicateKey = true; 
                    break; 
                }
                else if (currentNode.next != null) currentNode = currentNode.next; 
                else break; 
            }
            if (!duplicateKey) currentNode.next = new HashMapItem<T, U>(key, value); 
        }
        return duplicateKey; 
    }

    public void put(T key, U value) {
        if (mCount >= mArray.length * LOAD_FACTOR) rehash(mArray.length << 1); 
        boolean duplicateKey = putInArray(key, value, mArray); 
        if (!duplicateKey) mCount++; 
    }

    public U get(T key) {
        int index = hashFunction(key, mArray.length); 
        HashMapItem<T, U> hashMapItem = mArray[index]; 
        if (hashMapItem != null) {
            HashMapItem<T, U> currentNode = hashMapItem; 
            while (currentNode != null) {
                if (currentNode.key.equals(key)) return currentNode.value; 
                currentNode = currentNode.next; 
            }
        }
        return null; 
    }

    public U remove(T key) {
        U removedItem = null; 
        int index = hashFunction(key, mArray.length); 
        HashMapItem<T, U> hashMapItem = mArray[index]; 
        if (hashMapItem != null) {
            HashMapItem<T, U> currentNode = hashMapItem; 
            HashMapItem<T, U> previousNode = null; 
            while (currentNode != null) {
                if (currentNode.key.equals(key)) {
                    removedItem = currentNode.value; 
                    if (previousNode == null) mArray[index] = currentNode.next; 
                    else previousNode.next = currentNode.next; 
                    break; 
                }
                previousNode = currentNode; 
                currentNode = currentNode.next; 
            }
        }
        if (removedItem != null) mCount--; 
        return removedItem; 
    }

    public int count() {
        return mCount; 
    }

    private class HashMapItem<T, U> {
        T key; 
        U value; 
        HashMapItem<T, U> next; 

        public HashMapItem(T key, U value) {
            this.key = key; 
            this.value = value; 
        }
    }
}

Answer 1

解决这个问题有两种方法:

• 维护非空桶的链表结构 - 这可以相当有效地完成。它还可以为您提供迭代的可预测性，类似于 LinkedHashMap 或
• 在重新散列时扫描所有位置 - 这正是您正在做的。

实际上，选择归结为支付内存以减少 CPU 使用。如果您必须经常迭代 HashMap ，第一个解决方案更好。如果你只在重新散列时才这样做，那么第二种解决方案更好，因为只有当你的 map 相对满时才会发生重新散列。换句话说，扫描期间的大部分检查都会成功。