写点什么

java 基础集合之 HashMap

用户头像
false℃
关注
发布于: 2021 年 04 月 13 日

1、 HashMap 介绍

HashMap 是开发中常用的数据结构,其以键值对的存储数据,接下来我们看下 hashmapde 数据结构、底层实现原理。主要介绍下下面的几方面,底层数据结构、扩容机制、寻址算法和 hash 算法、在 1.7 下的死锁问题

2、 底层数据结构

在 1.7 中由数组和链表构成,hash 存在概率性,不可避免的存在冲突,链表其实在 hash 冲突情况的下产物,在 jdk1.8 之前采用头插法,此时就形成了链表。在一些极端情况下,hash 冲突严重,会造成链表过长,此时查找效率严重降低。所以在 jdk1.8 引入了红黑树,当链表过长的情况下转化为红黑树。

3、 扩容机制、寻址算法、hash 算法

以 put 为入口理解下相关的原理寻址算法和 hash 算法 public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}


通过 hash(hey)计算 hash 值 static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}


  Hash计算主要有两个重点,计算出hash值,然后进行右移16位;在与原来的值进行抑或,其实就是hash高16位和低16位进行抑或,可以有效的减少hash冲突。
复制代码


为什么不直接用 hashCode() 而是用它的高 16 位进行异或计算新 hash 值?int 类型占 32 位,可以表示 2^32 种数(范围:-2^31 到 2^31-1),而哈希表长度一般不大,在 HashMap 中哈希表的初始化长度是 16(HashMap 中的 DEFAULT_INITIAL_CAPACITY),如果直接用 hashCode 来寻址,那么相当于只有低 4 位有效,其他高位不会有影响。这样假如几个 hashCode 分别是 2^10、2^20、2^30,那么寻址结果 index 就会一样而发生冲突,所以哈希表就不均匀分布了。为了减少这种冲突,HashMap 中让 hashCode 的高位也参与了寻址计算(进行扰动),即把 hashCode 高 16 位与 hashCode 进行异或算出 hash,然后根据 hash 来做寻址。扩容机制:HashMap 底层主要结构是数组,而数组必须开辟连续的空间;达到一定长度后会触发扩容机制,也就是 resize。主要有两个因素● Capacity:HashMap 当前长度。● LoadFactor:负载因子,默认值 0.75f。怎么理解呢,当你当前容量是 16,存进第 13 的元素的时候,判断需要进行 resize。


扩容?它是怎么扩容的呢?


  • 扩容:创建一个新的 Entry 空数组,长度是原数组的 2 倍。

  • ReHash:遍历原 Entry 数组,把所有的 Entry 重新 Hash 到新数组。为甚需要重新 hash 一遍,因为此时数组长度不一样,需要计算位置。

取模

(1)(n-1)&hash=.(1)hash % (n-1) (1)保证了位运算的效率,(2)保证了范围在数组范围内,所以 2 必须为 2 的 n 次幂。


负载因子为什么默认值 0.75f。如果太大,hash 冲突的可能性随之提高;太小有点浪费空间,这是在经验中取得一个平衡值。


红黑树当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间,8 是经过开发和实际经验来采用的。


头插是 JDK1.7 的那 1.8 的尾插是怎么样的呢?使用头插会改变链表的上的顺序,但是如果使用尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。就是说原本是 A->B,在扩容后那个链表还是 A->B


Java7 在多线程操作 HashMap 时可能引起死循环,原因是扩容转移后前后链表顺序倒置,在转移过程中修改了原来链表中节点的引用关系。

Java8 在同样的前提下并不会引起死循环,原因是扩容转移后前后链表顺序不变,保持之前节点的引用关系。


发布于: 2021 年 04 月 13 日阅读数: 20
用户头像

false℃

关注

还未添加个人签名 2018.11.13 加入

还未添加个人简介

评论

发布
暂无评论
java基础集合之HashMap