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 时, 建一棵红黑树, 解决严重冲突时的性能问题
参考
来源: http://www.bubuko.com/infodetail-2514671.html