什么是HashMap？

一 、什么是hashmap：HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。

简单来说，HashMap是一个Entry对象的数组。数组中的每一个Entry元素，又是一个链表的头节点，每一个Entry对象通过Next指针指向它的下一个Entry节点。

  1. put方法原理： 比如调用 hashMap.put(“apple”, 0) ，插入一个Key为“apple”的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置（index）。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可。需要注意的是，新来的Entry节点插入链表时，使用的是“头插法”。之所以把新节点放在头节点，是因为HashMap的发明者认为，后插入的Entry被查找的可能性更大。
  2. get方法原理： 首先会把输入的Key做一次Hash映射，得到对应的index，然后根据index查看这个头节点，不是的话，查找下一个。

二、 Hashmap不是线程安全的。在高并发环境下做插入操作，有可能出现下面的环形链表让下一次读操作出现死循环：

_20180731140221

三、 hashmap默认的初始长度是多少？为什么这么规定？

默认长度是16，并且每次扩展的时候或者手动初始化时，长度必须是2的幂。

之所以选择16，是为了服务于从key映射到index的hash算法。

index = HashCode（Key） & （Length - 1）

下面我们以值为“book”的Key来演示整个过程：

  1. 计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001。

  2. 假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。

  3. 把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。

可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。这样做不但效果上等同于取模，而且大大提高了性能。

长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。

四、Java8中，hashmap的优化。

高并发下的HashMap

一、ReHash概念：

ReHash是hashmap在扩容时候的一个步骤。HashMap的容量是有限的。当经过多次元素插入，使得HashMap达到一定饱和度时，Key映射位置发生冲突的几率会逐渐提高。这时候，HashMap需要扩展它的长度，也就是进行Resize。

影响发生Resize的因素有两个：

1. Capacity：HashMap的当前长度。上一期曾经说过，HashMap的长度是2的幂。为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。


2. LoadFactor：HashMap负载因子，默认值为0.75f。

衡量HashMap是否进行Resize的条件如下：

HashMap.Size >= Capacity * LoadFactor

Resize的两个步骤：

1. 扩容：创建一个新的Entry空数组，长度是原数组的2倍。

2. ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。

二、高并发场景下存在的问题？就是死循环

高并发下为什么hashmap可能出现死循环？

高并发会可能会导致链表出现环形。（具体原因先不写，看源码的执行）当调用Get查找一个不存在的Key，而这个Key的Hash结果恰好等于环形链表的位置的时候，程序将会进入死循环！

1.Hashmap在插入元素过多的时候需要进行Resize，Resize的条件是HashMap.Size >= Capacity * LoadFactor.

2.Hashmap的Resize包含扩容和ReHash两个步骤，ReHash在并发的情况下可能会形成链表环。

什么是ConcurrentHashMap？

concurrenthashmap能够兼顾线程安全和运行效率。

concurrentHashMap是怎么保证线程安全的？怎么实现高性能读写的？

一、segment概念：

Segment本身就相当于一个HashMap对象。同HashMap一样，Segment包含一个HashEntry数组，数组中的每一个HashEntry既是一个键值对，也是一个链表的头节点。

像这样的Segment对象，在ConcurrentHashMap集合中有多少个呢？有2的N次方个，共同保存在一个名为segments的数组当中。

因此整个ConcurrentHashMap的结构如下：

concurrenthashmap

可以说，ConcurrentHashMap是一个二级哈希表。在一个总的哈希表下面，有若干个子哈希表。这样的二级结构，和数据库的水平拆分有些相似。

二、Segment的写入是需要上锁的，因此对同一Segment的并发写入会被阻塞。

由此可见，ConcurrentHashMap当中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度，让并发操作效率更高。

三、concurrenthashmap读写方法

  1. get方法： 1.为输入的Key做Hash运算，得到hash值。

    2.通过hash值，定位到对应的Segment对象

    3.再次通过hash值，定位到Segment当中数组的具体位置。

  2. put方法： 1.为输入的Key做Hash运算，得到hash值。

    2.通过hash值，定位到对应的Segment对象

    3.获取可重入锁

    4.再次通过hash值，定位到Segment当中数组的具体位置。

    5.插入或覆盖HashEntry对象。

    6.释放锁。

四、ConcurrentHashMap的Size方法

大体逻辑如下：

1.遍历所有的Segment。

2.把Segment的元素数量累加起来。

3.把Segment的修改次数累加起来。

4.判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是。说明没有修改，统计结束。

5.如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计。

6.再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁，次数一定和上次相等。

7.释放锁，统计结束。

这种思想和乐观锁悲观锁的思想如出一辙。为了尽量不锁住所有Segment，首先乐观地假设Size过程中不会有修改。当尝试一定次数，才无奈转为悲观锁，锁住所有Segment保证强一致性。

什么是HashTable？

hashtable是线程安全的。但是读写操作，都会给整个集合加锁，导致性能较差。现在一般已经不用hashtable了。 hashtable的key-value不允许为null。当时不允许是因为希望每个 key 都会实现 hashCode 和 equals 方法。而 null 显然没有。