HashMap
实现原理
底层基于数组+链表实现，元素存储的位置基于hash算法，计算出要存储元素的数组下标，如果该下标有值，则放入该下班对应的链表中。查找时，根据key的hashcode得到数组下标，再查找链表中key相同的值返回即可。
简而言之，核心是采用数组的存储方式，并将出现hash冲突的key放入链表，发现冲突就在链表中进行对比
哈希算法：将任意长度的消息压缩到一定长度的消息的消息摘要函数，不能通过散列值来确定惟一值
hash冲突：不同的消息输入通过散列函数得到相同散列值的现象叫做哈希冲突，通过链地址法解决
hash算法得到是整形int数值，代表有2的31次方个数组地址，但数组长度远远达不到，所以需要进行重写hash方法，让高低位都参与hash运算，尽量减少碰撞概率，保证存储效能。这种过程称为扰动
JDK7与JDK8实现差别
JDK7：采用数组+链表的方式存储，链表元素采用头插法，4次位运算5次异或运算得到hash值（9次扰动）
JDK8：采用数组+链表+红黑树的方式存储，链表或数新增元素采用尾插法，链表长度一旦超过8个元素，将进化成红黑树，查找时间复杂度从O(n)到Olog(n)，1次位运算和1次异或运算得到hash值（2次扰动）
扩容机制
默认数组容量为16，若指定一个容量，则hashMap将自动查找大于等于2的n次幂的容量，默认负载因子为0.75，即数组容量达到75%就行扩容
扩容过程：新建一个两倍的数组，并将元素遍历后重新计算下标放入新数组，扩展后的节点要么在原来的位置，要么是原来位置的2倍
为什么必须是2的n次幂数组长度：为了保证hash算法的有效性，因为hash算法使用了二进制操作符异或，我们知道二进制运算都是操作2的倍数
concurrentHashMap
实现原理：锁分段技术，通过每个分组都采用一个锁的方式实现线程安全，相对于hashTable锁定整个hash表锁力度更加精细，并发性能更加好，底层采用分段数组+链表实现
线程安全的保证：与原理一致，对底层数组桶采用分割（Segment）的方式作为持有锁的单位，多线程环境下，操作的数据不再同一个组内，不存在竞争现象。JDK8摒弃了分组的概念，使用了红黑树+node数组+链表的数据结构来实现，线程安全使用synchronize+CAS保证，只锁定当前链表或红黑树的首节点，只要hash不冲突，就没有并发关系
