Map及子类

1、hashMap

HashMap数据结构：根据key的hashCode来计算hash值，只要hashCode相同，计算出来的hash值就一样。出现hash冲突，就采用链表的方式，将相同hash值的对象用链表连接。

HashMap存取：put新元素时，首先根据key的hashCode重新计算hash值（二次hash），根据这个新的hash值得到这个元素在数组的位置（下标），如果数组已经存放其他元素，那么该位置元素以链表形式存放，新加入的放链头，最先加入的在链尾。根据Key的hashCode二次hash的算法函数hash（int h），此方法加入了高位计算，防止低位不变而高位变化时造成的hash冲突。函数的具体实现如下(>>>表示右移1位并忽略符号位，空位以0补齐。而>>表示右移不忽略符号位，即相当于除以2)：

2 ConcurrentHashMap

在HashMap的基础上,ConcurrentHashMap将数据分为多个segment，默认16个，然后每次操作对一个segment加锁，避免多线程锁的几率，提高并发效率。

3 Hashtable和HashMap的区别

HashMap父类为AbstractMap，方法不同步，K，V可为null，添加新的kv，若k相同，则将新的v覆盖。

HashTable父类为Dictionary，方法同步，k，v不可为null，添加新的kv，若k相同，则将新的v覆盖。