JDK8HashMap源码

爱被打了一巴掌 2023-06-18 03:57 36阅读 0赞

> 进入这篇文章之前，我想清楚的说一说怎么去理解`HashMap`源码。它先是使用的`hash`算法，那么哈希算法需要注意的那就是怎么`hash`，怎么减少冲突，怎么避免冲突。然后是`Map`,`Map`是存储这些`<K,V>结构`的`Entity`，那么`HashMap`需要注意的就是`HashMap`的初始化过程，什么时候进行数组（桶）扩容等等

## 构造和初始化 ##

要深入了解`HashMap`就必须先了解它的这几个比较重要属性

//节点，就是Entity
        transient Node<K,V>[] table;
        //同来记录使用过的那些键值对
        transient Set<Map.Entry<K,V>> entrySet;
    
        //Map中k，v的对数
        transient int size;
        //threshold（threshold=capacity*loadFactor）是一个阈值，是触发resize的一个重要条件
        int threshold;
        //负载因子
        final float loadFactor;

`HashMap`有四种构造方法，如下代码

/*
    自定义初始容量和负载因子
    代码解释：
    先进行判断传进来的初始容量是否合法，如果初始化容量超出了最大容量范围，就将给它设置最大容量的值
    再判断负载因子是否合法，如果是合法的就将次负载因子正确的初始化。  threshold（threshold=capacity*loadFactor）是一个阈值，当HashMap的size大于这个阈值，就会进行 resize
    */
        //默认初始容量16  
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
       
        //最大容量是1<<30
        static final int MAXIMUM_CAPACITY = 1 << 30;
       
        //默认的负载因子
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        //树形化的阈值
        static final int TREEIFY_THRESHOLD = 8;
    
        //在剪枝的时候取消树形化的阈值
        static final int UNTREEIFY_THRESHOLD = 6;
    
        //最小树形化容量	
        static final int MIN_TREEIFY_CAPACITY = 64;
    
    
    public HashMap(int initialCapacity, float loadFactor) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;
            //tabelSizeFor(int cap)方法是为了对于一些不是2的幂次方的数求出大于initialCapacity的最小的2的幂次方数，然后赋值给threshold。值得注意的是，我看了看JDK8以前的代码，这块是没有这个tableSizeFor操作，而是直接将initialCapacity赋值给threshold。
            this.threshold = tableSizeFor(initialCapacity);
        }
    
      
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        /**
        默认容量16，负载因子0.75
         */
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
    
    
        public HashMap(Map<? extends K, ? extends V> m) {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);
        }

对于上面说到过的`tableSizeFor`方法，可以来看看是怎么实现的，很精致的一段代码

/*
         提出问题：
         1.为什么cap-1
         2.为什么要用五个移位或操作
         */
         /*
         解决问题：
         先说第二个问题
         以5为例，我们都知道一个int值是4个字节，也就是32为
         0101
         0010 -> 0111
                 0000 -> 0111 
                 .....
                 移位或的结果是0111（32为数前面的0此处省略）
                 
          因此我们可以看出来这些移位或运算都是为了使得最小的大于这个数的2的幂次方这个数的后面所有位都变为1，然后我们在n在合理范围内+1就可以得到我们想要得到的值了。
          
          现在来说第一个问题，为什么是cap-1呢。我们可以试图想一想，如果输入这个值本来就是2的幂次方，那么这么一系列操作之后我们会惊奇的发现，求出来的值会是我们想要求出的值的2倍。这就是为什么先对cap-1
          
         */
         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;
            //如果n<0，就返回1,n>=0，如果n>=最大容量，就返回最大容量，否则就返回n+1
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }
    
            /*输出
            tableSizeFor(5)=8
            tableSizeFor(8)=8
            tableSizeFor(9)=16
            */

测试

public static void main(String[] args) {
            System.out.println("tableSizeFor(5)="+tableSizeFor(5));
            System.out.println("tableSizeFor(8)="+tableSizeFor(8));
            System.out.println("tableSizeFor(9)="+tableSizeFor(9));
        }
        static final int MAXIMUM_CAPACITY = 1 << 30;
        static final int tableSizeFor(int n) {
            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;
        }
    
    
    正常情况
    tableSizeFor(5)=8
    tableSizeFor(8)=8
    tableSizeFor(9)=16
    
    注释掉cap-1并进行相应替换后的情况
    tableSizeFor(5)=8
    tableSizeFor(8)=16
    tableSizeFor(9)=16

## put方法 ##

说put前，肯定要先说说hash方法，在1.8中的hash和1.7中不同，比1.7中右移变少（也就是位扰动），有一部分是因为在1.8中加入了红黑树在同一index下，保证了查找效率，不会因为散列集中引起性能大幅度下降。

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

public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    
        //hash就是hash(k),onlyIfAbsent如果是true的话，就是如果key相同的话不进行覆盖，evict如果是false的话就表示初始化
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //1.判断当前hashtable是否为空，如果为空就进行初始化 resize方法既能用于初始化，又能用于扩容
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //2.根据（n-1）&hash得到index，判断index的位置是否为空（链表头或树根），如果是空就new一个Node并放到这个位置
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            //3.如果index这个位置不为空
            else {
                Node<K,V> e; K k;
                //p就是当前index下对应的Node节点
                //3-1.（如果当前桶放的是链表）如果p的key对应的值和准备要方进来的key的值是相同的，就把这个值（OldNode）记下来（记为e）
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                //3-2.（如果当前桶放的是树）如果是树节点，就调用putTreeVal，在下面会说
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                //3-3.如果不是覆盖操作，那就进行遍历链表（因为在3-2中已经排除了是树），找到链表最后的一个节点进行尾插，并用binCount记录当前正在遍历的链表此刻的长度。
                else {
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            //到达链表尾部的话就进行尾插
                            p.next = newNode(hash, key, value, null);
                            //如果binCount=7（TREEIFY_THRESHOLD-1）就说已经达到树形化的一个条件了（另一个条件是table.length>=MIN_TREEIFY_CAPACITY,默认为64），因为现在未加入新节点都已经是7了，因此肯定是会到达树化的阈值，因此会进入treeifyBin(tab, hash)方法。
                            if (binCount >= TREEIFY_THRESHOLD - 1) 
                                treeifyBin(tab, hash);
                            break;
                        }
                        //如果未到达尾部，就对hash值进行比对，如果hash值相同并且key也是相同的，那就说明找到要替换的节点（就可以break了）
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        
                        //没找到要替换的节点就替换以便于通过p访问下一个Node（循环要素）
                        p = e;
                    }
                }
                
                //如果e！=null就说明有需要替换的值（如果遍历到链表尾部，e=null）
                if (e != null) { 
                    //oldValue拿出来准备返回
                    V oldValue = e.value;
                    //onlyIfAbsent默认false（有相同就替换）或者以前的值是null就进行替换
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    //空方法
                    afterNodeAccess(e);
                    //返回被替换的值
                    return oldValue;
                }
            }
            
            //如果能执行到此处的话，说明是添加了一个节点而不是修改了一个节点，因此++modCount
            ++modCount;
            //对size值进行++操作，如果size>threshold，就要进行扩容
            if (++size > threshold)
                resize();
            //空方法
            afterNodeInsertion(evict);
            //不是更新进返回null
            return null;
        }

//new一个Node节点
       Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
            return new Node<>(hash, key, value, next);
        }
       //没有任何东西，这些空方法并且是afterxx都可作为回调方法
       void afterNodeAccess(Node<K,V> p) { }
       void afterNodeInsertion(boolean evict) { }

//给红黑树里添加Node
    final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                           int h, K k, V v) {
                Class<?> kc = null;
                boolean searched = false;
                //取树根，如果当前Node的parent！=null，说明不是根，需要循环找根。如果parent==null说明就是根
                TreeNode<K,V> root = (parent != null) ? root() : this;
                //从根开始遍历这棵树
                for (TreeNode<K,V> p = root;;) {
                    int dir, ph; K pk;
                    //根据哈希判断去左还是去右
                    if ((ph = p.hash) > h)
                        dir = -1;
                    else if (ph < h)
                        dir = 1;
                    //如果key相等就返回p，说明找到替换的节点了
                    else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                        return p;
                    //如果hash相等，但是key不相等
                    else if ((kc == null &&
                              (kc = comparableClassFor(k)) == null) ||
                             (dir = compareComparables(kc, k, pk)) == 0) {
                        if (!searched) {
                            TreeNode<K,V> q, ch;
                            searched = true;
                            //如果从当前hash相同的节点的子树中找到key相同的就返回
                            if (((ch = p.left) != null &&
                                 (q = ch.find(h, k, kc)) != null) ||
                                ((ch = p.right) != null &&
                                 (q = ch.find(h, k, kc)) != null))
                                return q;
                        }
                        //当哈希值相同并且不可比较
                        dir = tieBreakOrder(k, pk);
                    }
                    
                    //如果hash不相等，根据上边的dir进行选路
                    TreeNode<K,V> xp = p;
                    if ((p = (dir <= 0) ? p.left : p.right) == null) {
                        Node<K,V> xpn = xp.next;
                        TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                        if (dir <= 0)
                            xp.left = x;
                        else
                            xp.right = x;
                        xp.next = x;
                        x.parent = x.prev = xp;
                        if (xpn != null)
                            ((TreeNode<K,V>)xpn).prev = x;
                        
                        //插入后并且进行树的平衡
                        moveRootToFront(tab, balanceInsertion(root, x));
                        return null;
                    }
                }
            }

//循环找根
    final TreeNode<K,V> root() {
                for (TreeNode<K,V> r = this, p;;) {
                    if ((p = r.parent) == null)
                        return r;
                    r = p;
                }
            }

//如果table==null就进行初始化，table.length<MIN_TREEIFY_CAPACITY=64,就进行桶的扩容而不是进行树化
     final void treeifyBin(Node<K,V>[] tab, int hash) {
            int n, index; Node<K,V> e;
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                resize();
            //如果满足上面集合条件就遍历并进行树化
            else if ((e = tab[index = (n - 1) & hash]) != null) {
                TreeNode<K,V> hd = null, tl = null;
                do {
                    TreeNode<K,V> p = replacementTreeNode(e, null);
                    if (tl == null)
                        hd = p;
                    else {
                        p.prev = tl;
                        tl.next = p;
                    }
                    tl = p;
                } while ((e = e.next) != null);
                if ((tab[index] = hd) != null)
                    hd.treeify(tab);
            }
        }

## get方法 ##

//通过key进行查找
        public V get(Object key) {
            Node<K,V> e;
            //在传入getNode方法时先对key进行hash
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }
        
        final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            //如果table！=null，并且hash对应的桶的位置也要有值
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                //如果key可以被直接找到就返回
                if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                //如果first存在next
                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);
                }
            }
            //找不到就返回null
            return null;
        }

## remove方法 ##

//根据key移除
        public V remove(Object key) {
            Node<K,V> e;
            //传入hash，key，value=null，machValue=false，movable=true
            return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
        }
    
        //如果matchable=true，就表示表示只有key，value同时相等时才删除   movale如果为false就表示删除节点的时候不移动其他节点
        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;
            //如果table不为null并且次hash对应的数组节点上有值
            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);
                    }
                }
                //node！=null并通过传进来的matchValue来选择需不需要对value进行校验
                if (node != null && (!matchValue || (v = node.value) == value ||
                                     (value != null && value.equals(v)))) {
                    //如果是树节点，就调用removetreeNode
                    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
                    --size;
                    //空方法
                    afterNodeRemoval(node);
                    return node;
                }
            }
            //没找到就返回null
            return null;
        }

## resize方法 ##

final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;
            //如果oldTable为null，就为0，否则就是oldTable.length
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
            //如果不是空table
            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
            }
            //如果为空table但oldThr>0，那么初始容量就使用以前的阈值
            else if (oldThr > 0) 
                newCap = oldThr;
            //如果threshold并且threshold被默认赋值为0（也就是没有进行table的初始化），那么就进行table初始化
            else {               
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            //上一步对table初始化的时候并没有对threshold进行初始化，因此对它赋值
            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 = newTab;
            //对oldTab进行遍历并把值移动到newTab，一个桶一个桶的进行遍历
            if (oldTab != null) {
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;
                        if (e.next == null)
                            //使用e.hash对newCap-1进行与，而不是oldCap
                            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;
                                //判断e需不需要进行移动，因为容量变了，为了保证正确性（如果是小于oldCap的数，结果就会为0）
                                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);
                            //进行尾插（1.7是头插）
                            if (loTail != null) {
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            //需要移动的偏移量是oldCap
                            if (hiTail != null) {
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }

//树的修剪
    //index表示修剪的开始，bit代表修剪的位数
    final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
                TreeNode<K,V> b = this;
                // Relink into lo and hi lists, preserving order
                //减为两棵树
                TreeNode<K,V> loHead = null, loTail = null;
                TreeNode<K,V> hiHead = null, hiTail = null;
                int lc = 0, hc = 0;
                for (TreeNode<K,V> e = b, next; e != null; e = next) {
                    next = (TreeNode<K,V>)e.next;
                    e.next = null;
                    //如果e.hash & bit就放到LTree
                    if ((e.hash & bit) == 0) {
                        if ((e.prev = loTail) == null)
                            loHead = e;
                        else
                            loTail.next = e;
                        loTail = e;
                        ++lc;
                    }
                    //否则就放到HTree
                    else {
                        if ((e.prev = hiTail) == null)
                            hiHead = e;
                        else
                            hiTail.next = e;
                        hiTail = e;
                        ++hc;
                    }
                }
                //元素个数小于等于6就会还原为链表
                if (loHead != null) {
                    if (lc <= UNTREEIFY_THRESHOLD)
                        tab[index] = loHead.untreeify(map);
                    else {
                        tab[index] = loHead;
                        if (hiHead != null) // (else is already treeified)
                            loHead.treeify(tab);
                    }
                }
                //给index+bit（也就是原数组容量）就是HTree放的位置（也就是放在了修剪范围之外）
                if (hiHead != null) {
                    if (hc <= UNTREEIFY_THRESHOLD)
                        tab[index + bit] = hiHead.untreeify(map);
                    else {
                        tab[index + bit] = hiHead;
                        if (loHead != null)
                            hiHead.treeify(tab);
                    }
                }
            }

> 读到这，我相信HashMap里面比较难理解的代码都基本掌握了！