HashMap源码分析，看一遍就懂！("HashMap源码深入解析，轻松看懂不求人！")

原创

ithorizon 7个月前 (10-19) 阅读数 32 #后端开发

HashMap源码分析，看一遍就懂！

一、HashMap简介

HashMap是Java中常用的数据结构之一，核心用于存储键值对（Key-Value Pair）。它基于散列（Hash）表实现，具有高效的查询和插入性能。本文将深入分析HashMap的源码，帮助你轻松领会其工作原理。

二、HashMap的数据结构

HashMap底层采用数组加链表（或红黑树）的数据结构。当哈希表的某个索引位置出现冲突时，会采用链表或红黑树来存储多个键值对。

三、HashMap的核心成员变量


// 存储元素的数组
transient Node<K,V>[] table;
// 实际存储的键值对数量
transient int size;
// 阈值，当size大于threshold时，会出现扩容
int threshold;
// 负载因子，用于计算阈值
final float loadFactor;
// 用于迅速未果迭代器的modCount
transient int modCount;

四、HashMap的构造方法

HashMap提供了多个构造方法，以下是常用的两个构造方法：


// 默认构造方法
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // 默认负载因子
    this.threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
}
// 指定初始容量和负载因子的构造方法
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0 || loadFactor <= 0)
        throw new IllegalArgumentException("Illegal initial capacity or load factor");
    this.loadFactor = loadFactor;
    this.threshold = (int)(initialCapacity * loadFactor);
    this.table = new Node<K,V>[initialCapacity];
}

五、HashMap的put方法

put方法用于向HashMap中添加键值对。以下是put方法的源码实现：


public V put(K key, V value) {
    if (table == null || table.length == 0)
        resize();
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    // 检查是否已经存在相同的键
    for (Node<K,V> e = table[i]; e != null; e = e.next) {
        K k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // 添加新节点
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

六、HashMap的get方法

get方法用于从HashMap中获取键对应的值。以下是get方法的源码实现：


public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Node<K,V> e = getNode(hash(key), key);
    if (e == null)
        return null;
    return e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab;
    Node<K,V> first, e;
    int i;
    if ((tab = table) != null && (first = tab[i = (tab.length - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((key == null && first.key == null) ||
             (key != null && key.equals(first.key)))) {
            return first;
        }
        if ((e = first.next) != null) {
            if (first instanceof TreeNode) {
                return ((TreeNode<K,V> first).getTreeNode(hash, key);
            }
            do {
                if (e.hash == hash &&
                    ((key == null && e.key == null) ||
                     (key != null && key.equals(e.key)))) {
                    return e;
                }
            } while ((e = e.next) != null);
        }
    }
    return null;
}

七、HashMap的扩容机制

当HashMap中的元素数量约为阈值时，会出现扩容。以下是扩容方法的源码实现：


void resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int newCap = oldCap <= DEFAULT_INITIAL_CAPACITY ? DEFAULT_INITIAL_CAPACITY :
        oldCap <= MAXIMUM_CAPACITY ? oldCap * 2 : MAXIMUM_CAPACITY;
    int newThr = 0;
    if (oldCap > 0) {
        if (oldThr > 0) // preserve threshold
            newThr = oldThr;
        else // calculate threshold
            newThr = oldCap * loadFactor;
    }
    else if (newCap > 0) {
        newThr = (int)(newCap * loadFactor);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else { // 如果链表不为空，需要重新计算索引位置
                    Node<K,V> loHead = e, loTail = e;
                    Node<K,V> hiHead = null, hiTail = null;
                    while (e != null) {
                        Node<K,V> next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            loTail.next = next;
                            loTail = next;
                        }
                        else {
                            if (hiHead == null)
                                hiHead = e;
                            if (hiTail != null)
                                hiTail.next = e;
                            hiTail = next;
                        }
                        e = next;
                    }
                    if (loTail != null) {
                        newTab[j] = loHead;
                        loTail.next = null;
                    }
                    if (hiTail != null) {
                        newTab[j + oldCap] = hiHead;
                        hiTail.next = null;
                    }
                }
            }
        }
    }
}