HashMap源码分析

文章目录

1. 继承体系
2. 源码分析
1. 2.1. 属性
2. 2.2. put(K key, V value) 方法

继承体系

在 Java 中，HashMap 的实现采用了（数组 + 链表 + 红黑树）的复杂结构，数组的一个元素又称作桶。

在添加元素时，会根据 hash 值算出元素在数组中的位置，如果该位置没有元素，则直接把元素放置在此处，如果该位置有元素了，则把元素以链表的形式放置在链表的尾部。

当一个链表的元素个数达到一定的数量（且数组的长度达到一定的长度）后，则把链表转化为红黑树，从而提高效率。

数组的查询效率为 O(1)，链表的查询效率是 O(k)，红黑树的查询效率是 O(log k)，k为桶中的元素个数，所以当元素数量非常多的时候，转化为红黑树能极大地提高效率。

源码分析

属性

/**
 * 默认初始容量为 16
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/**
 * 最大容量为 2 的 30 次方
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

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

/**
 * 当一个桶中的元素 ≥ 8 时进行树化
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 当一个桶中的元素 ≤ 6 时把树转换成链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 当桶的个数达到 64 的时候进行树化
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * 数组，又叫做桶
 */
transient Node<K, V>[] table;

/**
 * 作为 enterSet() 的缓存
 */
transient Set<Map.Entry<K, V>> entrySet;

/**
 * 元素的数量
 */
transient int size;

/**
 * 修改次数，用于在迭代的时候执行快速失败策略
 */
transient int modCount;

/**
 * 当桶的使用数量达到多少时进行扩容，threshold = capacity * loadFactor
 */
int threshold;

/**
 * 装载因子
 */
final float loadFactor;

put(K key, V value) 方法

public V put(K key, V value) {
    // 调用 hash(key) 计算出 key 的 hash 值
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    // 如果 key 为 null，则 hash 值为0，否则调用 key 的 hashCode() 方法
    // 并让高 16 位与整个 hash 异或，这样做是为了使计算出的 hash 更分散
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果桶的数量为 0，则初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        // 调用 resize() 初始化
        n = (tab = resize()).length;
    // (n-1) & hash 计算元素在哪个桶中
    // 如果这个桶中还没有元素，则把这个元素放在桶中的第一个位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 新建一个节点放在桶中
        tab[i] = newNode(hash, key, value, null);
    else {
        // 如果桶中已经有元素存在了
        Node<K,V> e; K k;
        // 如果桶中第一个元素的 key 与待插入元素的 key 相同，保存到 e 中用于后续修改 value 值
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            // 如果第一个元素是树节点，则调用树节点的 putTreeVal 插入元素
            e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 遍历这个桶对应的链表，binCount 用于存储链表中元素的个数
            for (int binCount = 0; ; ++binCount) {
                // 如果链表遍历完了都没有找到相同 key 的元素，则 key 对应的元素不存在，则在链表最后插入一个新节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果插入新节点后链表长度 > 8，则判断是否需要树化，因为第一个元素没有加到 binCount 中，所以 -1
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果待插入的 key 在链表中找到了，则退出循环
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果找到了对应 key 的元素
        if (e != null) { // existing mapping for key
            // 记录下旧值
            V oldValue = e.value;
            // 判断是否需要替换旧值
            if (!onlyIfAbsent || oldValue == null)
                // 替换旧值为新值
                e.value = value;
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 到这里了说明没有找到元素
    // 修改次数 +1
    ++modCount;
    // 元素数量 +1，判断是否需要扩容
    if (++size > threshold)
        // 扩容
        resize();
    afterNodeInsertion(evict);
    // 没有找到元素返回 null
    return null;
}

计算 key 的 hash 值；
如果桶（数组）数量为 0，则初始化桶；
如果 key 所在的桶没有元素，则直接插入；
如果 key 所在的桶中的第一个元素的 key 与待插入的key相同，说明找到了元素，转后续流程（9）处理；
如果第一个元素是树节点，则调用树节点的 putTreeVal() 寻找元素或插入树节点；
如果不是以上三种情况，则遍历桶对应的链表查找 key 是否存在于链表中；
如果找到了对应 key 的元素，则转后续流程（9）处理；
如果没找到对应 key 的元素，则在链表最后插入一个新节点并判断是否需要树化；
如果找到了对应 key 的元素，则判断是否需要替换旧值，并直接返回旧值；
如果插入了元素，则数量加 1 并判断是否需要扩容；