Java的HashMap

基于hash值的K-V结构数据容器。

重要计算方法

计算key的hash值

(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)

利用hash计算tab中的位置

p = tab[i = (n - 1) & hash]

数据结构

• 初始化后HashTable为一个Node<K,V>[] table，
• 随着往里面添加键值对，table数组上可悬挂Node链表。
• 当Node链表长度binCount >= TREEIFY_THRESHOLD - 1，链表会被转变成红黑树挂在链表上。

原因：应该是从平均查找长度估算，超过了8，用折半查找的效率更好

PUT方法

1. 计算key的hashCode，并找到table上的位置。
2. 如果没用发生碰撞则直接放在table上对应位置。
3. 如果发生碰撞，检查该位置悬挂的是链表还是树
4. 如果是链表，逐一比较
   • 如果key与某节点的hashCode相同，则覆盖。
   • 链表上未发生碰撞，则添加到链表末尾。如果链表长度>=8，则进行树化。
5. 如果是树调用putTreeVal(this, tab, hash, key, value)进行查找。
6. 对数组的扩容检查。

GET方法

1. 计算key的hashCode，并找到table上的位置。
2. 检查key值与table上的节点发生碰撞。
3. 如果未发生碰撞，则根据节点类型，在红黑树或者链表上查找。

重要变化

JDK1.7 数据存储结构为TABLE数组+Entry数组
JDK1.8 数据存储结构为TABLE数组+(Entry数组/红黑树)

历史问题

HashTable的设计理念本就不适合应用于多线程环境中，但是那些面试题强行会提一些问题，就是HashTable的线程安全方面的缺陷。简而言之，HashMap在resize()的时候，头插法多线程无序执行产生循环链表；后面JDK8优化，resize()已经改为尾插法了，避免了死循环的问题，不过还是没解决数据丢失的问题。