JoJo的个人博客

记录精彩的程序人生

目录
HashMap
/  

HashMap

概括

HashMap 散列表,通过数组加链表的形式构成,在jdk1.8以后,当链表长度大于8的时候,会转化成红黑树的形式存储。

允许null值,同时非有序,非同步(即线程不安全)

put 方法原理

  1. 根据keyhasCode,通过哈希函数算出存储位置index值。
  2. 如果该位置没有元素,则直接存储
  3. 如果已经有了元素,就判断该元素的key值和keyhashCode是否一致,一致就直接覆盖value
  4. 如果不一致,就产生了hash冲突,就在链表上插入新的结点存储,如果链表长度大于8的话,就转化成红黑树进行存储
  5. 插入后,如果数量大于阈值则进行扩容

get 方法原理

  1. 根据keyHash映射,得到对应的index
  2. 遍历链表或者红黑树,查找key值和keyhashCode都相等的节点,返回value

HashMap 的容量为什么一定要是 2 的 n 次方

HashMap的默认初始长度是16,并且每次自动扩展或者手动初始化时,长度必须为2的幂

因为为了让元素能够均匀分配,HashMap需要将key映射到index

计算方法 index = key的hash值 & (Length - 1)keyhash值和数组的长度-1取逻辑与运算

HashMap的容量为2n次方的时候,length-1的值所有二进制位都为1,这样能让index的计算结果分布更加均匀

扰动函数(hash 函数)

在计算数组的index值的时候,并不是直接通过keyhashcodelengh-1取逻辑与运算的,这里有很多文章都是错误的讲解,需要先将hashcode通过hash函数计算出hash值,再和数组的lengh-1取逻辑与运算

///jdk1.8源码
static final int hash(Object key) {
 int h;
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

我们需要hash值是足够散列的,这样才能减少hash碰撞的概率

任意一个Objec类型的hashCode方法得到的hashCode值是一个int类型,有32位。

显然很少有HashMap的数组有40亿这么长。如果只是取低几位的hash值的话,那么那些低位相同,高位不同的hash值就碰撞了,如:

/// Hash碰撞示例:
H1: 00000000 00000000 00000000 00000101 & 1111 = 0101
H2: 00000000 11111111 00000000 00000101 & 1111 = 0101

为了解决这类问题,HashMap想了一种办法(扰动):将hash值的高16位右移并与原hash值取异或运算^,混合高16位和低16位的值,得到一个更加散列的低16位的hash值。如:

00000000 00000000 00000000 00000101 // H1
00000000 00000000 00000000 00000000 // H1 >>> 16
00000000 00000000 00000000 00000101 // hash = H1 ^ (H1 >>> 16) = 5

00000000 11111111 00000000 00000101 // H2
00000000 00000000 00000000 11111111 // H2 >>> 16
00000000 00000000 00000000 11111010 // hash = H2 ^ (H2 >>> 16) = 250

这样将hashcode通过扰动函数生成hash值,就可以减少hash碰撞的概率了

负载因子

负载因子loadFactor表示哈希表空间的使用程度,当size到达数组的容量*负载因子的时候,会触发扩容

当负载因子越大,则HashMap的装载程度就越高。也就是能容纳更多的元素,元素多了,发生hash碰撞的几率就会加大,从而链表就会拉长,此时的查询效率就会降低。

当负载因子越小,则链表中的数据量就越稀疏,此时会对空间造成浪费,但是此时查询效率高。

扩容机制

条件: HashMap.Size >= Capacity * LoadFactor

步骤:

1. 扩容

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

2. ReHash

遍历原Entry数组,把所有的Entry重新Hash到新数组。为什么要重新Hash呢?因为长度扩大以后,index的计算规则也会改变,需要重新计算分布

HashMap 为什么是非线程安全的

  1. a线程准备插入的时候,线程阻塞,b线程插入成功,a线程继续运行的话,会覆盖b线程的值

  2. ReHash在并发的情况下可能会形成链表环(java8之前)

头插法和尾插法

java8之前是头插法,java8之后是尾插法

使用头插法,在高并发的场景下会出现链表成环的问题,导致CPU利用率接近100%

使用头插会改变链表的上的顺序,但是如果使用尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了

为啥我们重写 equals 方法的时候需要重写 hashCode 方法呢

如何重写了equals方法,会导致原先不相同的两个对象,现在相同了,但是他们的hashcode还是不相同,违背了相同的对象返回相同的 hash 值,不同的对象返回不同的 hash 值的设计初衷

使用HashMap时,谨慎使用可变对象作为key键

如果key对象是可变的,那么key的哈希值就可能改变。在HashMap中可变对象作为Key会造成数据丢失。因为我们再进行hash & (length - 1)取模运算计算位置查找对应元素时,位置可能已经发生改变,导致数据丢失

最好选择不可变对象作为key。例如StringInteger等不可变类型作为key是非常明智的

树的链表还原阈值为什么是6

链表树化阀值是8,那么树还原为链表为什么是6而不是7呢?这是为了防止链表和树之间频繁的转换。如果是7的话,假设一个HashMap不停的插入、删除元素,链表个数一直在8左右徘徊,就会频繁树转链表、链表转树,效率非常低下

HashMap 和 HashTable 的区别

  1. HashMap 的 key 和 value 都允许为 null,Hashtable 的 key 和 value 都不允许为 null
  2. HashMap 的初始化容量为 16,并且容器容量一定是 2 的 n 次方,扩容时,是以原容量 2 倍 的方式 进行扩容。Hashtable 初始化容量为 11 扩容时,是以原容量 2 倍 再加 1 的方式进行扩容。即int newCapacity = (oldCapacity << 1) + 1
  3. 散列分布方式
    • HashMap是先将key键的hashCode经过扰动函数扰动后得到hash值,然后再利用 hash & (length - 1)的方式代替取模,得到元素的存储位置
    • Hashtable则是除留余数法进行计算存储位置的(因为其默认容量也不是2n次方。所以也无法用位运算替代模运算),int index = (hash & 0x7FFFFFFF) % tab.length
  4. 线程安全
    • HashMap 不是线程安全,如果想线程安全,可以通过调用synchronizedMap(Map m)使其线程安全。但是使用时的运行效率会下降,所以建议使用ConcurrentHashMap容器以此达到线程安全。
    • Hashtable则是线程安全的,每个操作方法前都有synchronized修饰使其同步,但运行效率也不高,所以还是建议使用ConcurrentHashMap容器以此达到线程安全。

Hashtable是一个遗留容器,如果我们不需要线程同步,则建议使用HashMap,如果需要线程同步,则建议使用ConcurrentHashMap

参考文章

漫画:什么是 HashMap?

JAVA 容器-自问自答学 HashMap

详解 HashMap 中的 Hash 算法(扰动函数)


标题:HashMap
作者:SunnySky
地址:https://www.tianyang.pub/articles/2020/06/01/1591001996808.html

评论