HashMap

JDK1.8

一、关键字段

//创建 HashMap 时未指定初始容量情况下的默认容量   
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

//HashMap 的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

//HashMap 默认的装载因子,当 HashMap 中元素数量超过 容量*装载因子 时，进行　resize()　操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//用来确定何时将解决 hash 冲突的链表转变为红黑树
static final int TREEIFY_THRESHOLD = 8;

// 用来确定何时将解决 hash 冲突的红黑树转变为链表
static final int UNTREEIFY_THRESHOLD = 6;

/* 当需要将解决 hash 冲突的链表转变为红黑树时，需要判断下此时数组容量，若是由于数组容量太小（小于　MIN_TREEIFY_CAPACITY　）导致的 hash 冲突太多，则不进行链表转变为红黑树操作，转为利用　resize() 函数对　hashMap 扩容　*/
static final int MIN_TREEIFY_CAPACITY = 64;

//保存Node<K,V>节点的数组
 transient Node<K,V>[] table;

//由　hashMap 中 Node<K,V>　节点构成的 set
transient Set<Map.Entry<K,V>> entrySet;

//记录 hashMap 当前存储的元素的数量
transient int size;

//记录　hashMap 发生结构性变化的次数（注意　value 的覆盖不属于结构性变化）
transient int modCount;

//threshold的值应等于 table.length * loadFactor, size 超过这个值时进行　resize()扩容
int threshold;

//记录 hashMap 装载因子
final float loadFactor;

二、算法特点

1.容量初始化

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;
    this.threshold = tableSizeFor(initialCapacity);
}

threshold 为阈值。1.7版本直接取 initialCapacity ，1.8做了运算，查看 tableSizeFor 方法

/**
 * 找到大于或等于 cap 的最小2的幂
 */
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;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

假设个数带入计算一下可以发现，其实就是将 cap 二进制的各位都转化为1，在最后返回前加上1，保证是2的幂

int n = cap - 1的作用是为了避免 cap 本来就是2的幂的情况，导致在 cap 的基础上又乘了次2

int 是32位，n 右移十六位后作或运算，正好将最高位以后的所有位都转化为了1，再右移32位（结果为0）作或运算就没有意义了

2.键在桶中位置

// 计算键的哈希值在哈希表（桶数组）中的位置
key.hash & (table.length-1)

等价于对桶数组长度取余

HashMap 中桶数组的长度 length 总是2的幂，这样在计算位置中，table.length-1的结果，二进制形式上各位都为1，在与 hash的&运算时，增加了结果的可能性，减少了哈希碰撞几率，让元素能够更均匀的分布在桶数组上。

3.哈希转换

/**
 * 计算键的 hash 值
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

看这个方法的逻辑好像是通过位运算重新计算 hash，那么这里为什么要这样做呢？为什么不直接用键的 hashCode 方法产生的 hash 呢？

当哈希表容量不大时，单纯利用 hashCode 和容量进行 & 运算，hashCode 只有低位参与了计算。这样导致了计算结果只与低位信息有关，高位数据没发挥作用。

hashCode 方法产生的 hash 是 int 类型，32 位宽，前16位为高位，后16位为低位。

像上图中，让高位数据与低位数据进行异或，变相的让高位数据参与到计算中，以此加大低位信息的随机性。

除此之外，重新计算 hash 的另一个好处是可以增加 hash 的复杂度。当我们覆写 hashCode 方法时，可能会写出分布性不佳的 hashCode 方法，进而导致 hash 的冲突率比较高。通过移位和异或运算，可以让 hash 变得更复杂，进而影响 hash 的分布性。这也就是为什么 HashMap 不直接使用键对象原始 hash 的原因了。

4.扩容后重新计算在桶中位置

    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;
    }

resize 扩容方法中的一段，当旧的表中有元素或链表，且链表还未转化为红黑树，对新表进行重新映射的实现

e.hash & oldCap - 1是对表容量取模，计算key在表中位置

注意e.hash & oldCap此运算，因为表容量一直为2的幂，所以 oldCap 的二进制形式除最高位以外，其余低位都为 0

与键的哈希值作 & 运算，可以判断键对应位上的值是1还是0

当为1时，e.hash & newCap - 1计算下的新位置，是原位置加上 oldCap 的值

当为0时，依旧为原位置，不发生变化

可以假设值带入验证。这样将原链表分为了两组，每组都用一个 Head 和 Tail 引用，形成两条链表，引用在新表上

三、构造

//构造方法１，指定初始容量及装载因子
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(initialCapacity)　方法返回的值是最接近 initialCapacity 的2的幂
    //注意此种方法创建的 hashMap 初始容量的值存在　threshold 中
    this.threshold = tableSizeFor(initialCapacity);
}

//构造方法２，仅指定初始容量，装载因子的值采用默认的　0.75
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造方法３，所有参数均采用默认值
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

四、插入

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // 初始化表
    if ((tab = table) == null || (n = tab.length) == 0)
        ...
        
    // 表对应位置为null，直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        ...
    // 表位置上已存在元素
    else {
        // 已存在，且在第一个位置上的情况
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            ···
        // 已树化的情况
        else if (p instanceof TreeNode)
            ···
        // 仍是链表的情况
        else {
            for (int binCount = 0; ; ++binCount) {
                // 没有此元素，开始插入
                if ((e = p.next) == null) {
                    ...
                    // 链表数已大于树化阈值，插入后开始树化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    ···
                }
                // 链表中存在的情况
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    ...
                ...
            }
        }
        // 如果存在就进行替换
        if (e != null) { // existing mapping for key
           ...
        }
    }
    // 大于扩容阈值，开始扩容
    if (++size > threshold)
        ...
    return null;
}

• 必要的话初始化表
• 对应表中位置为null直接插入，不是null分情况讨论
• 根据树化、链化不同，实现不同；链化时超过了树化阈值进行树化
• 如果链表中或者树中已存在key，进行替换
• 最后再判断元素个数是否大于表阈值进行扩容

//读懂这个函数要注意理解 hash 冲突发生的几种情况
//１、两节点　key 值相同（hash值一定相同），导致冲突
//２、两节点　key 值不同，由于 hash 函数的局限性导致hash 值相同，冲突
//３、两节点　key 值不同，hash 值不同，但 hash 值对数组长度取模后相同，冲突
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;
    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;　//　dir小于０，接下来查找当前节点左孩子
        else if (ph < h)
            dir = 1;　//　dir大于０，接下来查找当前节点右孩子
        else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
            //进入这个else if 代表　hash 值相同，key　相同
            return p;
        /*要进入下面这个else if,代表有以下几个含义:
        1、当前节点与待插入节点　key　不同,　hash 值相同
    　　 2、ｋ是不可比较的，即ｋ并未实现　comparable<K>　接口
    　　 （若 k 实现了comparable<K>　接口，comparableClassFor（k）返回的是ｋ的　class,而不是　null）
    　　 
    　　 或者　compareComparables(kc, k, pk)　返回值为 0
    　　 (pk 为空　或者　按照 k.compareTo(pk) 返回值为０，返回值为０可能是由于
    　　 ｋ的compareTo 方法实现不当引起的，compareTo 判定相等，而上个 else if　中　equals 判定不等)*/
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            //在以当前节点为根的整个树上搜索是否存在待插入节点（只会搜索一次）
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                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);
        }//end else if

        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            //找到了待插入的位置，xp 为待插入节点的父节点
            //注意TreeNode节点中既存在树状关系，也存在链式关系，并且是双端链表
            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;
        }
    }//end for
}//end putTreeVal    　

static int tieBreakOrder(Object a, Object b) {
    int d;
    //System.identityHashCode()实际是利用对象 a,b 的内存地址进行比较
    if (a == null || b == null ||
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}

• 比较键与键之间 hash 的大小，如果 hash 相同，继续往下比较
• 检测键类是否实现了 Comparable 接口，如果实现调用 compareTo 方法进行比较
• 如果仍未比较出大小，就需要进行仲裁了，仲裁方法为 tieBreakOrder

五、扩容

final Node<K,V>[] resize() {
    
    // 如果 table 不为空，表明已经初始化过了
    if (oldCap > 0) {
        
        // 当 table 容量超过容量最大值，则不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        
        // 按旧容量和阈值的2倍计算新容量和阈值的大小
        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
        // 阈值暂存着桶数组初始容量，后续阈值重新计算
        newCap = oldThr;
    
    //调用无参构造方法时，桶数组容量为默认容量，
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // 有参构造重新计算阈值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        ...
    }
    ...
    
    // 将旧桶数组中的数据映射到新桶中
    if (oldTab != null) {
        //把　oldTab 中的节点　reHash 到　newTab 中去
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //若节点是单个节点，直接在 newTab　中进行重定位
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //若节点是　TreeNode 节点，要进行 红黑树的 rehash　操作
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //若是链表，进行链表的 rehash　操作
                else { // preserve order
                    ...
                }
            }
        }
    }
    return newTab;
}        

• 根据是否初始化桶数组，使用的有无参构造，计算新桶数组的容量 newCap 和新阈值 newThr
• 根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的
• 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。

// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;

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;
    /* 
     * 红黑树节点仍然保留了 next 引用，故仍可以按链表方式遍历红黑树。
     * 下面的循环是对红黑树节点进行分组，与上面类似
     */
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
        // 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            /* 
             * hiHead == null 时，表明扩容后，
             * 所有节点仍在原位置，树结构不变，无需重新树化
             */
            if (hiHead != null) 
                loHead.treeify(tab);
        }
    }
    // 与上面类似
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

从源码上可以看得出，重新映射红黑树的逻辑和重新映射链表的逻辑基本一致。

不同的地方在于，重新映射后，会将红黑树拆分成两条由 TreeNode 组成的链表。

如果链表长度小于 UNTREEIFY_THRESHOLD，则将链表转换成普通链表。

否则根据条件重新将 TreeNode 链表树化。

参考

HashMap 源码详细分析(JDK1.8)：https://segmentfault.com/a/1190000012926722?utm_source=tag-newest

JDK1.8源码阅读系列之四：HashＭap (原创)：https://www.cnblogs.com/Michaelwjw/p/6411176.html