HashMap他的结构和底层原理
我知道HashMap是我们非常常用的数据结构，由数组和链表组合构成的数据结构。
大概如下，数组里面每个地方都存了Key-Value这样的实例，在Java7叫Entry在Java8中叫Node。
因为他本身所有的位置都为null，在put插入的时候会根据key的hash去计算一个index值。
你提到了还有链表，为啥需要链表，链表又是怎么样子的呢？
我们都知道数组长度是有限的，在有限的长度里面我们使用哈希，哈希本身就存在概率性，就是”Aa“和”aA“我们都去hash有一定的概率会一样，就像上面的情况我再次哈希”aA“极端情况也会hash到一个值上，那就形成了链表。
每一个节点都会保存自身的hash、key、value、以及下个节点，我看看Node的源码。
说到链表我想问一下，你知道新的Entry节点在插入链表的时候，是怎么插入的么？
java8之前是头插法，就是说新来的值会取代原有的值，原有的值就顺推到链表中去，就像上面的例子一样，因为写这个代码的作者认为后来的值被查找的可能性更大一点，提升查找的效率。
但是，在java8之后，都是所用尾部插入了。
为啥改为尾部插入呢？
首先我们看下HashMap的扩容机制：
帅丙提到过了，数组容量是有限的，数据多次插入的，到达一定的数量就会进行扩容，也就是resize。
什么时候resize呢？
有两个因素：
怎么理解呢，就比如当前的容量大小为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。
原文：https://www.cnblogs.com/goodhao/p/13948853.html