HashMap

HashMap特性

HashMap存储键值对实现快速存取，key不可重复，重复则覆盖。HashMap对象的key、value均可为null；HashTable对象的key、value均不可为null。
线程不安全
- 具体表现1：put的时候多线程导致数据不一致。假定线程A、B，其中A希望插入一个key-value对到HashMap，首先记录所要落到的桶的索引坐标，然后获得该桶里面的链表头节点，此时线程A的时间片用完。此时线程B开始执行，和线程A一样，只不过B成功将记录插到了桶里面。假设A计算出的桶索引与B计算出的桶索引一样，那么B插入成功之后，A再被调度执行并插入，那么B所插入额记录就会被A凭空覆盖。参考链接
- 具体表现2：jdk1.7的扩容机制resize采用头插法，新table中链表的顺序和旧链表的顺序是相反的，这种头插法在多线程时可能会导致环状节点。参考链接1，参考链接2
  
  而jdk1.8的扩容机制resize采用尾插法，无环状节点问题。（但是1.8仍存在表现1的问题）
  
  （扩容是指HashMap的整体容量要变大，不是只扩某一个桶链表的长度）
底层Hash表，不保证有序性。
底层数据结构：散列表 + 链表/红黑树。
- 通过源码可知，散列表上每个节点都记录着hash值，key值，value值。
- 链表和红黑树的作用：Hash碰撞时（不同元素通过Hash算法得到了相同的hash值），防止同一桶内的元素覆盖。链表查询复杂度为O(n)，红黑树O(log(n)).
- 链表转红黑树的阈值：链表长度 >= 8 & 散列表大小 >= 64
- 红黑树转链表的阈值：红黑树节点个数 < 6.
5.HashMap扩容时刻：存储元素个数 > 负载因子 * 当前散列数组大小。

HashMap的put实现原理

判断散列表数组table是否为空，为空进行初始化。
不为空，计算key的hash值，通过 (n-1) & hash 计算当前元素应存放在散列表数组table中的下标index （n为散列表数组大小）
查看table[index]是否存在数据，没有数据就构造一个Node节点，存放在table[index]中。
存在数据，说明hash冲突（存在两个节点的key的hash值一样），继续判断key值是否相等，相等则覆盖原value。
如果不相等，判断当前节点类型是否为树型节点，是则插入红黑树中。
不是树型节点，创建普通Node节点，加入链表。若加入后链表长度 >= 8 且散列表大小 >= 64，着手链表转红黑树。
插入完成后判断HashMap中节点数是否大于阈值，大于则开始resize扩容。

HashMap初始化大小

new HashMap()这种不传值的默认大小为16，负载因子为0.75.如果手动指定大小n，则初始化大小为大于n的2的整数次方，例如n=10，则初始化大小为16。

如何计算key的hash值/为什么计算key的hash值，不直接使用hashCode

先拿到key的hashCode，为32位int值，然后让hashCode的高16位和低16位进行异或操作。

也称为扰动函数，尽可能降低hash碰撞，越分散越好；为了尽可能高效，采用位运算。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// >>表示带符号右移，正数补0负数补1
// >>>表示不带符号右移，高位统统补0

为何散列数组的长度要取2的整数次幂

因计算元素将要放置在散列表的位置下标时，数组长度-1恰好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标。以初始长度16为例，16-1=15,，二进制为00000000 00000000 00001111.和某散列值与操作，结果就是截取了最低4位。

bucketIndex = indexFor(hash, table.length);
    
static int indexFor(int hash, int length) {
    return h & (length - 1);
}

10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
  00000000 00000000 00000101       //高位全部归零，只保留末4位

但此时问题来了，就算散列值分布再松散，若仅取最后几位，碰撞也会很严重。这时扰动函数的意义就体现出来了。

桶index计算

右移16位，正好是32bit的一半。自己高半区和低半区异或，就是为了混合原始哈希码的高位和低位，从而加大低位的随机性，使得低位掺杂了高位的部分特性。

jdk1.8对HashMap优化

将“数组+链表”改为“数组+链表/红黑树”。
链表头插改为尾插。
扩容时1.7需对原数组元素重新定位；1.8判断简化，位置不变或索引 + 旧容量大小（因扩容时原散列数组大小为原数组大小的2倍，用于计算数组位置的掩码仅仅只是高位多了一个1）

HashMap扩容后元素定位

对于HashMap线程不安全问题如何解决

使用HashTable、Collections.synchronizedMap、ConcurrentHashMap可实现线程安全的Map。

HashTable直接在实例方法上使用synchronized关键字，锁住整个散列数组，粒度较大。

Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入一个Map封装出一个SynchronizedMap对象（SynchronizedMap类实现了Map接口），该类内部定义了一个对象锁，方法内通过对象锁实现。（迭代器遍历时还是需要自己手动加锁实现）参考链接

但HashTable、Collections.synchronizedMap都是给整个集合加锁，性能一般。

ConcurrentHashMap：

jdk1.7下，ConcurrentHashMap分段Segment处理，每个Segment包含一个HashEntry数组，HashEntry数组的每个元素是链表的头节点。即ConcurrentHashMap是一个二级哈希表，采用分段锁的技术提高了并发性。
- get方法：
  1. 对输入的key做hash运算得到hash值；
  2. 通过hash值定位到对应的Segment；
  3. 再次通过hash值定位到Segment当中数组的具体位置。
- put方法：
  1. 同上；
  2. 同上；
  3. 获取重入锁；
  4. 再次通过hash值定位到Segment当中数组的具体位置；
  5. 插入或覆盖HashEntry对象；
  6. 锁释放
- size方法：
  
  先后计算两次，若计算结果一致则返回计算结果；若不一致，尝试几次，若还是不一致，则锁住所有Segment求和。参考链接
jdk1.8下，首先，CAS的实现原理，java借助C来调用CPU底层指令实现的。参考链接

jdk1.8的ConcurrentHashMap移除了Segment的概念，使用Synchronized + CAS的机制，锁粒度更小，并发效率更高。且Synchronized的优化也做的越来越好了。且与HashMap一样，1.8多了红黑树。
- get方法：与1.7类似，由于value被声明为volatile，保证了修改的可见性，因此不需要加锁。
- put方法：移除了Segment，可直接定位到桶
- size方法：baseCount…不太清楚…