hashMap 类图

　　　　　　　　　　　　　　　　　　　图1

hashMap数据结构图

　　　　　　　　　　　　　　　图2(注：该图实在网络上找的)

hashMap 变量初始值

// 默认的初始容量（必须是2的幂数）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 树化临界值
static final int TREEIFY_THRESHOLD = 8;
// 取消树化临界值
static final int UNTREEIFY_THRESHOLD = 6;
// 容器可以树状化的最小表容量。（应该至少是4 * TREEIFY_THRESHOLD）
static final int MIN_TREEIFY_CAPACITY = 64;
// 要调整大小的下一个大小值（容量×负载因子）。
int threshold;

实现逻辑

1. 实例化时，可以指定初始容量和负载因子，将初始容量赋给threshold；
2. put逻辑：
   2.1 若数组为空则初始化数组；
   2.2 计算key的hash值在数组中的位置，该位置若无值，则存放到该位置；
   2.3 若该位置有值，且为树节点，则将put的数据加入树中；
   2.4 若该位置有值，且不为树节点，则将put的数据加入链表的最后，并判断该链表是否达到树化条件；
   2.5 若达到树化条件，则将链表转化为红黑树
3. get逻辑：
   3.1 计算入参key的hash，取数组中该位置的值；
   3.2 判断该位置的值的key是否为入参的key，若不是，则执行以下步骤；
   3.2 若该值为树节点，则遍历红黑树，取相应的树节点；
   3.3 若该节点不为树节点，则遍历该链表，取与key相等的node；
4. remove逻辑：
   4.1 获取入参key所对应的Node节点；
   4.2 若Node为树节点，则调用node.removeTreeNode(this, tab, movable);移除树节点；
   4.3 若Node在数组中，则直接将node位置置空，若在链表中则将node的下个节点指针赋给上个节点；
   4.4 size做自减操作；
5. clear清空map逻辑：
   5.1 将size置0；
   5.2 遍历数组，将数组的每个位置置空；
6. resize扩容逻辑：resize方法主要分为两部分，一是数组的扩容，二是将迁移原数组的数据
   6.1 数组容量默认为16，最大为1>>30，负载因子默认为0.75，
   6.2 扩容的新数组是原数组的容量的2倍，并且下次扩容的阈值为新数组容量×负载因子；
   6.3 迁移原数据：结点在新数组中的位置只有两种，原下标位置或原下标+旧数组的大小；
   6.4 扩容时可能将树转换为链表。
7. hash实现：
   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

通过key的hashCode()的高16位去异或低16位；因为表使用的是2次幂掩码，因此这样做可以减少碰撞。

面试常问

1. HashMap数据结构？

在jdk8中，HashMap的数据结构变为数组+单链表+红黑树的结构，如图2；
并且单链表使用的是尾插法。

2. HashMap工作原理？

调用hash方法计算key的hash以确定在数组中的位置，若该位置不存在值，则插入到该位置；若该位置存在值，即发生碰撞，即判断该位置的节点是否为树节点，若为树节点，则调用添加树节点方法，若不为树节点，则遍历单链表，比对插入的key是否存在，若存在则替换value的值，若不存在则插入到单链表的尾部，若单链表的长度大于等于8则将链表转化为红黑树，最后size自加，并判断数组是否需要扩容，需要则调用resize方法进行扩容。

3. HashMap的数组扩容实现？

数组扩容分为两部分，第一部分是确定扩容后新数组的长度以及下次扩容的阈值，第二部分是将原数组中的值迁移到新的数组；
计算扩容数组的长度，新数组的长度扩容到原数组的长度的二倍，但不能超过2的30次幂；
下次扩容的阈值为新数组长度乘以负载因子，并且不能大于Integer的最大值；
迁移原数据，遍历原数组，重新计算节点在新数组的的位置，若是单链表则遍历单链表，若是 树节点，则调用树的拆分方法，将树拆分为上部和下部，若是树小于6则取消树化。