原理

HashMap的底层采用的散列算法是拉链法（另一种散列算法是线性探测法）。并且在JDK1.8中使用红黑树对长链表进行优化。

初始容量、负载因子、阈值

初始容量比较好理解，阈值指的是当桶的个数超过了这个值后Hash表会进行扩容。

/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;

注释中说的是阈值可以通过容量乘以负载因子得到，但是实际上我们通过的是tableSizeFor方法初始化阈值：

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);  // 根据初始容量得到阈值，例如初始容量为10，则阈值为16
}

/**
* Returns a power of two size for the given target capacity.
*/
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操作。int n = cap - 1; 这是为了防止，cap已经是2的幂。如果cap已经是2的幂，又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。如果不懂，要看完后面的几个无符号右移之后再回来看看。

下面看看这几个无符号右移操作：
如果n这时为0了（经过了cap-1之后），则经过后面的几次无符号右移依然是0，最后返回的capacity是1（最后有个n+1的操作）。

这里只讨论n不等于0的情况。

第一次右移

由于n不等于0，则n的二进制表示中总会有一bit为1，这时考虑最高位的1。通过无符号右移1位，则将最高位的1右移了1位，再做或操作，使得n的二进制表示中与最高位的1紧邻的右边一位也为1，如000011xxxxxx

第二次右移

注意，这个n已经经过了n |= n >>> 1; 操作。假设此时n为000011xxxxxx ，则n无符号右移两位，会将最高位两个连续的1右移两位，然后再与原来的n做或操作，这样n的二进制表示的高位中会有4个连续的1。如00001111xxxxxx

第三次右移

这次把已经有的高位中的连续的4个1，右移4位，再做或操作，这样n的二进制表示的高位中会有8个连续的1。如00001111 1111xxxxxx 。以此类推。

注意，容量最大也就是32bit的正数，因此最后n |= n >>> 16; ，最多也就32个1，但是这时已经大于了MAXIMUM_CAPACITY，所以取值到MAXIMUM_CAPACITY。

使用移位运算算数组的阈值

为什么大部分hashCode都选用素数31

String类的hashCode实现是这样的：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

idea自动生成的hashCode方法调用的是Object.hash，而Object.hash调用的是Arrays.hash，如下所示：

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

从上面的代码中，我们也可以发现HashMap是允许空键的

都不约而同使用了素数31。为什么要选择这样一个素数呢？

第一，31是一个不大不小的质数，是作为 hashCode 乘子的优选质数之一。另外一些相近的质数，比如37、41、43等等，也都是不错的选择。那么为啥偏偏选中了31呢？请看第二个原因。
第二、31可以被 JVM 优化，31 * i = (i << 5) - i。

HashMap 的 hash 算法的实现原理

为什么右移 16 位，为什么要使用异或。

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

HashMap在寻找桶的时候不会直接调用对象的hashCode取得下标，而是会使用上面的抖动函数对对象的hashCode再进行一次加工，使求得到的哈希值分布尽量平均。但是为什么移动16位，为什么异或？

在分析这个问题之前，我们需要先看看另一个事情，什么呢？就是 HashMap 如何根据 hash 值找到数组种的对象，我们看看 get 方法的代码：

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 && (n = tab.length) > 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;
        if ((e = first.next) != null) {
            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);
        }
    }
    return null;
}

我们看看代码中注释下方的一行代码：first = tab[(n - 1) & hash]。

使用数组的最后一个索引和传入的hash值进行与运算。这句代码就是为什么要让前面的抖动函数移位并异或。

如果不经过抖动函数的处理，假设有一种情况：

a.hashCode: 01000010001110001000001111000000
b.hashCode: 00111011100111000101000010100000

假设数组长度为16，也就是说上面两个数要和15(转化成二进制是28个0加4个1)进行与操作，因为a和b的后4位都是1，从而结果都是0。换而言之：如果不经过抖动函数的处理，则丢失了高位的细节，hash不均匀。但是如果我们将 hashCode 值右移 16 位，也就是取 int 类型的一半，刚好将该二进制数对半切开。并且使用位异或运算（如果两个数对应的位置相反，则结果为1，反之为0），这样的话，就能避免我们上面的情况的发生。

总的来说，使用位移 16 位和异或就是防止这种极端情况。但是，该方法在一些极端情况下还是有问题，比如：10000000000000000000000000 和 1000000000100000000000000 这两个数，如果数组长度是16，那么即使右移16位，在异或，hash 值还是会重复。但是为了性能，对这种极端情况，JDK 的作者选择了性能。毕竟这是少数情况，为了这种情况去增加 hash 时间，性价比不高。

HashMap 为什么使用 & 与运算代替模运算

计算数组下标的方法中使用了tab[(n - 1) & hash]。这个代码其实和tab[hash % n]是一样的（n是数组长度，等于2的幂）。抽象成一般情况就是：a % b == (b - 1) & a（b是2的幂）。

我们可以这样思考：当b是2个幂的时候，b-1可以得到末位全是1的数字，例如:

(11)2 = 3
(111)2 = 7
(1111)2 = 15

可以看出b-1其实是掩码，和这个数字进行与运算其实是和求余数是等价的（过滤高位的结果，并且低位保持不变，数据区间[0,掩码]）。

如何手动构造哈希冲突

复用上面的概念，传入的hash与掩码进行与运算可以得到哈希桶的索引，我们只需要手动让索引全部相等即可。例如：假设此时hash桶的个数为16 = 2^4，则掩码为(1111)2。

如果我们希望碰撞后的索引位于0号索引，则二进制表示就是0,10000,100000,110000 …. 我们只要保证构造的数据后4位（和掩码的位数相同）都是0即可.

const max = 0x7fffffff;
const bit = 14;
const mask = 1 << bit - 1;
const size = 1 << bit;
const hashCollisionKeys = [];

// 构造hash冲突的元素
for (let cur = 0; cur >= 0 && cur <= max; cur += size) {
  hashCollisionKeys.push(String(cur));
}

console.log('key的长度', hashCollisionKeys.length);

const _ = require('lodash');

const normalKeys = [];
for (let i = 0; i < hashCollisionKeys.length; i++) {
  normalKeys.push(String(_.random(0, max)));
}

const map1 = new Map();
const map2 = new Map();

console.time('normal#insert');
for (const key of normalKeys) {
  map1.set(key, 1);
}
console.timeEnd('normal#insert');

console.time('collision#insert');
for (const key of hashCollisionKeys) {
  map2.set(key, 1);
}
console.timeEnd('collision#insert');

console.time('normal#get');
for (let i = 0; i < 1000; i++) {
  map1.get(_.sample(normalKeys));
}
console.timeEnd('normal#get');

console.time('collision#get');
for (let i = 0; i < 1000; i++) {
  map2.get(_.sample(hashCollisionKeys));
}
console.timeEnd('collision#get');

我们知道Integer类型的hashCode等于其自身，因此以上述结果做成的键作为Hash表的key将会导致Hash冲突，性能急剧下降。

key的长度 131072
normal#insert: 31.981ms
collision#insert: 23341.859ms
normal#get: 1.100ms
collision#get: 158.040ms

以这样的整数作为键插入到HashMap中会造成Hash冲突，利用这个原理可以进行哈希碰撞攻击。

HashMap 的容量为什么建议是 2的幂次方

假设数组容量为10，即与运算的对象是10 = (1010)2

任何一个二进制数和以上的结果进行运算只会产生0000,0010,1000,1010，4种结果，而1111，0111 ……根本不会出现，因此和一个掩码进行与运算可以得到的散列结果最多。散列结果最多可以理解为数据分布比较均匀，不容易产生哈希碰撞。

所以，当我们为HashMap指定初始容量的时候应该向上乘以1.33倍(0.75倍扩容)，再向上取一个二进制数。

为什么HashMap非线程安全而HashTable线程安全

查看源码可知HashTable大部分方法都被synchronized关键字修饰过。HashTable的Hash算法采用的取余，而HashMap用位运算；HashTable每次扩容的时候是原先的2倍容量加1，HashMap是2的幂。

其实应对并发场景，推荐使用ConcurrentHashMap，因为HashTable虽然是线程安全的，但是使用的的是synchronized关键字修饰方法，相当于对对象进行上锁，所以当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。

JDK 1.8中ConcurrentHashMap采用的是CAS原理。如果没有Hash冲突则进行CAS插入，否则使用syn关键字较低粒度锁住节点，进行插入。

参考链接

为什么常用的hash算法中用31作为乘子