HashMap是java开发中常见的一个类，也是面试中经常会被问到的类，诸如：
- HashMap的底层数据结构是什么？
- HashMap默认容量多大？什么时候会扩容？
- HashMap中底层中的链表何时会被转化为红黑树？
这些问题如果阅读过源码就能够轻松回答上来，如果没有那就只能凉凉，HashMap这个系列以及后面可能还会写的ConcurrentHashMap、LongAdder等，我会尽量认真写完，想学习的同学请认真读懂我写在代码上的注释，在阅读源码之前需要了解什么是位运算，会编写基本的链表。
一、静态常量
打开HashMap的源码，首先会看到下面这几个常量，这些常量每个都很重要，需要先了解它们的含义。
/**
* HashMap默认容量 --- 16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* HashMap的最大容量 --- 2^30
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 负载因子 0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 扩容阈值
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 从红黑树退化为链表的阈值
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 链表转换为红黑树的最小桶数量（数组长度）
*/
static final int MIN_TREEIFY_CAPACITY = 64;
DEFAULT_INITIAL_CAPACITY HashMap默认容量，这里使用位运算让1左移4位,也就是从0000 0001变为0001 0000，即为16，如果创建HashMap时不传入容量，则使用16作为默认值。可能有同学疑惑为什么是16，16其实是一个经验值，在大多数情况下，16刚刚好可以满足大部分的需求。
MAXIMUM_CAPACITY HashMap的最大容量，同样使用位运算完成赋值2^30，为什么使用位运算而不使用乘法运算？这是因为计算机底层中乘法会最终还是用加法计算得出结果，而位运算的话则会高效很多，以后在阅读源码的过程中会发现很多源码涉及到乘除的计算都会使用位运算代替。
DEFAULT_LOAD_FACTOR负载因子，扩容阈值 = 当前数组长度 * 负载因子。
TREEIFY_THRESHOLD 扩容阈值，当HashMap中元素个数达到扩容阈值时会发生扩容。
UNTREEIFY_THRESHOLD 从红黑树退化为链表的阈值。
MIN_TREEIFY_CAPACITY 链表转换为红黑树的最小桶数量。
二、链表
这是HashMap中的静态内部类，也是真正存放元素的类，后面使用时会创建一个Node数组。
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;
}
}
三、构造方法
构造方法有四个，HashMap(int initialCapacity, float loadFactor) ，HashMap(int initialCapacity) ，HashMap() HashMap(Map<? extends K, ? extends V> m)，我们最常用的应该是第三个，构造方法主要就是用来确定初始容量和负载因子，如果不传则使用默认值 16 和 0.75。需要注意的是第一个构造方法中的tableSizeFor(initialCapacity) 这个方法，它是用来修改传入的初始容量，让初始容量变为大于传入的数的2的整数次幂，举个例子，如果传入的是5则返回结果为8、传入的是27则返回结果为32。最后一个构造方法就是把另一个map放入新的map中，可以先跳过。
/**
* initialCapacity: 初始容量
* loadFactor: 负载因子
*/
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;
// 计算初始容量，让初始容量变为2的整数次幂。
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
现在来看一下tableSizeFor的内部逻辑，属实是非常非常牛皮的代码了，但是为什么要这么做？这个留待后续分析中会有答案。
/**
* 演示传入值为30 (0000 0000 0001 1110) 的情况
* n = 30 - 1 = 29 -> 0000 0000 0001 1101
* n与n无符号右移1位后做或运算
* 0000 0000 0001 1101 | 0000 0000 0000 1110 = 0000 0000 0001 1111
* 0000 0000 0001 1111 | 0000 0000 0000 0111 = 0000 0000 0001 1111
* 0000 0000 0001 1111 | 0000 0000 0000 0001 = 0000 0000 0001 1111
* 0000 0000 0001 1111 | 0000 0000 0000 0000 = 0000 0000 0001 1111
* 0000 0000 0001 1111 | 0000 0000 0000 0000 = 0000 0000 0001 1111
* n = 31 最终返回n + 1 = 32
*/
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;
}
四、hash()
HashMap中设计了一个扰动算法来作为每个元素的hash值，后续会使用这个hash值来判断元素是否相等以及用于寻找元素存放的数组下标。
static final int hash(Object key) {
int h;
/**
* h = key.hashCode()先获得key的hashCode值，然后让hashCode和hashCode的高16位进行异或运算
* 演示 hashCode为 0010 0101 1001 1011 0100 0010 0101 1011
* 0010 0101 1001 1011 0100 0010 0101 1011 ^ 0000 0000 0000 0000 0010 0101 1001 1011
* 0010 0101 1001 1011 0110 0111 1100 0000
* 这样做的好处是让hash可以更加均匀的分布以减少hash冲突
*/
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
