HashMap源码总结（持续更新中）

我会带着你远行 2023-07-14 05:49 3阅读 0赞

1.  可以存放多少个数据：
    
        源码：MAXIMUM_CAPACITY = 1 << 30 2的29次方
2.  初始状态数组的大小：
    
        源码static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
        为什么是16呢，其实没有特别的含义。这个是一个经验数字，只要是2的倍数都行
3.  负载系数：
    
        final float loadFactor = DEFAULT_LOAD_FACTOR //0.74
        这个数字和泊松分布相关
    
        DEFAULT_LOAD_FACTOR
4.  put方法
    
        //常常被问到的问题：key = null的时候，hash(key)返回的是0，也就是说key= null的时候，node节点一定在0号链表的某个位置
         final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
                Node<K,V>[] tab; 
                Node<K,V> p; int n, i;
                //ps1 第一次put的时候，table为空，所以会初始化node数组
                if ((tab = table) == null || (n = tab.length) == 0)
                    n = (tab = resize()).length;
                //ps2 说明任何一个node在数组的哪个链表上面是使用自己key的hash来定位。发现这个角标没有链表，那么就他就是插入该位置的第一个node。直接二话不说插入就行了
                if ((p = tab[i = (n - 1) & hash]) == null)
                    tab[i] = newNode(hash, key, value, null);
                else {
                    //发现第一个位置里面有node值了，那么开始检查key是否存在
                    Node<K,V> e; K k;
                    //为什么要比较hash值？因为hash值比较的非常快，hash值是int类型
                    //只有hash值比较通过之后，再进行内存地址或者具体对象内容值比较
                    if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                        e = p;   //key值已经存在，那么在下面代码就会把value替换一次，不管有没有值变化
                    else if (p instanceof TreeNode)//转到树的逻辑处理
        //根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一，所以将7//作为一个分水岭，等于7的时候不转换，大于等于8的时候才进行转换，小于等于6的时候就化为链表。
                        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                    else {
                        //按照ps2 位置代码可知，当前要put的内容一定在这表链表上面，代码里面使用了：p 表示
                        //开始从数组上的这条链表上节点遍历
                        for (int binCount = 0; ; ++binCount) {
                            if ((e = p.next) == null) {
                                //到了链表的末尾了，没找到，那就新建一个
                                p.next = newNode(hash, key, value, null);
                                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;//对比链表上面的下一个，开始一个节点比对
                        }
                    }
                    if (e != null) { // existing mapping for key 不论如何，更新一下value值
                        V oldValue = e.value;
                        if (!onlyIfAbsent || oldValue == null)
                            e.value = value;
                        afterNodeAccess(e);
                        return oldValue;
                    }
                }
                ++modCount;
                if (++size > threshold)
                    resize();
                afterNodeInsertion(evict);
                return null;
            }
    
     
5.  jdk1.8 链表变成红黑树的两个条件：数组长度大于64（小于的时候会触发resize,resize之后单链长度会小于8），需要转换的链表的长度节点数量大于等于8。
6.  jdk1.8的触发扩容有两个事件：1.整个大小大于了阈值，2.在触发树化的时候，数组长度小于64.
7.  get方法

final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            //先判断key对应的链表存不存在
            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 {//普通链表，继续遍历该链表，直到最后链表末尾
                        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

6.resize方法

//jdk1.8和jdk1.7的有很大区别
    //jdk1.7只是简单的把old数组全部遍历，每条链条重新遍历，然后每个node重新计算在新数组中的位置。
    //jdk1.7扩容的时候，当老数据插入到新的数组中的时候，都是直接插入到链条的第一个位置，所以会出现链条翻转的情况
    //jdk1.8是一次性先放到一条链条上面，然后把链条放到数组上。jdk1.7是直接把数据放到对应数组链条的第一个位置
    final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length; //老数组的大小
            int oldThr = threshold;//老数组的扩容阈值，比如16*.075=12。如果调用的是new HashMap();那么threshold = 0；
            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)
                    //注意if里面进行了逻辑操作。这个就是普通扩容操作，新的长度是旧的2倍
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold ps1
                newCap = oldThr;
            else { // zero initial threshold signifies using defaults，new hashmap时候执行的逻辑
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
    
            if (newThr == 0) {
                //对于 ps1出代码，对新的数组阈值进行重新计算
                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 = newTab;
            if (oldTab != null) {
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        //遍历数组上面的每一条链条
                        oldTab[j] = null;//让gc回事内存
                        if (e.next == null)//如果该链条只有一个node,那么就直接定位了，然后存入新数组中
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof TreeNode)//如果该链条是二叉树
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // preserve order 开始重新定位
                            //下面定位有很多数学相关的知识；
                            //原理：2倍扩容之后，如果(e.hash & oldCap) == 0，说明该node在新的数组中，所处数组的脚标不会变化
                            //原理：2倍扩容之后，如果(e.hash & oldCap) ！= 0，说明该node在新数组中，它的角标一定在：老角标+老数组长度  这个位置
                            Node<K,V> loHead = null, loTail = null;//用来处理数组位置不会发生变化的node。loHead储存的是处理完成的数据，LoTail可以看成是临时变量
                            Node<K,V> hiHead = null, hiTail = null;//用来处理数组位置会发生变化的node。HiHead储存的是处理完成的数据，HiTail可以看成是临时变量
                            Node<K,V> next;
                            do {
                                next = e.next;
                                if ((e.hash & oldCap) == 0) {//数组位置不会变，下面代码有点抽象，需要好好理解。下面实现了：把符合条件的node依次链接到lohead的屁股后面，所以jdk1.8是“不会发生颠倒的，仅限于在新数组角标不变的情况下”。当doWhile结束的时候，loHead的屁股后面最后一个node.next是脏数据，要进行处理
                                    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);
                            //屁股后面的最后一个node的next是脏数据，如果不是脏数据，说明代码也就初问题了
                            if (loTail != null) {
                                //这里面是位置不会发生变化的node链条集合
                                loTail.next = null;//把链表放到数据里面
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) {
                                hiTail.next = null;
                                //这里面是位置发生了变化，变成了j+oldCap的链条集合。
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;

6.remove相关的方法

//调用remove的时候，参数中的value matchvalue movable一般是传入了默认的  
    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;
                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;
        }

jdk1.7在插入数据的时候，是直接把数据插入到链表的表头。jdk1.8之后是插入到链表的表尾。