聊聊 HashMap

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;  //链表节点中的下一个 Entry<K,V> 对象
    int hash;         //当前 Entry 对象的 hash 值
    //构造函数
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
    //其它代码省略 ...
}

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);  //1.判断 key 是否为 Null，为 Null 直接存放在数组下标 0 的位置
    int hash = hash(key);  //2.计算 key 的 hash 值
    int i = indexFor(hash, table.length);  //3.通过 hash 值计算数组下标 index
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //4.判断 hash 值和 key 值是否相同，相同则覆盖并返回旧值
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;  //5.修改次数 +1
    addEntry(hash, key, value, i);  //6.将 key-value 封装为 Entry 对象并添加，
    return null;
}
static int indexFor(int h, int length) {
    return h & (length-1);  // 数组长度-1，按位与计算出下标
}
void addEntry(int hash, K key, V value, int bucketIndex) {
    //如果加入新元素超过阈值，则扩容为原来的2倍大小
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);  // 创建 Entry
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    //若 e 不为空，则说明发生 hash 碰撞，将 Entry 插入到链表头，将原有节点(e)作为下一个节点
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++; //HashMap 元素数量 +1
}

public V get(Object key) {
    if (key == null)
        return getForNullKey();  //1.判断 key 是否 Null，为空直接获取数组下标为 0 的元素
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();  //三目表达式判断
}
final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key);  //计算 key 的 hash 值
    //2.indexFor() 计算数组下标并循环遍历该下标处的链表节点
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null;e = e.next) {
        Object k;
        //3.判断是否 hash 值和 key 值是否相同且不为 null，不匹配则循环判断下一节点
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;  //1.获取旧数组长度
    //MAXIMUM_CAPACITY 的值为 1<<30，是 Integer.MAX_VALUE 的一半减1，已经大的夸张，基本不存在扩容情况
    //所以重新设置阈值后直接返回
    if (oldCapacity == MAXIMUM_CAPACITY) { 
        threshold = Integer.MAX_VALUE;
        return;
    }
    //2.创建一个新的数组，大小为原来的2倍
    Entry[] newTable = new Entry[newCapacity];
    //3.获取是否需要重新计算 hash
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
        (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    //4.扩容的关键方法，旧数组数据复制到新数组
    transfer(newTable, rehash);
    table = newTable;
    //5.重新计算阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
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;
            //判断是否需要重新计算 hash
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);  //计算数组下标
            e.next = newTable[i];  //头插法，链表头部插入，已有的节点往后移作为 next 节点
            newTable[i] = e;  //头部插入
            e = next;
        }
    }
}