HashMap在JDK1.7和JDK1.8的改动

Integer.MAX_VALUE = 2 ^ 31 - 1;

HashMap table 的最大大小 1 << 30 = 2 ^ 30

HashMap 查找的时间复杂度 O(1) + O(n) (before JDK 1.7) | O(1) + O(logN) (after JDK 1.8)

JDK 1.7 和 1.8 的区别

1. JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法，那么他们为什么要这样做呢？因为JDK1.7是用单链表进行的纵向延伸，当采用头插法时会容易出现逆序且环形链表死循环问题 （在并发环境中进行扩容时）。但是在JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。
2. 扩容后数据存储位置的计算方式也不一样：1. 在 JDK1.7 的时候是直接用 hash 值和需要扩容的二进制数进行&（这里就是为什么扩容的时候为啥一定必须是2的多少次幂的原因所在，因为如果只有2的n次幂的情况时最后一位二进制数才一定是1，这样能最大程度减少 hash 碰撞) (hash值 & length-1)

Key 的 Hash 策略

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

/*	
	这里 HashMap 的最大容量只能到 Integer.MAX_VALUE 的一半。原因是 HashMap 的容量必须是 2 的整数次幂，其二进制表示必须为 某位为1，其余所有位均为0。这个最大值是 1 << 30。
	
	这个方法接收的参数是 KEY 的 hashCode, 由于在计算位置时使用了 原理上与取余一样的位操作 , 
	table 长度 n 为 2 的整数次幂，并且 table 的最大值为 1 << 30，所以在进行计算 hash 时只会用到 int 的低 16 位，设计者认为如果只取低 16 位很容易产生 Hash 碰撞，所以也将 高 16 位 右移过来参与了计算。
*/

HashMap 中的一些常量

    /**
     * The load factor used when none specified in constructor.
     * 默认的装填因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The default initial capacity - MUST be a power of two.
     * 默认的容量
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * 最大容量
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 容量大于 8 转为红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 容量小于 6 转为链表 （尾插）
     */
    static final int UNTREEIFY_THRESHOLD = 6;

		/**
     * The next size value at which to resize (capacity * load factor).
     * 阈值 = 容量 * 装填因子
     * @serial
     */
    int threshold;

​ 如果在 new HashMap()时未指定初始容量，则在第一次 putVal() 时即会触发一次 resize() 操作，扩容 (或者称为初始化更贴切) 后的大小为 DEFAULT_INITIAL_CAPACITY = 16

​ 除了初始化之外，扩容操作会扩大为原来的两倍

​ 缩容操作：

链表结构的 Node 节点

/**
 * Basic hash bin node, used for most entries.  (See below for
 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 */
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

// 对应的初始化操作：
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

扩容的 rehash 操作

/** 
* hash 值与元素位置的对应策略
* hash 与一个数 N 按位与，只能得到 <= N 的数
* 这个过程相当于取余，不过位操作的效率更高
* x % y = x - floor(x/y);
*
* @since jdk1.7
*/
newTab[e.hash & (newCap - 1)] = e;

/**
 * @since jdk1.8
 */
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;
}

​ jdk1.7 及以前的 rehash 操作实际上是对 hash 值与新的数组大小减1进行了按位与操作。

​ jdk1.8 之后对 rehash 操作做了优化， 不再计算按位与，而是直接使用 原来的位置或者原来的位置加上原来的数组长度

​ 1.8 版本之后能这么做的原因是：

1. 数组长度必须是 2 ^ N ，N是整数。如果初始化时指定了一个长度为 13，实际也会扩大成 16

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

/**
 * 只会取 2^N 的值
 */
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;
  /*
    int 32 位, 这里取其 低 16 位说明
    >>> 无符号位右移，高位直接补0
    313 - 1 = 0000 0001 0011 1000
    n = 0000 0001 0011 1000 | 0000 0000 1001 1100 = 0000 0001 1011 1101;
    n = 0000 0001 1011 1101 | 0000 0000 0110 1111 = 0000 0001 1111 1111;

    该操作即为先减一，然后找到第一个 `1` 将其后面所有位都置为 1
  */
}

2. 每次扩容都必须扩大成原来的 2 倍

   newCap = oldCap << 1
   

比如，容量从 16 扩大成 32 的过程，原来的位置是通过 hash 值与 16 - 1 按位与得到的，新的位置应该与 32 - 1 按位与得到。

16 - 1 = 0000 0000 0000 1111
32 - 1 = 0000 0000 0001 1111

​ 所以 hash 值与这两个数按位与的结果就是取 低 4 位还是取低 5 位值的问题。如果 hash 值的第 5 位为 1，那么新位置就是原来位置 + 16（原来数组大小），如果 hash 值的第 5 位为 0，那么新位置就是 原来的位置不变。

例如我们从16扩展为32时，具体的变化如下所示：

	resize前	resize后
n	16	32
n -1的十进制形式	2^4 - 1=2^0 + 2^1 +…+2^3	= 2^5 - 1=2^0 + 2^1 +…+2^3 + 2^4
n-1的二进制形式（int类型，32位）	高28位为0，低4位为1相当于低4位掩码0000 0000 0000 0000 0000 0000 0000 1111	高27位为0，低5位为1相当于低5位掩码0000 0000 0000 0000 0000 0000 0001 1111
低第5位为0的hashhash&(n - 1)的结果：（以hash值为1111 1111 1111 1111 0000 1111 0000 0101为例）	与低4位掩码相与，保留低4位内容0000 0000 0000 0000 0000 0000 0000 0101转为10进制后为5	与低5位掩码相与，保留低5位内容0000 0000 0000 0000 0000 0000 0000 0101转为10进制后为5（该结果与resize前相同）
低第5位为1的hashhash&(n - 1)的结果：（以hash值为1111 1111 1111 1111 0000 1111 0001 0101为例）	与低4位掩码相与，保留低4位内容0000 0000 0000 0000 0000 0000 0000 0101转为10进制后为5	与低5位掩码相与，保留低5位内容0000 0000 0000 0000 0000 0000 0001 0101转为10进制后为21（该结果与resize前不同）（= resize前的结果 + 2^4）（= resize前的结果 + resize前的n值）

【参考资料】位运算的奇淫巧技

本文地址：https://blog.csdn.net/PitBXu/article/details/109637873