[备份] Java HashMap 源码研究

介绍

Hash

Hash也称散列和哈希。简单理解是把任意长度的输入通过Hash算法变成固定长度的输出，原始数据映射后的二进制串就是哈希值。由于哈希值空间远小于输入空间，一定存在不同输入被映射到相同输出的情况，又被称为抽屉原理

特点：

• 不可能从哈希值反推出原始数据
• 输入数据微小变化会产生完全不同的哈希值
• 算法应该高效
• 减小冲突概率

Node

我们传入hashmap的item其实是node对象，首先来看node是怎样的，图里大致可以看出hashmap由一个node数组构成，在一些特殊情况下会转为红黑树，具体将在后续分析

xxxxxxxxxx
static class Node<K,V> implements Map.Entry<K,V> {
    // 经过扰动函数的hashcode
    final int hash;
    // 输入key
    final K key;
    // 输入value
    V value;
    // node数组存放碰撞后形成的链表
    Node<K,V> next;
    ......
}

Put

Node数组应该是2的次方倍长度，当我们put一个k-v时，会发生以下的事

• 获取key的哈希值
• 经过绕过函数，获得更散列的哈希值
• 构造出Node对象
• 经过路由算法得到Node应该存放在数组的位置

其中路由算法大致是：(table.length-1)&node.hash

某种情况下，经过路由算法会得到相同的位置，正是这时候碰撞形成链表

当链表碰撞变地很长时候，链表查找效率会较低

源码分析

常量

默认长度16（1左移4位）和最大长度

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

负载因子0.75，后续分析

xxxxxxxxxx
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

树化阈值（在什么情况下链表转为红黑树）

xxxxxxxxxx
    static final int TREEIFY_THRESHOLD = 8;

树降级阈值（在什么情况下红黑树转为链表）

xxxxxxxxxx
    static final int UNTREEIFY_THRESHOLD = 6;

另一个树化阈值，node数组长度达到64后才升级为树

xxxxxxxxxx
    static final int MIN_TREEIFY_CAPACITY = 64;

属性

哈希表Node数组

xxxxxxxxxx
    transient Node<K,V>[] table;

暂时不用关心的属性

xxxxxxxxxx
    transient Set<Map.Entry<K,V>> entrySet;

当前哈希表中元素个数

xxxxxxxxxx
    transient int size;

当前哈希表结构修改次数

xxxxxxxxxx
    transient int modCount;

当哈希表中元素超过阈值时扩容

xxxxxxxxxx
    int threshold;

负载因子，一般不会改，作用是计算threshold threshold = capacity * loadFactor

xxxxxxxxxx
    final float loadFactor;

构造方法

双参数构造方法

xxxxxxxxxx
    public HashMap(int initialCapacity, float loadFactor) {
        // initialCapacity校验
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
         // loadFactor校验
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        // 计算threshold
        this.threshold = tableSizeFor(initialCapacity);
    }

跟入tableSizeFor 返回一个大于等于cap的数，并一定是2的次方 该函数比较巧妙，可以自行带入一个数进行计算，效果是恰好得到当前数下一个2的次方数 例如输入9会得到16，输入15也会得到16。将输入二进制每一位置1并在最后加1进位

xxxxxxxxxx
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        // 右移并或运算
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

另外3个套娃构造方法，都调用了双参构造方法

xxxxxxxxxx
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

putVal

hashmap.put本质是putVal方法

xxxxxxxxxx
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

扰动函数

跟入hash方法，这里对key进行了扰动，得到是正是node中的hash属性

xxxxxxxxxx
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

右移16位让key的哈希值高16位和它本身进行异或运算（相同得0不同得1）

16位正好为32位的一半，自己的高半区和低半区做异或，为了混合原始哈希吗的高位和低位，来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，使高位的信息也被保留下来

总之：让哈希值更加散列，减少寻址时的哈希冲突

参考大佬表格

putVal方法

注意到传入两个bool

• onlyIfAbsent为true时，如果key存在不会修改value
• evict参数在Hashmap中无用，在LinkedHashMap中用到

xxxxxxxxxx
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
                       ...
                   }

具体分析

xxxxxxxxxx
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // tab 当前node数组，也就是hashMap散列表
        Node<K,V>[] tab;
        // p 当前散列表的node元素
        Node<K,V> p;
        // n 散列表数组长度
        // i 路由寻址算法的结果
        int n, i;

        // 延迟初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            // 第一次put时会扩容，具体在后文分析
            n = (tab = resize()).length;

        // 路由算法 (table.length-1)&node.hash
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 得到的桶位（node数组索引）正好是null那么直接new一个node
            tab[i] = newNode(hash, key, value, null);
        else {
            // 得到的桶位（node数组索引）可能是链表也可能是树

            // 找到与插入key相同的node
            Node<K,V> e;
            // 与插入key相同的node的key（临时变量）
            K k;

            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 插入node的key已存在，赋值e
                e = p;
            else if (p instanceof TreeNode)
                // 如果是树，插入树（暂不分析红黑树原理）
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 如果是链表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        // 尾部插入新node
                        p.next = newNode(hash, key, value, null);
                        // 超过阈值会树化
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 在链表中找到了key为node的元素，跳出进行替换
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 遍历链表
                    p = e;
                }
            }
            // e被赋值说明key已存在要进行替换
            if (e != null) {
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    // 满足条件后替换
                    e.value = value;
                // 暂时无用
                afterNodeAccess(e);
                // 返回旧值
                return oldValue;
            }
        }
        // 散列表结构被修改次数统计
        ++modCount;
        // 是否需要扩容
        if (++size > threshold)
            resize();
        // 暂时无用
        afterNodeInsertion(evict);
        return null;
    }

resize

如果node中元素链表或树包含node过多，也就是链化严重，这时候查询效率会过低

resize方法分两步：

• 计算新容量和新阈值
• 实现扩容

计算新容量和新阈值分析

xxxxxxxxxx
// 引用扩容前的node数组
Node<K,V>[] oldTab = table;
// 扩容前node数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 扩容前的扩容阈值
int oldThr = threshold;
// 扩容后的大小和新扩容阈值
int newCap, newThr = 0;

// 正常扩容
if (oldCap > 0) {
    // 很少达到扩容上线
    if (oldCap >= MAXIMUM_CAPACITY) {
        // 超出扩容上限以后不再进行扩容
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    // oldCap左移翻倍，赋值给newCap
    // oldCap大于默认第一次扩容阈值（16）才可以
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
        // 新阈值翻倍（*2）
        newThr = oldThr << 1; // double threshold
}
// oldCap等于0，进行初始化扩容
else if (oldThr > 0) // initial capacity was placed in threshold
    // 构造方法调用到tableSizeFor方法初始化了扩容阈值
    // new HashMap(initCap, loadFactor)
    // new HashMap(initCap)
    // new HashMap(map)
    newCap = oldThr;
else {               // zero initial threshold signifies using defaults
    // 初始化设置默认值
    // new HashMap()
    newCap = DEFAULT_INITIAL_CAPACITY;
    // 负载因子
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr为0时计算出一个非零newThr
if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                (int)ft : Integer.MAX_VALUE);
}
// 赋值
threshold = newThr;

实现扩容分析（参考图片）

xxxxxxxxxx
// new一个新的node数组用于扩容
@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节点
        Node<K,V> e;
        // 说明当前桶位存在数据，但不确认是单个或链表或树
        if ((e = oldTab[j]) != null) {
            // 置空方便JVM GC
            oldTab[j] = null;
            // 当前桶位只有1个元素没有碰撞过
            if (e.next == null)
                // 寻址算法确定新桶位
                newTab[e.hash & (newCap - 1)] = e;
            // 红黑树处理（暂不分析）
            else if (e instanceof TreeNode)
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            // 最重要：如何处理链表
            else {
                // 低位链表头尾
                Node<K,V> loHead = null, loTail = null;
                // 高位链表头尾
                Node<K,V> hiHead = null, hiTail = null;
                Node<K,V> next;
                do {
                    next = e.next;
                    // oldCap一定是2的倍数，二进制表示为00..00100..00
                    // 和hash与操作后除了某一位之外其他位一定是0
                    // oldCap这一位与操作结果只能是0或1
                    // 最终结果是0或1
                    if ((e.hash & oldCap) == 0) {
                        // 构造链表
                        if (loTail == null)
                            loHead = e;
                        else
                            loTail.next = e;
                        loTail = e;
                    }
                    else {
                        // 构造另一条链表
                        if (hiTail == null)
                            hiHead = e;
                        else
                            hiTail.next = e;
                        hiTail = e;
                    }
                } while ((e = next) != null);
                // 遍历完e，设置新桶低位
                if (loTail != null) {
                    loTail.next = null;
                    newTab[j] = loHead;
                }
                // 设置新桶高位
                if (hiTail != null) {
                    hiTail.next = null;
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }
}
return newTab;

get

get方法本质是getNode方法

xxxxxxxxxx
public V get(Object key) {
    Node<K,V> e;
    // put时候调用hash方法
    // get也应该调用一次
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode分析

xxxxxxxxxx
final Node<K,V> getNode(int hash, Object key) {
    // 引用当前散列表
    Node<K,V>[] tab;
    // 桶中的头元素和临时元素
    Node<K,V> first, e;
    // node数组长度
    int n;
    // 临时变量
    K k;
    // 确定存在数据
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 单个元素直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 不是单一元素
        if ((e = first.next) != null) {
            // 红黑树暂不分析
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 遍历链表拿到key相同的
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

remove

remove方法

xxxxxxxxxx
public V remove(Object key) {
    Node<K,V> e;
    // false表示不对value进行校验
    // true表示不移除其他node
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

跟入removeNode

xxxxxxxxxx
final Node<K,V> removeNode(int hash, Object key, Object value,
                            boolean matchValue, boolean movable) {
    // 当前散列表的引用
    Node<K,V>[] tab;
    // 当前node元素
    Node<K,V> p;
    // 散列表长度和寻址结果
    int n, index;
    // 散列表不为空并且p赋值为查找到的桶位
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        // 查找到的node结果
        Node<K,V> node = null, e;
        // 临时变量
        K k;
        V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 桶位元素唯一且恰好一致
            node = p;
        else if ((e = p.next) != null) {
            // 红黑树暂不分析
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 遍历链表
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                            (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 校验是否需要验证value相同后删除
        if (node != null && (!matchValue || (v = node.value) == value ||
                                (value != null && value.equals(v)))) {
            // 红黑树的remove暂不分析
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // 当前桶位元素唯一直接到next
                tab[index] = node.next;
            else
                // 删除链表中的某个节点
                p.next = node.next;
            // 操作数统计
            ++modCount;
            // 长度减少
            --size;
            // 暂时无用
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

replace

两个方法比较简单

xxxxxxxxxx
@Override
public boolean replace(K key, V oldValue, V newValue) {
    Node<K,V> e; V v;
    // 调用已分析过的getNode方法
    // 验证value是否一致
    if ((e = getNode(hash(key), key)) != null &&
        ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}

@Override
public V replace(K key, V value) {
    Node<K,V> e;
    // 调用已分析过的getNode方法
    // 不用验证直接替换
    if ((e = getNode(hash(key), key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}