java篇-HashMap

我的博客java篇-HashMap

概括

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

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

put 方法原理

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

get 方法原理

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

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

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

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

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

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

扰动函数（hash 函数）

在计算数组的index值的时候，并不是直接通过key的hashcode和lengh-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之后是尾插法

使用头插法，在高并发的场景下会出现链表成环的问题

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

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

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

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

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

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

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则是除留余数法进行计算存储位置的（因为其默认容量也不是2的n次方。所以也无法用位运算替代模运算），int index = (hash & 0x7FFFFFFF) % tab.length
4. 线程安全
   • HashMap 不是线程安全，如果想线程安全，可以通过调用synchronizedMap(Map m)使其线程安全。但是使用时的运行效率会下降，所以建议使用ConcurrentHashMap容器以此达到线程安全。
   • Hashtable则是线程安全的，每个操作方法前都有synchronized修饰使其同步，但运行效率也不高，所以还是建议使用ConcurrentHashMap容器以此达到线程安全。

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

参考文章

漫画：什么是 HashMap？

JAVA 容器-自问自答学 HashMap

详解 HashMap 中的 Hash 算法（扰动函数）