写点什么

了解 HashMap 数据结构,超详细!

发布于: 2020 年 10 月 23 日
了解HashMap数据结构,超详细!

写在前面

小伙伴儿们,大家好!今天来学习HashMap相关内容,作为面试必问的知识点,来深入了解一波!

思维导图:

学习框架图

1,HashMap集合简介

HashMap基于哈希表的Map接口实现,是以key-value存储形式存在,即主要用来存放键值对。HashMap的实现不是同步的,这意味着它不是线程安全的。它的key、value都可以为null。此外,HashMap中的映射不是有序的。

JDK1.8之前的HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了节解决哈希碰撞(两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同)而存在的(“拉链法”解决冲突)。

JDK1.8之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(或者红黑树的边界值,默认为8)并且当前数组的长度大于64时,此时此索引位置上的所有数据改为使用红黑树存储。

数组里面都是key-value的实例,在JDK1.8之前叫做Entry,在JDK1.8之后叫做Node。

key-value实例

由于它的key、value都为null,所以在插入的时候会根据key的hash去计算一个index索引的值。计算索引的方法如下:

/**
* 根据key求index的过程
* 1,先用key求出hash值
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//2,再用公式index = (n - 1) & hash(n是数组长度)
int hash=hash(key);
index=(n-1)&hash;

这里的Hash算法本质上就是三步:取key的hashCode值、高位运算、取模运算。

这样的话比如说put("A",王炸),插入了key为"A"的元素,这时候通过上述公式计算出插入的位置index,若index为3则结果如下(即hash("A")=3):

那么,HashMap中的链表又是干什么用的呢?

大家都知道数组的长度是有限的,在有限的长度里面使用哈希函数计算index的值时,很有可能插入的k值不同,但所产生的hash是相同的(也叫做哈希碰撞),这也就是哈希函数存在一定的概率性。就像上面的K值为A的元素,如果再次插入一个K值为a的元素,很有可能所产生的index值也为3,也就是即hash("a")=3;那这就形成了链表,这种解决哈希碰撞的方法也叫做拉链法。

当这个链表长度大于阈值8并且数组长度大于64则进行将链表变为红黑树。

补充:

将链表转换成红黑树前会判断,如果阈值大于8,但是数组长度小64,此时并不会将链表变为红黑树。而是选择进行数组扩容。

这样做的目的是因为数组比较小,尽量避开红黑树结构,这种情况下变为红黑树结构,反而会降低效率,因为红黑树需要进行左旋,右旋,变色这些操作来保持平衡。同事数组长度小于64时,搜索时间相对快一些。所以综上所述为了提高性能和减少搜索时间,底层在阈值大于8并且数组长度大于64时,链表才转换为红黑树。具体可以参考treeifyBin方法。

当然虽然增了红黑树作为底层数据结构,结构变得复杂了,但是阈值大于8并且数组长度大于64时,链表转换为红黑树时,效率也变得更高效。

特点:

  1. 存取无序的

  2. 键和值位置都可以是null,但是键位置只能是一个null

  3. 键位置是唯一的,底层的数据结构控制键的

  4. jdk1.8前数据结构是:链表 + 数组  jdk1.8之后是 :链表 + 数组  + 红黑树

  5. 阈值(边界值) > 8 并且数组长度大于64,才将链表转换为红黑树,变为红黑树的目的是为了高效的查询。

2,HsahMap底层数据结构

2.1,HashMap存储数据的过程

每一个Node结点都包含键值对的key,value还有计算出来的hash值,还保存着下一个 Node 的引用 next(如果没有下一个 Node,next = null),来看看Node的源码:

static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
...
}

HashMap存储数据需要用到put()方法,关于这些方法的详解,我们下节再说,这里简要说一下;

public static void main(String[] args) {
HashMap<String,Integer> hmap=new HashMap<>();
hmap.put("斑",55);
hmap.put("镜",63);
hmap.put("带土",25);
hmap.put("鼬",9);
hmap.put("佐助",43);
hmap.put("斑",88);
System.out.println(hmap);
}

当创建HashMap集合对象的时候,在jdk1.8之前,构造方法中会创建很多长度是16的Entry[] table用来存储键值对数据的。在jdk1.8之后不是在HashMap的构造方法底层创建数组了,是在第一次调用put方法时创建的数组,Node[] table用来存储键值对数据的。

比方说我们向哈希表中存储"斑"-55的数据,根据K值("斑")调用String类中重写之后的hashCode()方法计算出值(数量级很大),然后结合数组长度采用取余((n-1)&hash)操作或者其他操作方法来计算出向Node数组中存储数据的空间的索引值。如果计算出来的索引空间没有数据,则直接将"斑"-55数据存储到数组中。跟上面的"A-王炸"数据差不多。

我们回到上方的数组图,如果此时再插入"A-蘑菇"元素,那么首先根据Key值("A")调用hashCode()方法结合数组长度计算出索引肯定也是3,此时比较后存储的"A-蘑菇"和已经存在的数据"A-王炸"的hash值是否相等,如果hash相等,此时发生hash碰撞。

那么底层会调用"A"所属类String中的equals方法比较两个key内容是否相等,若相等,则后添加的数据直接覆盖已经存在的Value,也就是"蘑菇"直接覆盖"王炸";若不相等,继续向下和其他数据的key进行比较,如果都不相等,则规划出一个节点存储数据。

两个结点key值比较,是否覆盖

2.2,哈希碰撞相关的问题

哈希表底层采用何种算法计算hash值?还有哪些算法可以计算出hash值?

底层是采用key的hashCode方法的值结合数组长度进行无符号右移(>>>)、按位异或(^)、按位与(&)计算出索引的

还可以采用:平方取中法,取余数,伪随机数法。这三种效率都比较低。而无符号右移16位异或运算效率是最高的。

当两个对象的hashCode相等时会怎么样?

会产生哈希碰撞,若key值内容相同则替换旧的value.否则连接到链表后面,链表长度超过阈值8就转换为红黑树存储。

何时发生哈希碰撞和什么是哈希碰撞,如何解决哈希碰撞?

只要两个元素的key计算的哈希值相同就会发生哈希碰撞。jdk8前使用链表解决哈希碰撞。jdk8之后使用链表+红黑树解决哈希碰撞。

如果两个键的hashcode相同,如何存储键值对?

hashcode相同,通过equals比较内容是否相同。相同:则新的value覆盖之前的value 不相同:则将新的键值对添加到哈希表中

2.3,红黑树结构

当位于一个链表中的元素较多,即hash值相等但是内容不相等的元素较多时,通过key值依次查找的效率较低。而jdk1.8中,哈希表存储采用数组+链表+红黑树实现,当链表长度(阀值)超过 8 时且当前数组的长度 > 64时,将链表转换为红黑树,这样大大减少了查找时间。jdk8在哈希表中引入红黑树的原因只是为了查找效率更高。

红黑树结构

JDK 1.8 以前 HashMap 的实现是 数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,这个时候 HashMap 就相当于一个单链表,假如单链表有 n 个元素,遍历的时间复杂度就是 O(n),完全失去了它的优势。针对这种情况,JDK 1.8 中引入了 红黑树(查找时间复杂度为 O(logn))来优化这个问题。当链表长度很小的时候,即使遍历,速度也非常快,但是当链表长度不断变长,肯定会对查询性能有一定的影响,所以才需要转成树。

2.4,存储流程图

HashMap存放数据是用的put方法,put 方法内部调用的是 putVal() 方法,所以对 put 方法的分析也是对 putVal 方法的分析,整个过程比较复杂,流程图如下:

来看看put()源码:

public V put(K key, V value) {
//对key的hashCode()做hash,调用的是putVal方法
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
/*
1,tab为空则开始创建,
2,(tab = table) == null 表示将空的table赋值给tab,然后判断tab是否等于null,第一次肯定是null
3,(n = tab.length) == 0 表示没有为table分配内存
4,tab为空,执行代码 n = (tab = resize()).length; 进行扩容。并将初始化好的数组长度赋值给n.
5,执行完n = (tab = resize()).length,数组tab每个空间都是null
*/
if ((tab = table) == null || (n = tab.length) == 0)
//调用resize()方法进行扩容
n = (tab = resize()).length;
/*
1,i = (n - 1) & hash 表示计算数组的索引赋值给i,即确定元素存放在哪个桶中
2,p = tab[i = (n - 1) & hash]表示获取计算出的位置的数据赋值给节点p
3,(p = tab[i = (n - 1) & hash]) == null 判断节点位置是否等于null,
如果为null,则执行代码:tab[i] = newNode(hash, key, value, null);根据键值对创建新的节点放入该位置的桶中
小结:如果当前桶没有哈希碰撞冲突,则直接把键值对插入空间位置
*/
if ((p = tab[i = (n - 1) & hash]) == null)
//节点位置为null,则直接进行插入操作
tab[i] = newNode(hash, key, value, null);
//节点位置不为null,表示这个位置已经有值了,于是需要进行比较hash值是否相等
else {
Node<K,V> e; K k;
/*
比较桶中第一个元素(数组中的结点)的hash值和key是否相等
1,p.hash == hash 中的p.hash表示原来存在数据的hash值 hash表示后添加数据的hash值 比较两个hash值是否相等
2,(k = p.key) == key :p.key获取原来数据的key赋值给k key表示后添加数据的key 比较两个key的地址值是否相等
3,key != null && key.equals(k):能够执行到这里说明两个key的地址值不相等,那么先判断后添加的key是否等于null,如果不等于null再调用equals方法判断两个key的内容是否相等
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
/*
说明:两个元素哈希值相等(哈希碰撞),并且key的值也相等
将旧的元素整体对象赋值给e,用e来记录
*/
e = p;
// hash值不相等或者key不相等;判断p是否为红黑树结点
else if (p instanceof TreeNode)
// 是红黑树,调用树的插入方法
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 说明是链表节点,这时进行插入操作
else {
/*
1,如果是链表的话需要遍历到最后节点然后插入
2,采用循环遍历的方式,判断链表中是否有重复的key
*/
for (int binCount = 0; ; ++binCount) {
/*
1)e = p.next 获取p的下一个元素赋值给e
2)(e = p.next) == null 判断p.next是否等于null,等于null,说明p没有下一个元 素,那么此时到达了链表的尾部,还没有找到重复的key,则说明HashMap没有包含该键
将该键值对插入链表中
*/
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//插入后发现链表长度大于8,转换成红黑树结构
if (binCount >= TREEIFY_THRESHOLD - 1)
//转换为红黑树
treeifyBin(tab, hash);
break;
}
//key值以及存在直接覆盖value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//若结点为null,则不进行插入操作
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//修改记录次数
++modCount;
// 判断实际大小是否大于threshold阈值,如果超过则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}



小结:

  1. 根据哈希表中元素个数确定是扩容还是树形化

  2. 如果是树形化遍历桶中的元素,创建相同个数的树形节点,复制内容,建立起联系

  3. 然后让桶中的第一个元素指向新创建的树根节点,替换桶的链表内容为树形化内容

3,HashMap的扩容机制

我们知道,数组的容量是有限的,多次插入数据的话,到达一定数量就会进行扩容;先来看两个问题

什么时候需要扩容?

当HashMap中的元素个数超过数组长度loadFactor(负载因子)时,就会进行数组扩容,loadFactor的默认值是0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中的元素个数超过16×0.75=12(这个值就是阈值)的时候,就把数组的大小扩展为2×16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预知元素的个数能够有效的提高HashMap的性能。

怎么进行扩容的?

HashMap在进行扩容时使用 resize() 方法,计算 table 数组的新容量和 Node 在新数组中的新位置,将旧数组中的值复制到新数组中,从而实现自动扩容。因为每次扩容都是翻倍,与原来计算的 (n-1)&hash的结果相比,只是多了一个bit位,所以节点要么就在原来的位置,要么就被分配到"原位置+旧容量"这个位置。

因此,我们在扩充HashMap的时候,不需要重新计算hash,只需要看看原来hash值新增的那个bit是1还是0就可以了,是0的话索引没变,是1的话索引变成“原索引+oldCap(原位置+旧容量)”。这里不再详细赘述,可以看看下图为16扩充为32的resize示意图:

hashmap扩容

4,HashMap数组长度为什么是2的次幂

我们先看看它的成员变量:

序列化版本号
private static final long serialVersionUID = 362498820763181265L;
集合的初始化容量initCapacity
//默认的初始容量是16 -- 1<<4相当于1*2的4次方---1*16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;



初始化容量默认是16,容量过大,遍历时会减慢速度,效率低;容量过小,那么扩容的次数变多,非常耗费性能。

负载因子
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;



初始默认值为0.75,若过大,会导致哈希冲突的可能性更大;若过小,扩容的次数也会提高。

为什么必须是2的n次幂?

当向HashMap中添加一个元素的时候,需要根据key的hash值,去确定其在数组中的具体位置。HashMap为了提高存取效率,要尽量较少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现就在把数据存到哪个链表中的算法。

这个算法实际就是取模,hash%length,计算机中直接求余效率不如位移运算。所以源码中做了优化,使用 hash&(length-1),而实际上hash%length等于hash&(length-1)的前提是length是2的n次幂。

如果输入值不是2的幂会怎么样?

如果数组长度不是2的n次幂,计算出的索引特别容易相同,及其容易发生hash碰撞,导致其余数组空间很大程度上并没有存储数据,链表或者红黑树过长,效率降低。

小结:

1,当根据key的hash确定其在数组的位置时,如果n为2的幂次方,可以保证数据的均匀插入,如果n不是2的幂次方,可能数组的一些位置永远不会插入数据,浪费数组的空间,加大hash冲突。

2,一般可能会想通过 % 求余来确定位置,这样也可以,只不过性能不如 & 运算。而且当n是2的幂次方时:hash & (length - 1) == hash % length

3,因此,HashMap 容量为2次幂的原因,就是为了数据的的均匀分布,减少hash冲突,毕竟hash冲突越大,代表数组中一个链的长度越大,这样的话会降低hashmap的性能


微信搜索公众号《程序员的时光

好了,今天就先分享到这里了,下期继续给大家带来HashMap面试内容!

更多干货、优质文章,欢迎关注我的原创技术公众号~



发布于: 2020 年 10 月 23 日阅读数: 1100
用户头像

程序员的路,会越来越精彩! 2020.04.30 加入

公众号:程序员的时光 记录学习编程的一路时光,从小白到现在也能稳操胜券; 主要从事Java后台开发,数据结构与算法,设计模式等等; 欢迎一起交流,分享经验,学习进步!

评论 (4 条评论)

发布
用户头像
2.2 第一问的回答中,”无符号右移16位异或运算效率是最高的“。这个说法固然没错,但这么做是因为只是取模运算每次取出的是低 16 位,很容易冲突。右移 16 位使高位参与运算,是为了减小 hash 碰撞几率。
2020 年 10 月 28 日 14:46
回复
您说的没错!受教了👌
2020 年 10 月 30 日 09:35
回复
用户头像
好详细
2020 年 10 月 23 日 16:38
回复
谢谢啦,后面还会继续更新的
2020 年 10 月 23 日 16:44
回复
没有更多了
了解HashMap数据结构,超详细!