HashMap源码解析(JDK8)

素颜马尾好姑娘i 2021-09-25 08:56 508阅读 0赞

### HashMap源码解析 ###

*   *  结构图
     *  常用变量
     *  内部类
     *  构造方法
     *  常见方法
     *   *  核心方法hash、resize、tableSizeFor等
         *  put
         *  get
         *  remove
     *  总结

## 结构图 ##

![hashmap][]

public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable { 
    	...
    }

## 常用变量 ##

// 序列号 ，序列化使用
    private static final long serialVersionUID = 362498820763181265L;
    // 默认的初始容量 1<<4 带符号左移 0001 ---> 10000 (2进制) = 16(10进制)
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // 最大容量 2的30次方
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 加载因子 例如：数组容量为8 当元素数量为6(8*0.75)时，则会触发扩容。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当某个桶节点(桶即为数组的每个格子)数量大于8时，会转换为红黑树。
    static final int TREEIFY_THRESHOLD = 8;
    //当某个桶节点数量小于6时，会转换为链表，前提是它当前是红黑树结构。
    static final int UNTREEIFY_THRESHOLD = 6;
    // 整个hashMap中元素数量大于64时，也会进行转为红黑树结构
    static final int MIN_TREEIFY_CAPACITY = 64;
    // hashmap底层存储数据结构 --数组 transient关键字表示该属性不能被序列化
    transient Node<K,V>[] table;
    // 将数据转换成set的另一种存储形式
    transient Set<Map.Entry<K,V>> entrySet;
    // 元素数量
    transient int size;
    // 统计该map修改的次数
    transient int modCount;
    // 临界值，也就是元素数量达到临界值时，会进行扩容 (LOAD_FACTOR * INITIAL_CAPACITY)
    int threshold;
    // 同加载因子
    final float loadFactor;

## 内部类 ##

static class Node<K,V> implements Map.Entry<K,V> { 
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    
        Node(int hash, K key, V value, Node<K,V> next) { 
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    
        public final K getKey()        {  return key; }
        public final V getValue()      {  return value; }
        public final String toString() {  return key + "=" + value; }
    
        public final int hashCode() { 
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
    
        public final V setValue(V newValue) { 
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
    
        public final boolean equals(Object o) { 
            if (o == this)
                return true;
            if (o instanceof Map.Entry) { 
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }
    
    // 树节点 注意继承了 LinkedHashMap的Entry，LinkedHashMap的Entry继承了HashMap的Node
    // 说明树节点本身也是一种双向链表
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) { 
            super(hash, key, val, next);
        }
    	...// 省略树的相关方法
    }

## 构造方法 ##

public HashMap() { 
    	// 加载因子 = 默认加载因子 = 0.75f
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    // 给定一个默认容量
    public HashMap(int initialCapacity) { 
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    // 自定义 容量 以及 加载因子
    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;
        // 注意：tableSizeFor 一个必问必知的方法,在下面核心方法中讲解。
        // 返回给定容量的最大2次幂；例如 initialCapacity = 6 返回 8(2的3次方)；initialCapacity = 12 返回 16(2的4次方)
        this.threshold = tableSizeFor(initialCapacity);
    }
    
     public HashMap(Map<? extends K, ? extends V> m) { 
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        // 见下
        putMapEntries(m, false);
    }
    
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 
    	// 获取元素个数
        int s = m.size();
        if (s > 0) { 
        	// 如果 hashmap 还未初始化
            if (table == null) {  // pre-size
            	// +1 是为了除不尽的情况 
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                	// 计算扩容阈值
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

## 常见方法 ##

### 核心方法hash、resize、tableSizeFor等 ###

// hash算法
    static final int hash(Object key) { 
        int h;
        // ^:异或运算; >>>:无符号右移
        // 1^1=0; 1^0=1; 0^1=1; 0^0=0
        // 这里又是异或又是位运算，理由呢。可以参照这个大神的解答：https://www.zhihu.com/question/20733617
        // 简单来说：这段代码叫“扰动函数”，目的就是为了混合原始hash的高位与低位，以此来增加低位的随机性；减少hash冲突
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    
    // ***** 计算扩容因子 *****
    // >>>:无符号右移,a>>>b a向右移动b位，高位用0补，低位舍弃 
    // |:或运算 有1必为1。 |= ---> a=a|b
    // 假设入参为6 6-1=5 转换成2进制即为 0101
    // 0101 >>> 1 ---> 0010
    // 0101 | 0010 ---> 0111
    // 0111 >>> 2 ---> 000111
    // 0111 | 000111 ---> 000111
    // 同理...
    // 最后 n+1 = 0111 + 1 = 1000 (8)
    static final int tableSizeFor(int cap) { 
    	// 这里-1就是为了防止 cap 本来就是2次幂。
        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;
    }
    
    // ***** 扩容 *****
    final Node<K,V>[] resize() { 
    	// 底层数组
        Node<K,V>[] oldTab = table;
        // 底层数组的长度（不是元素数量）
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 扩容因子 threshold = capacity*loadFactor 
        int oldThr = threshold;
        int newCap, newThr = 0;
        // 如果长度不为0 也就是说 不是首次加载 hashmap在put时添加数据（懒加载）
        if (oldCap > 0) { 
        	// 如果数组长度大于等于最大容量
            if (oldCap >= MAXIMUM_CAPACITY) { 
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 如果 原长度*2 < 最大容量 且 原长度 >= 16 那么就扩容两倍且把扩容因子*2 注意点1
            // newCap = oldCap * 2 新长度为旧长度的2倍 ***********
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
            		 // DEFAULT_INITIAL_CAPACITY = 1<<4 = 16
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 扩容因子 * 2
                newThr = oldThr << 1; 
        }
        // 如果oldCap<=0，且oldThr>0 说明已经初始化了，例如把元素删除完之后的情况，那么它的临界值肯定还存在;如果是首次初始化，它的临界值则为0
        // 如果不是首次初始化
        else if (oldThr > 0) 
        	// 这种情况下，数组容量=old扩容阈值
            newCap = oldThr;
        else {  // 如果是首次初始化 
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 这里是对 注意点1 的完善，如果注意点1的条件不满足 那么newThr还是未赋值的状态。
        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;
        if (oldTab != null) { 
        	// 遍历旧数组
            for (int j = 0; j < oldCap; ++j) { 
                Node<K,V> e;
                if ((e = oldTab[j]) != null) { 
                	// 设为null 方便GC回收。
                    oldTab[j] = null;
                    if (e.next == null)
                    	// 下标计算 e.hash & (newCap - 1)
                    	// 如果下一个节点为null，重新计算新的节点位置 并把节点放入新的位置
                    	// newCap为2次幂 所以-1 低位全是1 所以位置信息由e.hash决定。
                        newTab[e.hash & (newCap - 1)] = e;	
                    else if (e instanceof TreeNode) 	//红黑树操作
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {  // 链表 resize最重要的操作之一就是对链表的拆分；
                    	// 可以去看看其他博主写的文章：https://blog.csdn.net/weixin_41565013/article/details/93190786
                    	// 链表1
                        Node<K,V> loHead = null, loTail = null;
                        // 链表2
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        // 这里注意：新的位置 = 【原位置】 或 【原位置 + 原数组长度】
                        do { 
                            next = e.next;
                            // oldCap 为 2次幂 低位全为0 高位为1
                            // 所以 (e.hash & oldCap) 只能等于 1 或 0，这里把0,1分成了两个链表
                            // 如果 等于 0
                            if ((e.hash & oldCap) == 0) { 
                            	// 如果尾节点为null
                                if (loTail == null)
                                    loHead = e;
                                else
                                	// 链表尾添加
                                    loTail.next = e;
                                loTail = e;
                            }
                            else { 	// (e.hash & oldCap) = 1
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) { 
                            loTail.next = null;
                            // 把链表头指向数组[j]
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) { 
                            hiTail.next = null;
                            // 把链表头指向 newTab[原下标+原数组长度]
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

### put ###

public V put(K key, V value) { 
        return putVal(hash(key), key, value, false, true);
    }
    
    // onlyIfAbsent：如果当前位置已存在一个值，是否替换，false是替换，true是不替换
    // 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;
        // 如果table未初始化或为空 则扩容
        if ((tab = table) == null || (n = tab.length) == 0)
        	// 扩容方法 resize(),详情见上resize()解析
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)	// n-1 必为低位全为1 
        	// 如果这个下标下没有数据，那么就赋值。
            tab[i] = newNode(hash, key, value, null);
        else { 
        	// 如果该下标 已有节点
            Node<K,V> e; K k;
    		
    		// 这里分三种情况
    		// 1. 如果hash 且 key相等，则直接替换旧值
    		// 2. 如果是红黑树，则调用红黑树的put方法
    		// 3. 如果是链表，使用尾插法。接着判断是否达到转树的条件，如果达到条件，那么就转成红黑树
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            	// 如果hash 相等 key也相等 那么就是同一个对象。
                e = p;
            else if (p instanceof TreeNode)
            	// 如果是红黑树，则调用红黑树的方法。
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else { // 否则就是链表操作
                for (int binCount = 0; ; ++binCount) { 
                	// 如果没有下一个节点
                    if ((e = p.next) == null) { 
                    	// 创建节点 放到链表最后(尾插法)
                        p.next = newNode(hash, key, value, null);
                        //static final int TREEIFY_THRESHOLD =8; 当链表长度大于8则会转成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1)//-1 for 1st:-1是为了第一次循环
                        	// 转成红黑树结构
                            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
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    
    // 转成树
    final void treeifyBin(Node<K,V>[] tab, int hash) { 
        int n, index; Node<K,V> e;
        // 如果数组长度<64 就去扩容；如果长度大于>=64；转成红黑树
        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);
        }
    }
    
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { 
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }
    
    final void treeify(Node<K,V>[] tab) { 
        TreeNode<K,V> root = null;
        for (TreeNode<K,V> x = this, next; x != null; x = next) { 
        	// 初始化
            next = (TreeNode<K,V>)x.next;
            x.left = x.right = null;
            // 如果根节点为null
            if (root == null) { 
                x.parent = null; // 父节点为null
                x.red = false; // 置为黑色
                root = x;	// 则把x（当前节点）设为根节点
            } else { 	// 如果已存在根节点
                K k = x.key;	// 当前节点的key
                int h = x.hash; // 当前节点的hash
                Class<?> kc = null; // key的class
                for (TreeNode<K,V> p = root;;) { 
                    int dir, ph;
                    K pk = p.key;
                    // 如果p(根节点)的hash值 > 当前节点的hash值
                    if ((ph = p.hash) > h)
                    	// 放到左侧的标记
                        dir = -1;
                    else if (ph < h)
                    	// 否则放到右侧
                        dir = 1;
    				// 如果hash值还是相等，那么就需要其他方法进行比较
    				// 如果当前链表节点的key实现了comparable接口，并且当前树节点和链表节点是相同Class的实例，那么通过comparable的方式再比较两者
                    else if ((kc == null &&
                              (kc = comparableClassFor(k)) == null) ||
                             (dir = compareComparables(kc, k, pk)) == 0)
                        dir = tieBreakOrder(k, pk);
    
    				/* * 如果dir小于等于0 ：当前链表节点一定放置在当前树节点的左侧，但不一定是该树节点的左孩子，也可能是左孩子的右孩子 或者 更深层次的节点。 * 如果dir大于0 ：当前链表节点一定放置在当前树节点的右侧，但不一定是该树节点的右孩子，也可能是右孩子的左孩子 或者 更深层次的节点。 * 如果当前树节点不是叶子节点，那么最终会以当前树节点的左孩子或者右孩子 为 起始节点 再进行下一个循环 重新寻找自己（当前链表节点）的位置 * 如果当前树节点就是叶子节点，那么根据dir的值，就可以把当前链表节点挂载到当前树节点的左或者右侧了。 * 挂载之后,还需要重新把树进行平衡。平衡之后,就可以针对下一个链表节点进行处理了。 */
                    TreeNode<K,V> xp = p;
                    if ((p = (dir <= 0) ? p.left : p.right) == null) { 
                        x.parent = xp;
                        if (dir <= 0)
                            xp.left = x;
                        else
                            xp.right = x;
                        root = balanceInsertion(root, x);
                        break;
                    }
                }
            }
        }
        moveRootToFront(tab, root);
    }

### get ###

public V get(Object key) { 
        Node<K,V> e;
        // 核心是getNode方法
        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;
        if ((tab = table) != null // table不为null
        	&& (n = tab.length) > 0 // 长度>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;
            // 如果第一个节点的next节点不为null
            if ((e = first.next) != null) { 
            	// 如果是红黑树结构
                if (first instanceof TreeNode)
                	// 使用树的方法
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // while 循环，如果key已经相等，就说明找到了；就返回。
                do { 
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
    
    final TreeNode<K,V> getTreeNode(int h, Object k) { 
    	// 获取根节点调用 find() 方法
        return ((parent != null) ? root() : this).find(h, k, null);
    }
    // 获取红黑树的根节点
    final TreeNode<K,V> root() { 
    	for (TreeNode<K,V> r = this, p;;) { 	
    		// 如果没有父节点，那么当前节点就是根节点。
    	    if ((p = r.parent) == null)
    	        return r;
    	    r = p;
    	}
    }
    
    // 红黑树的查询算法
    // kc:k的Class对象，该Class应该是实现了Comparable<K>的，否则应该是null
    final TreeNode<K,V> find(int h, Object k, Class<?> kc) { 
        TreeNode<K,V> p = this;
        do { 
            int ph, dir; K pk;
            // pl:左子树节点；pr:右子树节点
            TreeNode<K,V> pl = p.left, pr = p.right, q;
            // 比较根节点的hash跟 需要查询的节点的hash值
            // 如果根节点的hash比需查询节点的hash值大，那么就往左子树查询。
            if ((ph = p.hash) > h)
                p = pl;
            else if (ph < h)
                p = pr;
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))	// 如果hash相等且key相等，直接放回当前节点即可。
                return p;
            else if (pl == null)	// 如果左子树为null，那么转到右子树
                p = pr;
            else if (pr == null)	// 如果右子树为null,那么转到左子树
                p = pl;
            else if ((kc != null ||
                      (kc = comparableClassFor(k)) != null) &&
                     (dir = compareComparables(kc, k, pk)) != 0)
                p = (dir < 0) ? pl : pr; //dir小于0，p指向右孩子，否则指向右孩子。紧接着就是下一轮循环了
            // 执行到这里说明无法通过comparable比较 或者 比较之后还是相等
            // 从右孩子节点递归循环查找，如果找到了匹配的则返回
            else if ((q = pr.find(h, k, kc)) != null)
                return q;
            else
                p = pl;
        } while (p != null);
        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;
    }
    
    /** * Implements Map.remove and related methods. * * @param hash: hash for key (key的hash) * @param key: the key * @param value: the value to match if matchValue, else ignored 如果是matchValue，则匹配值，否则忽略 * @param matchValue: if true only remove if value is equal 如果为true，只在value相等时移除 * @param movable: if false do not move other nodes while removing 如果为false，则在移除时不要移动其他节点 * @return the node, or null if none */
    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;
        // 如果数组不为null 长度大于0 且根据key得到的数组下标中有值。
        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;
            // 如果key相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;	
            else if ((e = p.next) != null) { 	// 如果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)))) { 
                             // 如果key一致，则跳出循环，并拿到node节点。
                            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)	// 如果链表头==需要删除的节点
                	// 那么直接让node节点的next节点指向数组当前位置
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

## 总结 ##

HashMap中最重要的几点：

*  底层结构 数组+链表+红黑树
 *  几个关键的数字：16(默认容量) 0.75f(默认扩容因子) 12(16\*0.75 默认扩容阈值) 6(当链表长度小于6时，转成链表) 8(当链表长度大于8时，转成红黑树) 64(当底层数组容量大于64时，转成红黑树)
 *  扩容方法resize()
 *  扩容阈值计算方法
 *  put方法
 *  remove方法
 *  对于红黑树的理解(加分)

[hashmap]: /images/20210923/d7ee1119b5b74494bebe7cd12b553f0b.png