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时，建一棵红黑树，解决严重冲突时的性能问题。
网友评论