HashMap

HashMap是由数组和链表组合构成的数据结构。

大概如下，数组里面每个地方都存了Key-Value这样的实例，在Java1.7叫Entry，在Java1.8中叫Node。

因为它本身所有位置都为null，在put插入的时候会根据key的hash去计算一个index值。

就比如我put（“rubenwei”,666），我插入了为"rubenwei"的元素，这个时候我们会通过哈希函数计算出插入的位置，如果计算出来index是2，那就放在第三个位置

但我们知道数组长度是有限的，在有限的长度里面我们使用哈希，哈希本身就存在概率性，就是"rubenwei"和“ruben”我们都去hash有一定的概率计算出来的hashcode是重复的，这时候如果put“ruben”就会在当前entry节点下形成一个链表用于存放hashcode一样的这些元素

每一个节点都会保存自身的hash、key、value以及（next）下个节点

java8之前采用头插法，原有的值顺推到链表中去，新来的值变成链表表头，是因为代码作者认为新来的值会被查找的可能性大一点，为了提升查找的效率设计的

java8之后改用尾插法，当hashmap里数据插入达到一定值的时候【这个值可以通过Capacity(当前长度)*LoadFactor(负载因子，默认0.75f)计算得到】

扩容的时候分为两步，先创建一个长度为原有数组的两倍的空数组，再调用rehash遍历原有entry数组，把所有的entry重新hash到新数组

因为扩容的时候，Capacity会改变，所以不能直接复制

改用尾插法的原因：

因为hashmap是线程不安全的，所以如果多线程同时进行插入，此时又触发了扩容机制的时候，可能会导致环形链表，此时如果对它取值会导致死循环

因此java8之后改成了尾插法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了

而且改用了红黑树，降低了时间复杂度

hashmap是线程不安全的，原因是put/get都没有加同步锁，多线程容易发生上一秒put的值，下一秒get就变了

hashmap初始化默认长度是16，因为1对4执行位运算就是16，位运算比算术计算的效率高了很多，所以选择2的幂，是为了实现均匀分布

重写equals时重写hashcode，是因为我们得通过这个hashcode方法去计算出我们在数组的哪个位置，然后通过equals去找到具体在链表的哪个位置

一般在需要线程安全的场景，我们用HashTable或者ConcurrentHashMap，但是因为HashTable的并发度原因，基本没什么使用场景了，所以一般使用ConcurrentHashMap

HashTable直接在方法上加锁，最多同时只能有一个线程操作，效率极低，ConcurrentHashMap则在效率上胜之