深入了解HashMap的底层原理

各位java开发的同学肯定对HashMap并不陌生，它是一种非常常见的数据结构，可是大家真的对它十分了解吗？知道它底层设计的原型和思路吗？

• 什么是HashMap
  HashMap是一个存储K-V键值对的集合，每一个键值对叫做Entry。这些键值对存储在一个数组当中，这个数组就是HashMap的主要组成部分。
  使用HashMap主要的方法有两个Put()和Get()。
  1.Put方法的原理
  当调用Put方法时需要使用Hash函数来确定Entry在数组中的位置（index）
  index=Hash("XX")
  假设index是0，则把“XX”放到数组的第一个位置上。
  但是如果随着数据的不断增多，就很容易出现相同的index，这样就需要通过使用链表来解决index冲突的问题。因此HashMap数组的每一个元素既是一个Entry对象也是链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。这样如果index再冲突的时候，只需要插入到对应的链表下即可。
  2.Get方法原理
  使用Get方法时传入key来获取value时，同样会使用Hash函数对key做一次hash映射，得到对应的index，通过index去数组对应的位置上取第一个值和key做比较，如果不是想要的key则顺着链表取下一个值，直到得到正确的结果。

• 为什么老是说HashMap是线程不安全的
  HashMap的容量是有限的，在经过多次元素的插入后，key的hash映射发生冲突的几率就逐渐提高。这个时候就需要扩展HashMap的长度，也就是进行Resize。
  Resize的步骤
  1.扩容
  扩容就是创建一个新的Entry空数组，长度是原来数组的两倍。
  2.ReHash
  ReHash的时候会首先遍历原来的数组，把原来数组所有的Entry重新Hash到新的数组中。为啥需要把以前的Entry重新Hash一遍呢，因为在数组的长度增加后，Hash的规则也相应发生变化。
  此时如果此HashMap达到了Resize的临界值，而同时有多个线程在对此HashMap做插入操作时就有可能使HashMap的链表出现环形链表，程序就会进入死循环（具体出现环形链表的条件比较苛刻，而且流程非常烧脑）。

• 线程安全的ConcurrentHashMap
  ConcurrentHashMap是HashMap的升级版，同时兼顾了线程安全和运行的效率。
  ConcurrentHashMap的设计包含了一个非常重要的数据结构Segment
  1.什么是Segment
  Segment本身就是一个HashMap对象，Segment包含一个HashEntry数组，数组中的每一个HashEntry既是一个键值对，也是链表的头结点。
  2.ConcurrentHashMap设计的好处
  每一个Segment都相当于一个自治区，读和写高度自治，每一个Segment之间互不影响。每一个Segment的写入是上锁的，因此对同一个Segment的并发写入会被阻塞。这样既保证了线程安全又降低了锁的粒度，使并发操作的效率更高。
  3.ConcurrentHashMap具体的读写流程
  Get()方法
  （1）：为输入的Key做Hash运算，得到hash值。
  （2）：通过hash值，定位到对应的Segment对象。
  （3）：再次通过hash值，定位到Segment当中数组的具体位置。
  Put()方法
  （1）：为输入的Key做Hash运算，得到hash值。
  （2）：通过hash值，定位到对应的Segment对象
  （3）：再次通过hash值，定位到Segment当中数组的具体位置。
  （4）：插入或覆盖HashEntry对象。
  （5）：释放锁。