HashMap源码分析
1.HashMap的底层实现图示
hash表结构图
如上图所示：
HashMap底层是由 数组+（链表）=（红黑树）组成，每个存储在HashMap中的键值对都存放在一个Node节点之中，其中包含了Key-Value之外，还包括hash值（key.hashCode()) ^ (h >>> 16）） 以及执行下一个节点的指针next。
2.源码分析
2.1几个重要常量
static final int DEFAULT_INITIAL_CAPACITY =1 <<4; HashMap的默认容量，16
static final int MAXIMUM_CAPACITY =1 <<30; HashMap的最大支持容量，2^30
static final float DEFAULT_LOAD_FACTOR =0.75f; HashMap的默认加载因子
static final int TREEIFY_THRESHOLD =8; Bucket中链表长度大于该默认值，转化为红黑树
static final int UNTREEIFY_THRESHOLD =6; Bucket中红黑树存储的Node小于该默认值，转化为链表
static final int MIN_TREEIFY_CAPACITY =64; 桶中的Node被树化时最小的hash表容量。（当桶中Node的数量大到需要变红黑树时，若hash表容量小于MIN_TREEIFY_CAPACITY时，此时应执行resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。）
transient Node[] table; 存储元素的数组，总是2的n次幂
transient Set>entrySet; 存储具体元素的集
transient int size; HashMap中存储的键值对的数量
transient int modCount; HashMap扩容和结构改变的次数。
int threshold; 扩容的临界值，=容量*填充因子
final float loadFactor; 填充因子
2.2几个重要方法
1）无参构造方法
public HashMap() {
this.loadFactor =DEFAULT_LOAD_FACTOR;// all other fields defaulted
}
无参构造方法，设定了负载因子为0.75的默认值
2）指定容量的构造方法
public HashMap(int initialCapacity) {
this(initialCapacity,DEFAULT_LOAD_FACTOR);
}
这种构造方法，最后会调用3中的指定容量和负载因子的构造方法，将负载因子设置为默认值
3）指定容量和负载因子的构造方法
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);
}
这个构造方法来确定负载因子和扩容临界值，最后调用tableSizeFor方法来计算扩容临界值
4）根据键值对数量获取HashMap容量方法 tableSizeFor
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;
}
tabSizeFor方法，主要根据传入的键值对容量，来返回大于容量的最小的二次幂数值。
算法如下：
将传入的容量-1：至于这里为什么需要减1，是为了防止cap已经是2的幂。如果cap已经是2的幂, 又没有执行这个减1操作,则执行完后面的几条无符号右移操作之后,返回的capacity将是这个cap的2倍。
假设原始n: 0001 xxxx xxxx xxxx
第一次右移1位+或运算：二进制序列出现至少两个连续的1，如 0001 1xxx xxxx xxxx；
第二次右移2位+或运算：二进制序列出现至少四个连续的1，如 0001 111x xxxx xxxx；
第三次右移4位+或运算：二进制序列出现至少八个连续的1, 如 0001 1111 1111 xxxx;
第四次右移8位+或运算：二进制序列至少出现16个连续的1，如 0001 1111 1111 1111;
第五次右移16位+或运算：二进制序列至少出现32个连续的1，如 0001 1111 1111 1111;
上述运算中，若出现右移后为0，则或运算得到的结果和原始值一致，则后续推导过程可以忽略。
此时可以保证，原始序列从包含1的最高位，到最低位，全部都变成了1.
最后+1，返回的结果就是大于原值的最小二次幂数。
5）hash方法
static final int hash(Object key) {
int h;
return (key ==null) ?0 : (h = key.hashCode()) ^ (h >>>16);
}
hash方法用传入的key的hashCode和hashCode无符号右移16位的结果，做异或运算后作为hash值返回。
注：之所以获取hashCode后，还需要和右移16位的hashCode做异或运算，原因是：在根据hash值获取键值对在bucket数组中的下标时，采用的算法是：index=h & (length-1）,当数组的length较小时，只有低位能够参与到“与”运算中，但是将hashCode右移16位再与本身做异或获取到的hash，可以使高低位均能够参与到后面的与运算中。
下面图说明：
6）插入方法 putVal
final V putVal(int hash,K key,V value,boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p;int n, i; //存储Node节点的数组tab,单个Node节点p,HashMap的容量n
if ((tab =table) ==null || (n = tab.length) ==0) //初始化数组桶table （首次进入初始化）
n = (tab = resize()).length;
if ((p = tab[i = (n -1) & hash]) ==null) //如果数组桶中不包含要插入的元素，将新键值对作为新Node存入数组（当前tab中无冲突元素）
tab[i] = newNode(hash, key, value,null);
else { //桶中包含要插入的元素（tab中已有元素，发生冲突）
Node<K,V> e;K k; //e用来保存当前key已存在时的节点
if (p.hash == hash &&((k = p.key) == key || (key !=null && key.equals(k)))) //如果key和链表第一个元素p的key相等
e = p;
else if (pinstanceof TreeNode) //若p是TreeNode类型，则使用红黑树的方法插入到树中
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else { //键值对的引用不在链表的第一个节点，此时需要遍历链表
for (int binCount =0; ; ++binCount) {
if ((e = p.next) ==null) { //将p.next指向e，并判断p是否为最后一个节点，若是插入新节点，此时e==null
p.next = newNode(hash, key, value,null);
if (binCount >=TREEIFY_THRESHOLD -1)// -1 for 1st ，若链表长度大于等于8，变红黑树，退出遍历
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&((k = e.key) == key || (key !=null && key.equals(k)))) //找到与当前key值相同的节点
break; //退出遍历（此时，e指向与当前key值相同的旧节点）
p = e; //将e指向p,便于下次遍历e = p.next
}
}
if (e !=null) {// existing mapping for key 当e非空时，说明e是原来HashMap中的元素，具有和新节点一样的key值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue ==null) //onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
e.value = value;
afterNodeAccess(e); //空实现，LinkedHashMap用
return oldValue;
}
}
++modCount; //HashMap结构更改，modCount+1
if (++size >threshold) //判断是否需要扩容
resize();
afterNodeInsertion(evict); //空实现，LinkedHashMap用
return null;
}
HashMap中进行存储的入口方法是：put（K，V），但是核心方法是putVal方法，该方法一共有以下步骤：
1.初始化数组桶
2.判断数组桶中对应下标是否无元素存在，是，就直接存入
3.若数组桶中对应下标有元素存在，则开始遍历，根据长度将元素存入链表尾部或树中。
4.判断是否需要扩容
7）扩容方法 resize
final Node[] resize() {
Node[] oldTab =table;
int oldCap = (oldTab ==null) ?0 : oldTab.length; //原HashMap的容量
int oldThr =threshold; //原HashMap的扩容临界值
int newCap, newThr =0;
if (oldCap >0) { //case1 : odlCap>0,说明桶数组已经初始化过
if (oldCap >=MAXIMUM_CAPACITY) { //原HashMap的越界检查
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap <<1) < MAXIMUM_CAPACITY && oldCap >=DEFAULT_INITIAL_CAPACITY) //容量扩大一倍后的越界检查
newThr = oldThr <<1;// double threshold
}
//case2：oldCap=0 && oldThr >0，桶数组尚未初始化,当调用带初始化容量的构造函数时会发生该情况
else if (oldThr >0)// initial capacity was placed in threshold
newCap = oldThr; //在前面HashMap的初始化中，将Initial capcity暂存在threshold中,新的阀值按照下面newThr==0中的公式进行计算
//case3：oldCap=0 && oldThr = 0，当调用无参构造函数时会发生该情况，此时使用默认容量初始化
else {// zero initial threshold signifies using defaults
newCap =DEFAULT_INITIAL_CAPACITY; //默认容量
newThr = (int)(DEFAULT_LOAD_FACTOR *DEFAULT_INITIAL_CAPACITY); //默认扩容临界值
}
if (newThr ==0) { //case2中，调用Initial capcity构造方法时，该阀值为0，需计算阀值
float ft = (float)newCap *loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 35(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap]; //上面获取到的新的Capcity，来创建一个新的桶数组 newTab，并指向table
table = newTab;
if (oldTab !=null) { //若oldTab非空，则需要将原来桶数组的元素取出来放到新的桶数组中
for (int j =0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) !=null) {
oldTab[j] =null; //将原桶数组的元素占用的空间释放，便于GC
if (e.next ==null) //若桶中元素的next为空，获取index后直接将其放入新桶数组中
newTab[e.hash & (newCap -1)] = e;
else if (einstanceof TreeNode) //若桶中元素的next是树节点
((TreeNode)e).split(this, newTab, j, oldCap); //采用树的方式插入
else {// preserve order 若桶中元素的next是链表节点
Node loHead =null, loTail =null;
Node hiHead =null, hiTail =null;
Node next;
do {
next = e.next;
if ((e.hash & oldCap) ==0) { //若e.e.hash & oldCap 结果为0，则下标在新桶数组中不用改变，此时，将元素存放在loHead为首的链表中
if (loTail ==null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { //若e.e.hash & oldCap 结果不为0，则下标在新桶数组等于原下标+oldCap，此时，将元素存放在hiHead为首的链表中
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;
}
}
}
}
}
return newTab;
}
/*原始链表中的元素，在resize之后，其下标有两种可能，一种是在原来下标处，另一种是原来下标+oldCap处
*举例说明： 若原来的容量 -1后 只有n位，低位有n个1，去下标公式为：i = (oldCap - 1) & hash，若hash值只有低n为有值，则与运算后获得的值和
*扩容前是一样的，若hash不止第n位有值，那采用与运算后，结果比原来刚好大oldCap。 下面有图片示例）
*/
上述代码分析较长，总结如下：
1.获取不同情况下的 新的容量 和 新的扩容临界值
2.根据新容量创建新的桶数组tab。
3.根据节点类型，树节点和链表节点分别采用对应方法放入新的桶数组
8）查找元素方法 getNode
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e;int n;K k;
if ((tab =table) !=null && (n = tab.length) >0 && (first = tab[(n -1) & hash]) !=null) { //根据hash值，获取对应下标的第一个元素first
if (first.hash == hash && ((k = first.key) == key || (key !=null && key.equals(k))))// always check first node 如果first的key和待查询的key相等，返回first
return first;
if ((e = first.next) !=null) { //若first不是待查询的元素
if (firstinstanceof TreeNode) //若first是树节点，采用树节点的方式获取
return ((TreeNode)first).getTreeNode(hash, key);
do {
if (e.hash == hash && ((k = e.key) == key || (key !=null && key.equals(k)))) //first是链表节点头，使用循环获取
return e;
}while ((e = e.next) !=null);
}
}
return null;
}
查询元素的入口方法是：public V get(Object key)，返回值是node的value，核心方法是getNode(int hash, Object key)。
9）删除元素 removeNode方法
final Node removeNode(int hash, Object key, Object value, boolean matchValue,boolean movable) {
Node[] tab; Node p;int n, index;
//通过hash值获取下标，下标对应的节点p不为空
if ((tab =table) !=null && (n = tab.length) >0 && (p = tab[index = (n -1) & hash]) !=null) {
Node node =null, e;K k;V v;
if (p.hash == hash && ((k = p.key) == key || (key !=null && key.equals(k)))) //若节点p的key和待移除的节点key相等
node = p; //将p指向待移除节点
else if ((e = p.next) !=null) { //p的key和待移除的节点key不相等，遍历p作为头的链表或者树
if (pinstanceof TreeNode) //采用树节点方式获得要移除的节点
node = ((TreeNode)p).getTreeNode(hash, key);
else { //p是链表的头节点
do {
//采用循环，当p.next不为空，比对它和传入的key，直到找到相等的key
if (e.hash == hash && ((k = e.key) == key || (key !=null && key.equals(k)))) {
node = e; //找到后，将节点指向node
break; //将e指向待移除节点，此时相当于p.next就是待移除的节点node
}
p = e;
}while ((e = e.next) !=null);
}
}
//若node非空，传入的matchValue参数为flase或 node的value等于传入value
if (node !=null && (!matchValue || (v = node.value) == value || (value !=null && value.equals(v)))) {
if (nodeinstanceof TreeNode) //若node是树节点
((TreeNode)node).removeTreeNode(this, tab, movable);
else if (node == p) //若待移除节点是链表头，将其指向待移除元素的next，移除对node的引用
tab[index] = node.next;
else //待移除元素是链表中的元素，此时其等于p.next
p.next = node.next; //将p.next指向node.next，移除了对node的引用
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
移除节点的入口方法是： public V remove(Object key) ，其核心方法是removeNode，主要做了以下几个工作：
1.通过用key获取的hash，来获取下标。
2.若下标对应处无元素，返回null。
3.若下标对应处有元素，判断是树或者链表，采用对应方法移除。
3.常见问题
3.1HashMap的容量为什么必须是2的n次幂？
1.由上述实例可以看出，当HashMap容量为2的n次幂的时候，length-1，可以使得在计算index的"&"运算过程中，hash值的对应位都能参与到计算；若HashMap容量不等于2的n次幂，leng-1后必然有一些位是等于0的，那么在计算index的"&"运算过程中，对应位的数字无论是0或者1，都未能参与到运算中。导致Hash冲突概率增大。
2.初次之外，若HashMap容量不为2的n次幂，无论Hash值如何变化，始终有一些下标值无法取得，因为"&"运算过程中，必然有一些位置结果始终为0，如实例所示，其最低位始终为0，因此下标 1（二进制0000 0001）、3（二进制0000 0011）、5（二进制0000 0101）、7（二进制0000 0111）等下标、永远都获取不了。造成了容量的浪费
综上: 当容量是2的n次幂时，不同的key获取在桶数组中的下标相同的概率减小，发生Hash碰撞几率减少，元素分布更加均匀，见下图。
3.2 HashMap的时间复杂度？
O(1)或者O(log(n))或O(n),分析如下:
根据第一节的内容可知，根据HashMap的数据结构，可能有以下三种情况：
1.无链表和红黑树，理想状态。每个桶只有一个或0个元素，不存在Hash冲突，此时时间复杂度为O(1);但此时耗费的内存空间较大。
2.只有链表，此时因为需要循环链表来获取元素，时间复杂度为O(n)
3.只有红黑树，此时时间复杂度为红黑树查找的时间复杂度，O(log(n)).
4.链表和红黑树均有，此时时间复杂度依据红黑树的层数和链表长度而定。为O(n)或者O(log(n)).
3.3 负载因子LoadFactor为何默认值为0.75。
当负载因子过大时，Hash冲突概率增加、读写的时间复杂度也大大增加，当负载因子过小时，Hash冲突概率较小，时间复杂度较低，但占用内存空间较大。至于为什么默认值是0.75，这是一个基于时间和空间复杂度的综合考虑的结果，可以参考这篇文章：HashMap的loadFactor为什么是0.75？
3.4 作为HasHMap的key有什么条件？
使用HashMap，若用int/String等作为key值，因为Integer类和String类都以及重写了equals()和hashCode()方法.但是如果key是自定义的类，就必须重写hashcode()和equals()。理由如下：
//在插入元素中，根据hash值后，与length-1做&运算获取下标
//获取hash
static final int hash(Object key) {
int h;
return(key ==null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//获取下标p = tab[i = (n - 1) & hash]
//用equals方法比对key值和节点的key值，来确认是否遍历到所需元素(key !=null&& key.equals(k)))
//对比hash值，如果不重写hashCode方法，那么采用Object类的默认的hash方法是获取内存地址，此时即使两个key对象相等，但其内存地址不可能相等，所以必须重写hashCode方法
//equals方法若不重写，采用的Object的equals方法，比对的是内存地址，如果不重写，会造成两个一样的key值都插入，存在重复元素*/
//同理，在查找过程中，在第二节putVal方法中有分析，会用到hash值，以及用到key.equals方法，因此如果不重写equals()和hashCode()，会造成虽然元素存在，但是因内存地址不一致，差找不到对应元素。
3.5HashMap key允许为空吗？，最多几个？
允许但只允许一个key值为空。当key值为空时，其hash值为0，因此在桶数组中位置是0，即第一个元素。
那么为什么不能有两个key值为null呢，原因是两个key为null，是一样的，后面put进去的(null,value2)会覆盖先put进去的(null,value1)
摘自：https://www.cnblogs.com/LearnAndGet/p/9971526.html
