HashMap源码解析(JDK8)-蒲公英云

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方法
对于红黑树的理解(加分)