数据结构之HashMap
前言：
在我们开发中，HashMap是我们非常常用的数据结构，接下来我将进一步去了解HashMap的原理、结构。
一：HashMap实现原理
HashMap底层是基于Hash表（也称“散列”）的数据结构实现的，由数组和链表组成，数组是HashMap的主体，链表主要是为了解决哈希冲突而存在的。
数组里每个地方都存了Key-Value这样的实例，在Java7中叫 Entry，在Java8中叫 Node。
他本身所有的位置都是 null，在 put 插入的时候会根据 key 的 hash 值去计算一个 index 值。
例如，我 put(“兄弟”，“砍我”)，我插入了为“兄弟”的元素，这个时候我们会同通过哈希函数计算插入的位置，计算出来的 index 是2，那结果如下。
hash("兄弟") = 2
以上就是我们前面说到的，数组是HashMap的主体。而为什么需要用到链表，这就需要提到哈希冲突了。
我们都知道数组长度是有限的，在有限的长度里面我们使用哈希，哈希本身就存在概率性，就是“兄弟”和“弟兄”我们都去hash，有一定的概率会一样，这就出现我们说的哈希冲突，就像上面的情况，我再次哈希“弟兄”极可能会hash到一个值上，这就形成了链表。
每一个节点都会保存自身的 hash、key、value、以及下个节点，我们看看 Node 的源码。
二：关于链表，新的Entry节点插入链表的方式
新增一个Entry节点，在 Java8 之前是头插法，就是说新来的值会取代原有的值，原有的值就顺推到链表中去，就像上面的例子一样，新增的"弟兄"会代替“兄弟”的位置，因为写这个代码的坐着认为后来的值被查找的可能性更大，有利于提升查找到的效率。
但是，在Java8之后，都是使用尾部插入法。至于为何使用尾插法，这就跟我们的扩容机制有关了。
三：HashMap扩容机制
前面我们提过，数组容量是有限的，数据多次插入，到达一定数量就会进行扩容，也就是resize。
而扩容的时机主要取决于两个因素：
- Capacity：HashMap当前长度；
LoadFactor：负载因子，默认值是 0.75f 。
这个比较好理解，比如我们当前容量大小是100，当你存进第76个的时候，判断发现需要进行 resize 了，那就进行扩容，但是HashMap的扩容也不是简单地扩大容量这么简单的。
HashMap的扩容分为两步：
- 扩容：创建一个新的 Entry 空数组，长度是原数组的2倍；
- ReHash：遍历原 Entry 数组，把所有的 Entry 重新 Hash 到新数组。
有的朋友会问，为何要重新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；
五：JDK1.8的尾插是怎样的？
在 Java8 之后的链表引入了红黑树的部分，我们可以看到代码已经多了很多 if else 的逻辑判断，红黑树的引入巧妙地将原本 O（n）的时间复杂度降低到 O（logn）。
Tip：红黑树的部分也很重要，面试中经常会被问到，在今后写到数据结构的时候再讲。
使用头插法会改变链表上的顺序，但是如果使用尾插，在扩容时会保持链表原本的顺序，就不会出现链表成环的问题。
就是说，原本指向 A-->B，在扩容之后那个链表还是 A-->B。
Java7 的多线程操作 HashMap 时可能引起死循环，原因是扩容转移后，前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。
Java8 在同样的前提下并不会引起死循环，原因是扩容转移前后链表的顺序不变，保持之前节点的引用关系。
六：HashMap多线程的应用
上面提到，Java8不会引起死循环，是不是意味着可以把 HashMap 用在多线程中？
我认为，即使不会出现死循环，但是通过源码看到 put/get 方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒 put 的值，下一秒 get 的时候还是原值，所以线程安全还是无法保证。
七：HashMap默认初始化长度
在源码中有提示，初始化大小是16。在JDK1.8 的 235 行，这么写着 1<<4就是16，这里为何运用了位运算呢？直接写16不香吗？
因为我们在创建 HashMap 的时候，阿里规范插件会提醒我们最好赋初值，而且最好是 2 的幂。
这样是为了位运算的方便，位运算比算数计算的效率高了很多，之所以选择16，是为了服务将 Key 映射到 index 的算法。
前面说过了，所有的 Key 我们都会拿到它的 hash 值，但是我们怎么尽可能地得到一个均匀分布的 hash 值呢？
这里就需要我们通过 Key 的 HashCode 值去做位运算。
例如，key为“兄弟”的十进制为669275，那二进制就是10100011011001011011。
String key = "兄弟"; int hashCode = key.hashCode(); //669275
我们再看下index的计算公式：index = HashCode（Key）&（Length - 1）
index = （n-1）&hash
15的二进制是 1111，那 10111011000010110100 &1111 十进制就是4。
之所以用位与运算效果取模一样，性能也提高了不少！
八：为何是16,而不是其他？
因为在使用不是2的幂的数字是，Length - 1 的值是所有二进制位全为1，这种情况下，index 的结果等同于 HashCode 后几位的值。
只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。
这是为了实现均匀分布。
九：我们重写equals()方法时，为什么需要重写hashCode()方法？
在Java中，所有的对象都是继承于Object类。Object类中有两个方法 equals、hashCode，这两个方法都是用来比较两个对象是否相等的。
在未重写 equals 方法，我们是继承了 Object 的equals方法，那里的 equals是比较两个对象的内存地址，显然我们 new 了2个对象，内存地址肯定不一样。
- 对于值对象，==比较的是两个对象的值；
- 对于引用对象，比较的是两个对象的地址；
是否还记得前面说过的HashMap是通过 key 的hashCode去寻找index的，那index一样就形成了链表了，也就是说“兄弟”和“弟兄”的index都可能是2，在一个链表上。
我们去 get 的时候，他就是根据 key 去 hash，然后计算出 index，找到了 2，那我怎么找到具体的“兄弟”还是“弟兄”呢？
equals！！！是的，所以如果我们对 equals 方法进行了重写，建议一定要对 hashCode 方法重写， 以保证相同的对象返回相同的 hash 值，不同的对象返回不同的 hash 值。
不然一个链表的对象，你怎么知道你要找哪个？到时候发现 hashCode 都一样，这不完犊子了嘛。
十：既然前面说到HashMap的线程不安全，那我们应该怎么处理HashMap线程安全场景呢？
在这样的场景，我们一般都会使用 HashTable 或者 CurrentHashMap，但是因为前者的并发度的原因，基本上没什么使用场景，所以存在线程不安全的场景，我们都是用的是CurrentHashMap。
我看过 HashTable 的源码，非常简单、粗暴，直接在方法上加锁，并发度很低，最多同时允许一个线程访问；CurrentHashMap 就好很多了， 1.7 和 1.8 有较大的不同，不过并发度都比前者好很多。