Java集合-HashMap源码实现深入解析

时间:2022-09-11 17:19:56

概述

本文学习知识点

1.HashMap的存储结构怎么实现,它有什么特点。
2.HashMap的工作原理。
3.put和get方法实现源码分析。
4.hash值有什么作用?如何进行hash?equals和hashCode方法有什么作用?
5.何谓负载因子,有什么作用?
6.何时会触发扩容,以及如何扩容?

Map<String, String> map = new HashMap<String, String>();
map.put("liuyi", "刘一");
map.put("wanger", "王二");
map.put("zhangsan", "张三");
map.put("lisi", "李四");
map.put("wangwu", "王五");
map.put("zhaoliu", "赵六");
map.put("chenqi", "陈七");
map.put("yangba", "杨八");
map.put("zhoujiu", "周九");
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getValue() + "\t" + entry.getKey());
}

想想上面代码的输出结果是什么样?运行后,可能的结果是:

赵六 zhaoliu
刘一 liuyi
王五 wangwu
王二 wanger
陈七 chenqi
李四 lisi
周九 zhoujiu
张三 zhangsan
杨八 yangba

从这个结果可以窥探出,HashMap存储的顺序和迭代时读取的顺序不相同,并非有序存储。来看看底层如何存储,如下图为Eclipse debug时的存储结构:

Java集合-HashMap源码实现深入解析
从图中来看,HashMap内部用一个table(Entry元素数组)来存储元素,索引中的每个元素又采用链表的结构进行存储,用于存储相同索引的元素。其中Entry类就是一个节点类,具有链接下一个节点的功能,内部存储了元素的key,value,hash,next引用,Entry的结构如下,采用内部类的方式实现:

Java集合-HashMap源码实现深入解析

HashMap的特性

1.实现了Map接口,里面的方法全部被HashMap实现。
2.允许null键和null值。这点和Hashtable不同,Hashtable不允许。
3.非线程安全,这点也和Hashtable不同,Hashtable为线程安全的。
4.不保证有序,即元素的插入和读取顺序不保证一致,这一点从开始的示例程序和图就能看出来。
5.也不保证元素的顺序始终不变,在扩容时,元素的顺序会重新被打乱。

有两个参数能够影响HashMap的结构:

1.initial capacity:table的初始容量(并非存放元素节点的容量大小,仅仅是table表的大小),默认初始容量为16。
2.load factor:负载因子,用于确定table的容量达到多大比例时,对容量进行扩容的一个参数。默认值为0.75,即默认超过12个时开始扩容,扩容时,会重新计算所有元素的hash值(rehashed),以确定其在新table上的索引下标,因此,扩容会改变原有hashtable的结构,元素的顺序也会重新改变。每次扩容后,容量的大小都是原来的2倍。至于为什么默认负载因子设置为0.75,按照官方的API说法,是因为通常0.75能够在时间复杂度和空间复杂度上达到最好的平衡效果。在设置初始容量时应该考虑到所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。

put方法的实现 JDK1.7

put方法的步骤:
1.对key的hashcode值再计算hash。
2.用计算出的hash值,与表的length求&算出索引位置。
3.如果索引碰撞,遍历链表,判断是否有key存在,若存在更新value值。(不过在JDK1.8中链表元素超过8个时,会把链表结构转换成红黑树结构存储,提高查询的性能)
4.若未碰撞,直接放入表中。
5.放入前,如果元素个数超过负载因子的比例,则进行rehash,扩容,之会插入。
6.null key的元素永远会放到index为0的链表里面。
代码实现如下:Java集合-HashMap源码实现深入解析

Java集合-HashMap源码实现深入解析

get方法实现

步骤:
1.null key走特殊逻辑。
2.key的hashcode计算hash值。
3.hash值计算表索引。
4.遍历索引下的链表,找到就返回,找不到返回null。

Java集合-HashMap源码实现深入解析

hash方法的实现

如下为hash方法的实现源码:Java集合-HashMap源码实现深入解析
hash方法中:对key的hashCode值进行了异或,逻辑右移等多个操作,目的是尽量减小冲突。因为table的容量是2的幂,直接用hashcode,低位会很容易碰撞,因此做了多次移位和异或操作,保证高位和低位都参与到hash的计算中,减少碰撞。

计算下标的时候,是这样实现的(使用&位操作,而非%求余):
hash & (length - 1)
设计者认为这方法很容易发生碰撞。为什么这么说呢?不妨思考一下,在n - 1为15(0x1111)时,其实散列真正生效的只是低4bit的有效位,当然容易碰撞了。
时间复杂度:读取O(1) + O(n),1为找索引的时间,n为链表元素的个数。插入O(1)。所以,如果冲突很频繁,某些链表非常长,就会影响HashMap的读取速度。这一点在JDK1.8中进行了性能提升,链表长度超过8则改为红黑树的存储结构实现。

resize扩容实现

实现如下:Java集合-HashMap源码实现深入解析
步骤:
1.创建新的table。
2.将旧table的元素重新计算hash,根据hash计算新table的索引,插入新table。
3.新table覆盖原table的引用,更新threshold值为新table * 负载因子的大小。

总结


让我们来回答几个问题,以加深对HashMap的理解:

1. 什么时候会使用HashMap?他有什么特点?

是基于Map接口的实现,存储键值对时,它可以接收null的键值,是非同步的,HashMap存储着Entry(hash, key, value, next)对象。

2. 你知道HashMap的工作原理吗?

通过put和get存储和获取对象。存储对象时,我们将K/V传给put方法时,它调用hashCode计算hash从而得到table位置,进一步存储,HashMap会根据当前table的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时,我们将K传给get,它调用hashCode计算hash从而得到table位置,并进一步调用equals()方法确定键值对。如果发生碰撞的时候,Hashmap通过链表将产生碰撞冲突的元素组织起来,在Java 8中,如果一个table中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。

3. 你知道get和put的原理吗?equals()和hashCode()的都有什么作用?

通过对key的hashCode()进行hashing,并计算下标( n-1 & hash),从而获得buckets的位置。如果产生碰撞,则利用key.equals()方法去链表或树中去查找对应的节点

4. 你知道hash的实现吗?为什么要这样实现?

在Java 1.8的实现中,是通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在bucket的n比较小的时候,也能保证考虑到高低bit都参与到hash的计算中,同时不会有太大的开销。

5. 何时会触发扩容,以及如何扩容?

如果table超过了负载因子(默认0.75)比例的容量,则会重新resize一个原来长度两倍的HashMap,并且重新调用hash方法计算元素在新table的索引,并挨个插入。


白天在加班加点的干活,还要抽出时间成为技术知识的分享者,分享不易,转载请注明出处。