原创

JDK1.8 HashMap 总结

概论

  • HashMap 是无论在工作还是面试中都非常常见常考的数据结构。比如 Leetcode 第一题 Two Sum 的某种变种的最优解就是需要用到 HashMap 的,高频考题 LRU Cache 是需要用到 LinkedHashMap 的。
  • 随着JDK(Java Developmet Kit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩容的优化等。
  • HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。
  • HashMap最多只允许一条记录的键为null,允许多条记录的值为null。
  • HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。

Hasmap 的继承关系

file

Hashmap 的原理

1、对于 HashMap 中的每个 key,首先通过 hash function 计算出一个 hash 值,这个hash值经过取模运算就代表了在 buckets 里的编号 buckets 实际上是用数组来实现的,所以把这个hash值模上数组的长度得到它在数组的 index,就这样把它放在了数组里。
2、如果果不同的元素算出了相同的哈希值,那么这就是哈希碰撞,即多个 key 对应了同一个桶。这个时候就是解决hash冲突。
3、随着插入的元素越来越多,发生碰撞的概率就越大,某个桶中的链表就会越来越长,直到达到一个阈值,HashMap就受不了了,为了提升性能,会将超过阈值的链表转换形态,转换成红黑树的结构,这个阈值是 8 。也就是单个桶内的链表节点数大于 8 ,就会将链表有可能变身为红黑树。(树化的条件是:桶中链表的长度达到了8,并且数组的长度大于等于64。)

解决Hash冲突的方法

开放定址法

这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:

Hi=(H(key)+di)% m i=1,2,…,n

其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有三种 线性探测再散列,二次探测再散列,伪随机探测再散列.

再哈希法

这种方法是同时构造多个不同的哈希函数

Hi=RH1(key) i=1,2,…,k

当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间.

链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。

链地址法适用于经常进行插入和删除的情况。

建立公共溢出区

这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。

Hashmap 最终的形态

HashMap主体上就是一个数组结构,每一个索引位置英文叫做一个 bin,我们这里先管它叫做桶,比如你定义一个长度为 8 的 HashMap,那就可以说这是一个由 8 个桶组成的数组。

当我们像数组中插入数据的时候,大多数时候存的都是一个一个 Node 类型的元素,Node 是 HashMap中定义的静态内部类。
file

在集合初始化时,指定集合初始值大小。

见《阿里编程规范》第一章 1.5集合处理章节第9条。

  • 在需要存储的数据个数确定的情况下,指定集合初始值大小。
  • initialCapacity = (需要存储的元素个数 / 负载因子) + 1.

对红黑树的理解

  • 1、每个节点非红即黑
  • 2、根节点总是黑色的
  • 3、如果节点是红色的,则它的子节点必须是黑色的(反之不一定)
  • 4、每个叶子节点都是黑色的空节点(NIL节点)
  • 5、从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)
    红黑树的见解.jpg

如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?

默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。这个值只可能在两个地方,一个是原下标的位置,另一种是在下标为<原下标+原容量>的位置。

重新调整HashMap大小存在什么问题吗?

  • 当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。(多线程的环境下不使用HashMap)
  • 为什么多线程会导致死循环,它是怎么发生的?
    • HashMap的容量是有限的。当经过多次元素插入,使得HashMap达到一定饱和度时,Key映射位置发生冲突的几率会逐渐提高。这时候,HashMap需要扩展它的长度,也就是进行Resize。
      • 1.扩容:创建一个新的Entry空数组,长度是原数组的2倍。
      • 2.ReHash:遍历原Entry数组,把所有的Entry重新Hash到新数组。

链表法导致的链表过深问题为什么不用二叉查找树代替

之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。

而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。

JDK8中对HashMap做了哪些改变?

  • 在 JDK1.8中,如果链表的长度超过了8,那么链表将转换为红黑树。(桶的数量必须大于64,小于64的时候只会扩容)

  • 发生hash碰撞时,JDK 1.7 会在链表的头部插入,而 JDK1.8会在链表的尾部插入

  • 在 JDK1.8中,Entry被Node替代

Hashmap 的容量大小为什么要求是2^n?

前提

元素在数组中的位置的计算方式是: tab[i = (n - 1) & hash] 。也就是通过对数组大小求模得到的,因为我们知道hash 的计算方式是 hashCode() 的高 16 位异或低 16 位实现的,32 位值只要有一位发生改变,整个 hash() 返回值就会改变,也就是说我们的hash 值发生冲突的概率是比较小的,也就是说hash 值是比较随机的。

冲突发生时

更多的冲突是发生在取模的时候,所以这个时候只要保证了我们的取模运算 (n - 1) & hash,尽量能保证hash 值的特性也就是随机性。因为我们知道与运算的特点是,两位同时为“1”,结果才为“1”,否则为0。

这个时候我们只要 (n - 1) 让的二进制表示都是一串1,例如"011111" 就可以了,因为安位与1 结果是不变的,也就是可以延续hash 值的散列性。

2n次方的二进制表示

2的6次方,就是从右向左 6 个 0,然后第 7 位是 1。
file

why?

只有数组的长度是2的次方了,n-1 的二进制才能尽可能多的是1 !

你觉得Hashmap 还有什么可以改进的地方吗,欢迎讨论

虽然java 源代码的山很高,如果你想跨越,至少你得有登山的勇气,这里我给出自己的一点点愚见,希望各位不吝指教

正文到此结束
广告是为了更好的提供数据服务
本文目录