Hashmap：
数组+链表
通过hash函数计算下标值
哈希冲突解决办法：开放寻址法，再散列函数法，链地址法
HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对
Entry里面存了key value hash next
默认16 到达加载因子0.75 每次翻倍
为什么大小一定是2的整数次幂：
因为数组下表index = h&(length-1)，保证index一定在数组范围内
每次扩容后只要最左位为0，就能保证索引值一致
高位也不会对计算产生影响，低位更加散列
重写equals方法的时候要重写hashcode方法，不然可能导致存取的时候hashcode值不相等找不到对应的索引值
Hashtable：
底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低，ConcurrentHashMap做了相关优化
初始size为11，扩容：2*n+1
计算index的方法：index = (hash & 0x7FFFFFFF) % tab.length
ConcurrentHashMap
底层采用分段的数组+链表实现，线程安全
通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。)
Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术
有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁
扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容
