JDK7 HashMap 源码分析

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

1、实现的接口

从文档中可以看出 HashMap 实现了 Serializable、Cloneable、Map<K,V>三个接口

Serializable：序列化接口

Cloneable：克隆接口

Map<K,V>：存储键值对的容器接口

2、子类

直接子类： LinkedHashMap、PrinterStateReasons

3、继承的类

AbstractMap

4、源码分析

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

默认初始容量为 $1 < < 4$ 即 16

static final int MAXIMUM_CAPACITY = 1 << 30;

最大容量为 $1 < < 30$ 即 1073741824

static final float DEFAULT_LOAD_FACTOR = 0.75f;

加载因子为 0.75

static final Entry<?,?>[] EMPTY_TABLE = {};

一个不能修改引用的 Entry 空键值对数组

transient Entry<?,?>[] table = EMPTY_TABLE;

transient 关键字，防止在序列化时序列化不必要的属性

把空数组的引用赋值给 table

transient int size;

键值对映射的数量

int threshold;

阈值：到达这个值后就进行扩容

$阈值 = 容量 * 加载因子$

final float loadFactor;

最终的加载因子

transient int modCount;

HashMap 修改的次数

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

默认的最大阈值 int 类型的最大值

transient int hashSeed = 0;

hash种子初始化为 0

public HashMap(int initialCapacity, float loadFactor) {
    // 如果容量小于 0 抛出异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
    // 如果指定的容量 > 最大容量，那指定容量就是最大容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
    // 如果加载因子 <= 0 或 不是 flaot 类型就抛出异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

    // 加载因子初始化
        this.loadFactor = loadFactor;
    // 阈值 = 指定容量
        threshold = initialCapacity;
        init();
    }

HashMap 的有参构造函数，initialCapacity 指定容量，loadFactor 指定加载因子

void init() {
    }

init 方法为空函数，没有方法体

public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

只指定容量，使用默认的加载因子，调用双参构造函数

public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

无参构造函数，使用默认容量(16)和默认的加载因子(0.75)

void resize(int newCapacity) {
    // 将 table 用 oldTable 存储
        Entry<?,?>[] oldTable = table;
    // 旧容量为 oldCapacity
        int oldCapacity = oldTable.length;
    // 如果旧容量为最大容量, 阈值就为 int 的最大值 7fffffff
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
	// 定义新的 Entry 数组 newTable
        Entry<?,?>[] newTable = new Entry<?,?>[newCapacity];
    // 
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 将新的 NewTable 赋值给 table
        table = newTable;
    // 计算新的阈值
    // 阈值 = min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1)
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

// 初始化 Hash 种子
final boolean initHashSeedAsNeeded(int capacity) {
    // 先判断当前的 hashSeed 是否等于 0，用 currentAltHashing 保存
        boolean currentAltHashing = hashSeed != 0;
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean switching = currentAltHashing ^ useAltHashing;
        if (switching) {
            hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }

// 新的 table 表，是否有 hash 种子
void transfer(Entry<?,?>[] newTable, boolean rehash) {
    // 将 table 定义为原Entry数组
        Entry<?,?>[] src = table;
    // newTable 的长度为 newCapacity
        int newCapacity = newTable.length;
    // 遍历原Entry数组
        for (int j = 0; j < src.length; j++) {
            // 将原数组的值对应下标放到新的数组中
            Entry<K,V> e = (Entry<K,V>)src[j];
            // 只要 e 不为 null 就一直循环
            while(null != e) {
                // 将 e 的下一个取出来，用 next 保存
                Entry<K,V> next = e.next;
                // 如果有 hash 种子
                if (rehash) {
                    // 判断 e.key(e的键) 是否为 null 是就为 0，否就为e.key 的 hash 值
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                // 返回 e.hash 的索引位置
                int i = indexFor(e.hash, newCapacity);
                // 将Entry数组的第 i 个元素放到 e.next 形成链表
                e.next = (Entry<K,V>)newTable[i];
                // 将 e 放到 i 的位置
                newTable[i] = e;
                // 将下一个赋给 e 进行循环
                e = next;
            }
        }
    }

final int hash(Object k) {
    // hash 种子用 h 来保存
        int h = hashSeed;
    // 如果 h 不为 0 且 k 是 String 的实例
        if (0 != h && k instanceof String) {
            // 返回 32 位的 hash 值
            return sun.misc.Hashing.stringHash32((String) k);
        }
	// h = h ^ k.hashCode();
        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    // 返回 h % length
        return h & (length-1);
    }

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 扩容为当前 table 长度的两倍
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

总结：从HashMap的底层源码中可以看出
数据结构为：数组 + 单向链表（使用的前插法）
默认初始容量为 16，默认加载因子为 0.75
从 addEntry 方法可以看出扩容为：原数组长度 * 2
没有 synchronized 关键字修饰：线程不安全
在扩容时二次哈希，重新获取位置

原文链接：https://blog.csdn.net/m0_51900835/article/details/124732163