解释一下 HashMap 的工作原理

4,815 total views, 3 views today

HashMap 概述

HashMap 是基于散列表的数据结构。所谓散列表,它通过键值对的方式存储数据,把 key 通过散列算法计算出一个存储地址,将 value 放入这个地址中。散列表是最常用的数据结构之一,在不考虑 hash 冲突的情况下,散列表的查询复杂度是 O(1)。

HashMap 的数据结构

Java 中,HashMap 是基于数组和链表来实现的,也许有人会奇怪,为什么不是用一个数组,不同的 hash 值对应数组中不同的位置。
其实,链表是用来解决 hash 冲突的。数组的长度有限,不同的 key 值,通过 Hash 算法也有可能算出同样的值,这就是 Hash 冲突的产生的原因,当一个地址,对应了多个值的时候,就把这些值放到链表中去,因此 Hash 冲突会使得查找费时间。

所以,有一种攻击手段,通过精心设计的 key 值,使得所有的 key 计算出的 hash 值都是同一个,即所有的 key 值都是冲突的,这样的话,所有的元素都放在一个链表里,Hash 表就变成了一个单链表,查询元素时必须遍历这个链表,使得性能大大降低。

 

Java 中,HashMap 默认的数组大小是 16,当满足一定条件的时候,这个数组会自动扩容,并且是按但并不是有了 16 个元素之后才扩容,而是根据加载因子来计算,默认是 0.75,即一旦元素数量大于 16*0.75 时,HashMap 会自动扩容,扩容到原先的 2 倍大小,这一步是很费时间的,因此,尽量合理的设计初始容量和加载因子。

在 Java8 之后,HashMap 进一步优化 Hash 冲突,冲突的元素不再是简单的放入链表中,而是根据当链表长度,当长度太长(默认超过 8)时,链表就转换为红黑树,红黑树的查询复杂度比链表低很多。

HashMap 中的 Hash 算法

自行查资料把,网上很多的。反正当时看懂了,几天后就会忘记了。

关于 HashMap 的面试题

1.HashMap 的键值对是否可空?

HashMap 键值对皆可 null。

2.HashMap 是否线程安全?

HashMap 线程不安全。

3. 为什么说 HashMap 线程不安全?

在 resize 的时候,多线程同时操作 HashMap 中的链表时,有一定的几率形成循环链表,这就导致了获取值的时候陷入循环链表,造成死循环。具体细节,有兴趣的可以看网上的各种分析。

网上有几个文章说的比较清楚的,可以参考:

https://tech.meituan.com/java_hashmap.html
http://yikun.github.io/2015/04/01/Java-HashMap 工作原理及实现/

原创文章,转载请注明出处!http://www.javathings.top/解释一下hashmap的工作原理/

About: wusq


发表评论

邮箱地址不会被公开。 必填项已用*标注