jdk源码解析二之HashMap

深藏阁楼爱情的钟 2023-02-22 05:12 38阅读 0赞

### 这里写自定义目录标题 ###

*   *  HashMap
     *   *  put
         *  remove
         *  replace
         *  get
         *  扩容resize
         *  迭代器
         *  总结
         *   *  什么时候采用红黑树?
             *  为什么每次扩容后,是2的幂次方?
             *  为什么扩容后,相同的在原位置保存,而不同的则当前索引+之前原位置索引保存?
             *  为啥用尾插法?
             *  为什么线程不安全?

## HashMap ##

[HashMap的loadFactor为什么是0.75？][HashMap_loadFactor_0.75]  
主要涉及到泊松分布的概念,猝!!!

一个bucket空和非空的概率为0.5，通过牛顿二项式等数学计算，得到这个loadfactor的值为log（2），约等于0.693. 同回答者所说，可能小于0.75 大于等于log（2）的factor都能提供更好的性能，0.75这个数说不定是 pulled out of a hat。

### put ###

public V put(K key, V value) {
        
            return putVal(hash(key), key, value, false, true);
        }
    
        static final int hash(Object key) {
        
            int h;
            //当key为null,默认存在0索引线性表
            //（因为hashCode是一个int类型的变量，是4字节，32位，所以这里会将hashCode的低16位与高16位进行一个异或运算，来保留高位的特征，以便于得到的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;
            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);
            else {
        
                //桶占用的处理
                Node<K, V> e;
                K k;
                //如果key相等,且不为null
                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 {
        
                    //链表处理
                    //先存A,在存B,接着存C，则数组存的是A,A.next=B,B.next=C,C.next=null
                    for (int binCount = 0; ; ++binCount) {
        
                        if ((e = p.next) == null) {
        
                            p.next = newNode(hash, key, value, null);
                            //链表个数>8则,转成红黑树
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        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;
                }
            }
            //记录修改次数
            ++modCount;
            //超过限制容量,扩容
            if (++size > threshold)
                resize();
            //空操作
            afterNodeInsertion(evict);
            return null;
        }

### remove ###

public V remove(Object key) {
        
            Node<K, V> e;
            return (e = removeNode(hash(key), key, null, false, true)) == null ?
                    null : e.value;
        }
    
      final Node<K, V> removeNode(int hash, Object key, Object value,
                                    boolean matchValue, boolean movable) {
        
            Node<K, V>[] tab;
            Node<K, V> p;
            int n, index;
            //非空判断
            if ((tab = table) != null && (n = tab.length) > 0 &&
                    //匹配
                    (p = tab[index = (n - 1) & hash]) != null) {
        
                Node<K, V> node = null, e;
                K k;
                V v;
                //第一个node的处理
                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);
                    }
                }
                if (node != null && (!matchValue || (v = node.value) == value ||
                        (value != null && value.equals(v)))) {
        
                    //红黑树处理
                    if (node instanceof TreeNode)
                        ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
                    //第一个节点的处理
                    else if (node == p)
                        tab[index] = node.next;
                    //其他节点的处理
                    else
                        p.next = node.next;
                    ++modCount;
                    --size;
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }

### replace ###

@Override
        public V replace(K key, V value) {
        
            Node<K, V> e;
            if ((e = getNode(hash(key), key)) != null) {
        
                V oldValue = e.value;
                e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
            return null;
        }
    
     final Node<K, V> getNode(int hash, Object key) {
        
            Node<K, V>[] tab;
            Node<K, V> first, e;
            int n;
            K k;
            //非空判断
            if ((tab = table) != null && (n = tab.length) > 0 &&
                    //根据hash映射数组
                    (first = tab[(n - 1) & hash]) != null) {
        
                //如果是first,则直接返回
                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 {
        
                        if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

### get ###

public V get(Object key) {
        
            Node<K, V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }

### 扩容resize ###

final Node<K, V>[] resize() {
        
            Node<K, V>[] oldTab = table;
            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;
                } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                        oldCap >= DEFAULT_INITIAL_CAPACITY)
                    //如果扩容后的大小<MAXIMUM_CAPACITY且不是第一次初始化容量,则扩充一倍Thr
                    newThr = oldThr << 1; // double threshold
            } else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
            else {
                       // zero initial threshold signifies using defaults
                //默认16容量
                newCap = DEFAULT_INITIAL_CAPACITY;
                //默认12,超过12限制容量,则重新扩容
                newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
        
                float ft = (float) newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                        (int) ft : Integer.MAX_VALUE);
            }
            threshold = newThr;
            @SuppressWarnings({
        "rawtypes", "unchecked"})
                    //临时存储扩容后的值
            Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
            //在整个扩容节点,table为空
            table = newTab;
    
            //以下执行扩容操作
            if (oldTab != null) {
        
                for (int j = 0; j < oldCap; ++j) {
        
                    Node<K, V> e;
                    if ((e = oldTab[j]) != null) {
        
                        //提前释放GC
                        oldTab[j] = null;
                        //对只有一个节点的处理
                        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 {
         // preserve order
                            //对数组链表下有很多节点的处理
                            Node<K, V> loHead = null, loTail = null;
                            Node<K, V> hiHead = null, hiTail = null;
                            Node<K, V> next;
                            do {
        
                                next = e.next;
                                //注意,此种情况为0,说明hash<当前容量,哪怕扩容后,进行&操作也是一样的索引值
                                //扩容后,按照之前的数组索引原位保存就行了
                                //尾部插入
                                if ((e.hash & oldCap) == 0) {
        
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                } else {
        
                                    //这种情况,说明扩容后的hasn进行&操作时,索引落在扩容的那一半部分
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            //为什么扩容后,相同的在原位置保存,而不同的则当前索引+之前原位置索引保存?
                            //因为这里的扩容都是扩容一倍,也就是01000扩容后变成10000
                            // 当e.hash & oldCap == 0,说明hash<当前容量,也就是落在0~1000范围内,哪怕扩容后,进行&操作也是一样的索引值
                            //!=0,则说明第一e.hash落在0~1000范围内,第二包含1000这个位置.而1000是之前扩容前的容量,所以最新的地址为扩容前容量+当前索引
                            //原位置保存
                            if (loTail != null) {
        
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            //存储索引在扩容的那部分
                            if (hiTail != null) {
        
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }

### 迭代器 ###

final Node<K, V> nextNode() {
        
                Node<K, V>[] t;
                Node<K, V> e = next;
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                if (e == null)
                    throw new NoSuchElementException();
                //遍历当前entry的下一个节点,如果没有则遍历数组,查找下一个链表节点
                if ((next = (current = e).next) == null && (t = table) != null) {
        
                    do {
        
                    } while (index < t.length && (next = t[index++]) == null);
                }
                return e;
            }

### 总结 ###

JDK8中,改变了底层数据结构,为线性表+链表+红黑树  
产生hash值碰撞后,用链表存储碰撞的值

#### 什么时候采用红黑树? ####

当桶里面存的链表个数>8,同时数组长度>64,的时候采用红黑树  
![在这里插入图片描述][20200525094114609.png]  
![在这里插入图片描述][20200626160051666.png]  
默认加载因子0.75  
![在这里插入图片描述][20200525094222567.png]  
默认容量16,加载扩容的大小12  
![在这里插入图片描述][20200525094354259.png]  
key一样时,覆盖旧的value  
可以存null,索引0

#### 为什么每次扩容后,是2的幂次方? ####

是因为在使用2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。  
只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。  
这是为了实现均匀分布。

![在这里插入图片描述][20200525094827271.png]

#### 为什么扩容后,相同的在原位置保存,而不同的则当前索引+之前原位置索引保存? ####

//因为这里的扩容都是扩容一倍,也就是01000扩容后变成10000
    // 当e.hash & oldCap == 0,说明hash<当前容量,也就是落在0~1000范围内,哪怕扩容后,进行&操作也是一样的索引值
    //!=0,则说明第一e.hash落在0~1000范围内,第二包含1000这个位置.而1000是之前扩容前的容量,所以最新的地址为扩容前容量+当前索引
                            //原位置保存
                            if (loTail != null) {
        
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            //存储索引在扩容的那部分
                            if (hiTail != null) {
        
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }

#### 为啥用尾插法? ####

[jdk7因为头插法存在环形问题][jdk7]  
而jdk8,使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了

#### 为什么线程不安全? ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70]  
在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。

在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。

[HashMap_loadFactor_0.75]: https://www.jianshu.com/p/64f6de3ffcc1
[20200525094114609.png]: https://img-blog.csdnimg.cn/20200525094114609.png
[20200626160051666.png]: https://img-blog.csdnimg.cn/20200626160051666.png
[20200525094222567.png]: https://img-blog.csdnimg.cn/20200525094222567.png
[20200525094354259.png]: https://img-blog.csdnimg.cn/20200525094354259.png
[20200525094827271.png]: https://img-blog.csdnimg.cn/20200525094827271.png
[jdk7]: https://mp.weixin.qq.com/s/VtIpj-uuxFj5Bf6TmTJMTw
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200626165557542.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw==,size_16,color_FFFFFF,t_70