我正在尝试在Java中构建一个HashMap类的简单实现，用于学习目的。我知道重新散列是如何工作的（hashmap或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; 
        }
    }
}