HashMap源码阅读（二，关键方法理解）

约定不等于承诺〃 2021-09-24 16:28 437阅读 0赞

## HashMap(jdk1.8) ##

*  HashMap的初始化容量，当输入为25的时候，n等于24，转成二进制为1100，右移1位为0110，将1100与0110进行或("|")操作，得到1110。接下来右移两位得11，再进行或操作得1111，接下来操作n的值就不会变化了。最后返回的时候，返回n+1，也就是10000，十进制为32。按照这种逻辑得到2的n次幂的数，容量为int类型，int的范围内的所有数，经过方法的位运算都会产生2的N次幂，HashMap的容量总是2的n次幂，利于HashMap后续查找。

/** * 根据容量参数，返回一个2的n次幂的table长度。 */
     // 假如cap 5
    static final int tableSizeFor(int cap) { 
            // 减一这个操作，是为了后面加1（好像是句废话），经过位运算，得到所有位均为1，当加一的时候所有位进位，即最高位为1，低位全为0，这样为2的N次幂
            int n = cap - 1;
            // |= 右移一位，换为二进制运算，0101 |= 0010
            // 0101 原始数值
            // 0010 右移一位
            // 0111 得到结果
            n |= n >>> 1;
            // 0111
            // 0011
            // 0111
            //这里之后其实这个数都不会变了，整体方法就是把数转为二进制之后，从遇到第一个1，把低位全变成1，然后就得到了2的N次幂减一，return的时候加1得到的就是2的n次幂
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

get方法

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 &&
                (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) { 
                // 如果是已经变成红黑树了，就走getTreeNode
                    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;
        }

put方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) { 
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //table为null或者size为0，还没出初始化，调用resize方法，调整map大小（也包括初始化map）
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            // hash之后需要插入的位置无数据，存一个新的node
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else { 
            // 这里就是插入的是hash位置已经有数据，hash碰撞，在查找插入位置
                Node<K,V> e; K k;
                // 存在同样的key
                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) { 
                    // 没找到相同key，然后newNode，如果现在的binCount为7证明链表除了头节点已经有了七个，加上这个新的会有八个，这时候会链表转红黑树
                        if ((e = p.next) == null) { 
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                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;
                }
            }
            ++modCount;
            // 看size是否超过阈值，是否需要阔容
            if (++size > threshold)
                resize();
                //插入数据之后执行的操作
            afterNodeInsertion(evict);
            return null;
        }

初始化 - 扩容

/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */
        final Node<K,V>[] resize() { 
        	// 先留一个原table的引用
            Node<K,V>[] oldTab = table;
            // 看是否已经初始化
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            // 旧的容量
            int oldThr = threshold;
            // 新的容量 threshold=capacity*loadFactor threshold即map的容量达到多少之后需要阔容，capacity代表能装的最大数量
            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)
                         //阔容的阈值也扩大两倍
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
            // 进入此if证明创建map时用的带参构造：public HashMap(int initialCapacity)或 public HashMap(int initialCapacity, float loadFactor)
                //注：带参的构造中initialCapacity（初始容量值）不管是输入几都会通过 “this.threshold = tableSizeFor(initialCapacity);”此方法计算出接近initialCapacity参数的2^n来作为初始化容量（初始化容量==oldThr）
                newCap = oldThr;
            else {                // zero initial threshold signifies using defaults
            // 无参构造，默认的map
                newCap = DEFAULT_INITIAL_CAPACITY;
                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) { 
            //旧的table不为空，扩容之后需要转移数据
                for (int j = 0; j < oldCap; ++j) { 
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) { 
                        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;
                                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);
                            if (loTail != null) { 
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) { 
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }