HashMap源码解读

本文主要是介绍HashMap源码解读，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

本文用于探索和学习HashMap源码，对HashMap的源码进行解读。

主要学习HashMap的插入和扩容思想。

1.基本概念

    HashMap在jdk1.8后对其内部数据结构进行了优化，从以前的 数组+链表 的结构改为 数组+链表+红黑树 的结构。

    在未发生哈希冲突时仅使用数组进行存储，但发生哈希冲突时，若key值不相同，则插入到冲突数组节点（HashMap的数组中存储数据为Node的节点，属于链表结构）的链表中，若链表长度大于8且数组的长度不小于64的时候通过 treeifyBin() 转化为红黑树提高查询效率。

2.存储方法put（）

先从存储方法put（）进行解读：

public V put(K key, V value) {
        //调用了putVal（）进行存储
        return putVal(hash(key), key, value, false, true);
    }

HashMap的存储方法put（）是通过调用putVal（）方法进行存储。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) 

其中一共传入了5个参数：

hash：使用hash方法计算key的哈希值

key：传入的key值

value：传入的value值

onlyIfAbsent：意义为当key值相同时，是否覆盖原有的key值。为true，不覆盖原有的key值；为false，key值相同时覆盖原有的key值。（默认为false）

evict：是否为创建模式，此处默认为true。

开始逐行解读代码：

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;​
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

​

 当我们调用putVal（）时：

第一个if（）先判断创建的HashMap对象是否初始化，若没有初始化则调用resize（）方法（resize方法 后文会进行解读）进行初始化扩容。

第二个if（）语句中，使用HashMap的长度与hash进行 &操作（HashMap插入的位置是无序的，仅根据hash值与长度n的&操作决定），判断该位置是否存在元素，若不存在则直接插入Node节点，若存在则说明发生了哈希冲突。（哈希冲突：不同的key进行哈希运算后得到相同的哈希值，代表发生了哈希冲突）

 else {
            Node<K,V> e; K k;
            //第一部分
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //第二部分
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //第三部分
            else {
                for (int binCount = 0; ; ++binCount) {
                    //第三部分A
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //第三部分B
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //第三部分C
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }

存储方法put（）的主要内容在于发生哈希冲突后的逻辑处理。

第一部分：判断发生哈希冲突的节点与插入节点的hash值、key值是否相同，若相同则插入节点覆盖原节点。

第二部分：判断发生哈希冲突的节点属于红黑树结构，如果为红黑树则直接插入到红黑树中

第三部分：当不属于前两种情况时，则需对该节点的链表进行操作，对当前节点的链表进行遍历。

              第三部分A：判断当前节点链表中是否还有后续节点，若没有则插入到链表尾部。

              第三部分B：判断链表长度是否 >= 8（因为binCount从0开始，所以TREEIFY_THRESHOLD需要减1），若大于等于8则调用treeifyBin（）将链表转化为红黑树的存储结构。

             第三部分C：但对当前节点的链表进行遍历时，发现其中节点的hash值、key值与插入节点相同，直接break结束遍历。

if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }

当 e != null 时，说明插入key值成功了，若 onlyIfAbsent 为false说明采用新值覆盖旧值的原则，或旧值为null时，新值覆盖旧值。afterNodeAccess（）用于LinkedHashMap。

        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;

modCount记录HashMap的修改次数。

因为插入了数据，所以size需要加1，此处if判断HashMap是否需要扩容，需要扩容则调用resize（）扩容方法。

afterNodeInsertion()也是用于LinkedHashMap中。

3.扩容方法resize（）

这篇关于HashMap源码解读的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！