HashMap 根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快
的访问速度，但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null，允许多条记
录的值为 null。 HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导
致数据的不一致。如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使
HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap。 我们用下面这张图来介绍
HashMap 的结构。
大方向上， HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。上图中，每个绿色
的实体是嵌套类 Entry 的实例， Entry 包含四个属性： key, value, hash 值和用于单向链表的 next。
capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。
loadFactor（负载因子）默认为0.75，threshold（阈)为12（ capacity * loadFactor ），并创建一个大小为16的Entry数组。
在遍历时是无序的，如需有序，建议使用TreeMap。
采用数组方式存储key、value构成的Entry对象，无容量限制。
基于key hash寻找Entry对象存放在数组中的位置，对于hash冲突采用链表/红黑树的方式来解决。
HashMap在插入元素时可能会扩大数组的容量，在扩大容量时需要重新计算hash，并复制对象到新的数组中。
是非线程安全的。
哈希冲突时采用链表法的类，一个哈希桶多于8个元素改为TreeNode
static class Node<K,V> implements Map.Entry<K,V>
哈希冲突时采用红黑树存储的类，一个哈希桶少于6个元素改为Node
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>
Hash冲突中链表结构的数量大于8个，则调用树化转为红黑树结构，红黑树查找稍微快些；红黑树结构的数量小于6个时，则转为链表结构
添加了红黑树
Java8 对 HashMap 进行了一些修改， 最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树组成。
根据 Java7 HashMap 的介绍，我们知道查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话， 需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度为 O(n)。为了降低这部分的开销，在 Java8 中， 当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)
节点插入方式的不同
java7是头插法，在java8之后，都是用尾插法了 具体原因如下：
因为数组容量是有限的，数据多次插入的，到达一定的数量就会进行扩容，也就是resize。
什么时候resize呢？
有两个因素：
Capacity：HashMap当前长度。
LoadFactor：负载因子，默认值0.75f。
怎么理解呢，就比如当前的容量大小为100，当你存进第76个的时候，判断发现需要进行resize了，那就进行扩容，但是HashMap的扩容也不是简单的扩大点容量这么简单的。
扩容？它是怎么扩容的呢？
分为两步
为什么要重新Hash呢
因为长度扩大以后，Hash的规则也随之改变。
Hash的公式—> index = HashCode（Key） & （Length - 1）
原来长度（Length）是8你位运算出来的值是2 ，新的长度是16你位运算出来的值明显不一样了。
扩容前：
扩容后：
为啥之前用头插法，java8之后改成尾插了呢？
我先举个例子吧，我们现在往一个容量大小为2的put两个值，负载因子是0.75是不是我们在put第二个的时候就会进行resize？
2*0.75 = 1 所以插入第二个就要resize了
现在我们要在容量为2的容器里面用不同线程插入A，B，C，假如我们在resize之前打个短点，那意味着数据都插入了但是还没resize那扩容前可能是这样的。
我们可以看到链表的指向A->B->C
Tip：A的下一个指针是指向B的
因为resize的赋值方式，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置，在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。就可能出现下面的情况。
B的下一个指针指向了A
一旦几个线程都调整完成，就可能出现环形链表
如果这个时候去取值，悲剧就出现了——Infinite Loop。出现死循环，
使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。
就是说原本是A->B，在扩容后那个链表还是A->B
Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。
Java8在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。
如何根据hash值计算index？（put和get中的代码)
n = table.length;
index = (n-1)& hash;
当n总是2的n次方时，hash & (n-1)运算等价于hash %n，但是&比%具有更高的效率。
hash的计算规则？
hash（hash算法，算法比较高效、均匀)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
HashMap的扩容方式？负载因子是多少？为什是这么多？
如果加载因子越大，对空间的利用更充分，但是查找效率会降低（链表长度会越来越长)；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了)，对空间造成严重浪费。如果我们在构造方法中不指定，则系统默认加载因子为0.75，这是一个比较理想的值，一般情况下我们是无需修改的。
为何按位与而不是取摸
一般对哈希表的散列很自然地会想到用hash值对length取模（即除法散列法)，Hashtable中也是这样实现的，这种方法基本能保证元素在哈希表中散列的比较均匀，但取模会用到除法运算，效率很低，HashMap中则通过h&(length-1)的方法来代替取模，同样实现了均匀的散列，而且效率要高很多，这也是HashMap对Hashtable的一个改进。
默认初始化大小是多少？为啥是这么多？为啥大小都是2的幂？
哈希表的容量一定要是2的整数次幂。首先，length为2的整数次幂的话，hsahcode&(length-1)就相当于对length取模，这样便保证了散列的均匀，同时也提升了效率；其次，length为2的整数次幂的话，为偶数，这样length-1为奇数，奇数的最后一位是1，这样便保证了h&(length-1)的最后一位可能为0，也可能为1（这取决于h的值)，即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间，因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。
有什么线程安全的类代替么?
ConcurrentHashMap，SynchronizedMap ，HashTable
为啥我们重写equals方法的时候需要重写hashCode方法呢？
因为在java中，所有的对象都是继承于Object类。Ojbect类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的。
HashMap是通过key的hashCode去寻找index的，那index一样就形成链表了，也就是说”B“和”A“的index都可能是2，在一个链表上的。
我们去get的时候，他就是根据key去hash然后计算出index，找到了2，那我怎么找到具体的”B“还是”A“呢？
equals！是的，所以如果我们对equals方法进行了重写，建议一定要对hashCode方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。
不然一个链表的对象，你哪里知道你要找的是哪个，到时候发现hashCode都一样，这不是完犊子嘛
我这篇blog主要是参考网上的，对相关问题和知识点进行概括，写的很不好，在这写下来是为了记录下来用来回顾知识点用的（见谅）
参考：https://mp.weixin.qq.com/s/0Gf2DzuzgEx0i3mHVvhKNQ
https://zhuanlan.zhihu.com/p/28501879