HashMap的底层实现-JDK1.8之前

原创

代码小李

发布于 2025-01-30 10:31:13

700

在JDK 1.8之前，HashMap的底层实现主要基于数组+链表的数据结构。具体来说，HashMap内部维护了一个数组，数组的每个元素都是一个单向链表的头节点。当存储键值对时，HashMap会根据键（key）的哈希值计算出该键值对应该存放在数组的哪个位置，如果该位置已经有其他键值对，则新的键值对会被添加到该位置的链表中。

主要特点

数组：HashMap内部使用一个数组来存储数据，数组的每个元素是一个Entry对象，Entry是HashMap的一个静态内部类，表示键值对。
链表：当多个键值对的哈希值相同（即发生了哈希冲突），这些键值对会被存储在同一个数组位置的链表中。
哈希函数：HashMap使用键的hashCode方法计算哈希值，并通过一定的算法将哈希值转换为数组的索引。
扩容机制：当HashMap中的元素数量超过某个阈值（通常是数组长度乘以负载因子，默认负载因子为0.75）时，HashMap会自动扩容，通常将数组的长度扩大一倍，并重新计算所有键值对的位置。

具体实现

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 默认初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // 默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 存储键值对的数组
    transient Entry<K,V>[] table;

    // 键值对的条目数
    transient int size;

    // 阈值，当实际大小超过此值时，会触发扩容
    int threshold;

    // 负载因子
    final float loadFactor;

    // 内部类，表示键值对
    static class Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;

        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final int hashCode() {
            return (key == null   ? 0 : key.hashCode()) ^
                   (value == null ? 0 : value.hashCode());
        }

        public final String toString() {
            return key + "=" + value;
        }
    }

    // 构造函数
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        setThreshold(initialCapacity);
    }

    // 计算阈值
    private void setThreshold(int initialCapacity) {
        threshold = (int)(initialCapacity * loadFactor);
    }

    // 扩容方法
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

    // 重新计算键值对的位置
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while (null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

    // 计算哈希值
    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 计算数组索引
    static int indexFor(int h, int length) {
        return h & (length-1);
    }
}