HashMap
HashMap是Map接口的一个实现，用于存储键值对的集合。其主体是一个数组，数组初始值为null。
put方法
调用HashMap的put方法存入键值对时，首先调用hash函数对键值对的key进行哈希运算，结果为存储该键值对的数组index。但数组空间有限，当键值对足够多时，再完美的hash函数也可能生成冲突的index。为解决该问题，每个数组元素除了存储键值对，还会存储next指针，当多个键值对通过hash函数映射到数组同一个index时，即组成一个链表。
Get方法
调用hashMap的get方法根据key查找时，首先调用hash函数计算key对应的hash值，也就是数组index；如果该index对应多个entry，那么遍历链表寻找key对应的entry。之所以链表采用头节点插入法，是因为hashmap的设计者认为后插入的键值对查找几率更高。
hashMap数组长度
数组的默认初始长度为16，每次自动扩展或手动初始化是都需要是2的幂。选择16，是为了得到一个尽量均匀分布的hash函数，hash函数采用位运算，如下：index = HashCode（Key） & （Length - 1）。当长度为16或者2的幂时，长度-1的二进制各位都是1。这样更有利于实现均匀分布。
举例：book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001；Length-1的结果为十进制的15，二进制的1111；与运算，101110001110101110 1001 &1111 = 1001，十进制是9，所以 index=9。
举例：如果数组长度为10，10-1=9，其二进制为1001，那么1111，1001与1001进行与运算的结果是一样的，都是1001，也就违背了均匀分布的目的。
HashMap的扩容Resize
HashMap的容量是有限的。当经过多次元素插入，HashMap达到一定饱和度时，Key映射位置发生冲突的几率会逐渐提高。这时HashMap需要扩展它的长度，也就是进行Resize。衡量HashMap是否进行Resize的条件如下：HashMap.Size >= Capacity * LoadFactor；loadFactor是负载因子，默认情况下为0.75。
HashMap的扩容包括两步，第一步是创建一个原有数组两倍大小的新数组；第二步是把原有数组的键值对重新进行哈希运算并根据计算得到的index值保存在新数组。第二步又称为rehash
高并发下的HashMap
rehash的过程并非线程安全。假设一个HashMap已经到了Resize的临界点。此时有两个线程A和B，在同一时刻对HashMap进行Put操作，此时达到Resize条件，两个线程各自进行Rezie的第一步，也就是扩容：并且进行rehash，rehash的过程中多线程可能导致链表中出现环，导致死循环。避免HashMap的线程安全问题，有多种方法，比如HashTable或者synchronisedMap，但二者存在性能问题，无论是读操作还是写操作，他们都会给整个集合加锁，使得同一时间的其他操作都被堵塞。因此在高并发场景下，通常使用ConcurrentHashMap，来兼顾线程安全与性能。
ConcurrentHashMap
相对于HashMap，ConcurrentHashMap的关键词是segment。一个concurrentHashMap包含若干个segment，类似数据库的水平扩展，把map中的数据分散在若干个segment；每个segment拥有和HashMap一样的结构。每个segment独立加锁，在保证线程安全的同时降低了锁的粒度，让并发操作效率更高。
在ConcurrentHashMap执行Get方法：根据key进行二次Hash运算，先定位到segment，再定位到segment中的entry：1.为输入的Key做Hash运算，得到hash值。2.通过hash值，定位到对应的Segment对象3.再次通过hash值，定位到Segment当中数组的具体位置。
在ConcurrentHashMap执行Put方法：1.为输入的Key做Hash运算，得到hash值。2.通过hash值，定位到对应的Segment对象。3.获取可重入锁。4.再次通过hash值，定位到Segment当中数组的具体位置。5.插入或覆盖HashEntry对象。6.释放锁。
