一，HashMap的底层数据结构
Java8 中HashMap的底层数据结构是数组＋链表，当数组长度达到64或者链表长度达到8时，将会把链表转化为红黑树。
1.HashMap的存取原理
put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 当前哈希表为空，则初始化
if ((tab = table) == null || (n = tab.length) == 0)
// 直接调用resize方法，返回长度，默认16
n = (tab = resize()).length;
// index的计算方法 (n - 1) & hash n是tab的Leagth
// 没有hash碰撞，则直接挂在tab[index]下
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 哈希值相等，key也equals相等，覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 遍历链表插入
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表节点数量 >= 8 转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 节点覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// e不是空，有需要覆盖的节点
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 空函数 Callbacks to allow LinkedHashMap post-actions
afterNodeAccess(e);
return oldValue;
}
}
// 插入新节点完毕，修改modCount
++modCount;
// 更新size 判断是否需要扩容
if (++size > threshold)
resize();
// 空函数 Callbacks to allow LinkedHashMap post-actions
afterNodeInsertion(evict);
return null;
}get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} // 传入扰动后的哈希值 和 key
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);
}
}2.resize，扩容，以及重新hash(rehash)
什么时候resize？
HashMap的默认负载因子是0.75f，所以当HashMap数组的长度大于容量＊0.75的时候，会对HashMap进行resize处理。
扩容分为两步，
首先，创建一个新的Entry空数组，长度是原来数组的两倍。
然后，进行ReHash操作，遍历原Entry数组，把所有的Entry重新Hash到新数组。
resize后是一定需要进行rehash的，因为index的计算与数组的长度相关，长度扩大之后，hash计算出来的值自然就发生了变化，这个会在下面hash计算展开详细描述。
对应HashMap源码位于resize()方法707行，往新的数组放元素进行了rehash。
3.Java7的头插法与Java8的尾插法
为什么Java7采用头插法，而Java8却改成了尾插法？
头插法插入会改变链表的顺序，导致并发情况下可能出现环形链表的情况，而改为尾插法之后，由于新插入元素之后维持原来链表的顺序不变，不会有环形链表的情况出现，但是在并发的情况下，会出现值覆盖的情况。
二，HashMap的主要参数都有哪些？
/**
* The default initial capacity - MUST be a power of two.
* 初始化容量必须是2的次方
*/
// 默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 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;
// 树形化最小容量
static final int MIN_TREEIFY_CAPACITY = 64;1.初始化容量为什么是16，为什么都要是2的次方？
为了实现数据的均匀分布。
首先了解index(HashMap底层是数组和链表)的计算规则，index = HashCode(Key) & (Length- 1) ,key的hash值与当前Node数组的长度做位运算。
奇数为什么不行？
由index的计算方法得知，Length为奇数，Length- 1为偶数，偶数二进制结尾都是0，经过＆运算后，index的末尾也都会时0，这样就会增加hash冲突。
2的倍数为什么不行？
2的幂数经过Length-1之后，二进制时二进制位全为1，这样计算的index等同于HashCode的后几位的值。
因为当Length为2的幂时，会满足(Length - 1) & hash = hash % Length，位运算的结果与取模的结果一直，index的计算效率更加高效。
2.默认负载因子为什是0.75？
负载因子:是哈希表在其容量自动扩容之前可以达到多满的一种度量。
首先看源码关于0.75有以下这样一段描述
关键内容是，分布良好的hash，树结构是很少用到的，理想情况下，节点服从泊松分布(Poisson distribution)，调整大小的参数平均是0.5，0.75与0.5差异很大，以为考虑调整粒度以及忽略方差。
总结来说，0.75作为默认的加载因子，是时间和空间成本上寻求的一种折衷选择。
0.5的话，虽然可以减少查询时间成本，但是空间的利用率过低，也就意味着会提高rehash操作的次数。
3.链表转红黑树的阈值为什么是8？
首先链表转红黑树是很消耗性能的，也就是说我们要尽可能减低树化的可能性。
还是上面的那张图，可以看到一个链表中达到8个元素的概率为 0.00000006，几乎是不可能事件，所以8应该是统计概率之后的最优选择。
三，HashMap中Hash的计算规则
1.HashMap是怎么处理hash碰撞的？
Hash碰撞或者Hash冲突，指的是计算hash之后所得的Index一致，即发生了hash碰撞，可以看下上面提到的头插法与尾插法，其实就是发生hash碰撞后如何添加数据的。
Java7中的解决办法是链表，Java8变成了链表+红黑树。
2.为什么重写equals方法时需要重写hashCode方法？
首先需要了解Object的hashCode和equals方法
通过源码我们可以很明显看出，hashCode方法返回的是一个整数，
而equals判断的是参数与当前对象thiis是否相等，这里的对象相等时比较对象的内存地址是否相同，如果内存地址相同，这两个对象相同。
所以，对象相等时，hashCode也一定相等，但是hashCode不同时，对象一定不相等，先比较hashCode可以减少equals比较次数，提高效率。
我们还知道，index的计算是index = HashCode(Key) & (Length- 1)，是与HashCode相关的，如果计算得出的index一致，那么就需要使用equals方法去确定同一个index位置的对象哪一个才是我们需要的那个对象。
总结来说，重写equals方法一定要重写hashCode方法是为了，保证不同的对象有不同的hashCode，相同的对象有同一个hashCode。
四，HashMap是否是线程安全
1.为啥会线程不安全？
Java7头插法并发情况下出现环形链表，transfer方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
而Java8还是之前提到的putVal()方法，由于没有锁，当线程A和线程B同时执行put，
Thread A 下图625行判断了tab[index] 为null，可以插入，但是还没有插入时，没有时间片而暂时挂起，
此时线程B也同样进行插入操作，而且同一个tab[index]位置正常插入元素，
之后，Thread A 再次执行626行put操作，就会把Thread B插入的元素覆盖。
2.有什么线程安全的类可以替代？
a.Hashtable,对所有方法加锁（synchronized）,所有线程锁的都是当前对象，锁的粒度太大。
b.ConcurrentHashMap，get时没有锁，put时有锁，锁的粒度比较小。
c.Collection.SynchronizedMap，锁的是同一个对象，每次锁的都是当前整张表，锁的粒度太大。
五，HashMap的红黑树操作
还没整理，先送上一篇文章连接，https://zhuanlan.zhihu.com/p/80587365