Java的HashMap

HashMap

HashMap原理？

Hash是一个用于存储key-value键值对的集合，每个键值对也叫Entry，这些Entry分散存储在一个数组当中，每个元素初始值都是Null，常用方法有put,get

put原理？

put(1,"A")

1）计算数组下标index=Hash(1)=hashcode(1)&(capacity-1)

2）插入数组talbe[index].value="A"

3）如果table[index]这个位置已经有值了，用链表来解决(Java8改用红黑树实现了)

table[index]->next.value="A"

get原理？

get(1, "A")

1）计算数组下标index=Hash(1)

2）从数组中获取数据table[index]

3）如果这个index存在冲突，需要遍历该处链表，比对key

HashMap初始长度？

默认初始长度是16，每次自动扩展或是手动初始化时必须是2的幂。为什么呢？

根据key计算数组下标用到一个Hash函数，要保证通过Hash函数得到的数组下标均匀分布，这样HashMap在put,get时才会更高效。计算数组下标的公式是：

index = hashcode(key) & (capacity-1)

# capacity是hashmap中数组的长度，假设使用默认长度
key   hashcode(key)                           capacity-1  index
1     49(0011 0001)                            1111       1 
a     97(110 0001)                             1111       1
book  3029737(00101110001110101110 1001)       1111       9
apple 93029210(010110001011100000110101 1010)  1111       10
# 保证HashMap数组长度是2的幂可保证capacity-1的二进制全是1，
# 如果hash函数是均匀的话，得到的index也是均匀的

如何扩容？

1）判断是否扩容

# 满足下列条件就需要扩容了
HashMap.Size >= Capacity * LoadFactor

# HashMap.Size表示HashMap中含有的元素个数
# Capacity表示HashMap中数组的长度
# LoadFactor表示负载因子，默认值为0.75f

2）Resize

创建一个空数组，长度为原数组的2倍。

Capacity = 2 * Capaicty

3）Rehash

数组长度变了，所以每个元素的数组下标也有可能会变，所以需要重新计算并添加到新的数组中。

非线程安全

并发下的Rehash可能产生条件竞争导致环形链接。具体分析看参考链接。

看参考文章中的分析能说出来，但是自己写还是写不出来。

与Java8的HashMap有什么不同

存在哈希冲突的情况，比如两个哈希值取模后落在同一个index，或者两条不同的key有相同的哈希值。

JDK7的做法是建一条链表，后插入的元素在上面，一个个地执行上面的判断。

而JDK8则在链表长度达到8，而且桶数量达到64时，建一棵红黑树，解决严重冲突时的性能问题。

参考

疫苗：JAVA HASHMAP的死循环 - 酷壳

漫画：什么是HashMap？

漫画：高并发下的HashMap

HashMap完全解读-HollisChuang's Blog

Java HashMap工作原理及实现 | Yikun

HashMap的工作原理 - ImportNew