前言
前面我们讨论了HashMap的结构, 接下来几篇我们从源码角度来看HashMap的实现细节.
本篇我们就来聊聊HashMap的hash算法
本文的源码基于 jdk8 版本.
hash算法
上一篇文章我们提到, 为了利用数组索引进行快速查找, 我们需要先将 key值映射成数组下标. 因为数组的下标是有限的集合, 所以我们可以先通过hash算法将key映射成整数, 再将整数映射成有限的数组下标:
Object -> int -> index
对于 Object -> int 部分, 使用的就是hash function, 而对于 int -> index 部分, 我们可以简单的使用对数组大小取模来实现.
下面我们就来看看HashMap使用了什么hash算法.
首先我们来看维基百科对于hash function的定义:
散列函数(英语：Hash function)又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值(hash values，hash codes，hash sums，或hashes)的指纹。
在java中, hash函数是一个native方法, 这个定义在Object类中, 所以所有的对象都会继承.
public native int hashCode();
因为这是一个本地方法, 所以我们无法看到它的具体实现, 但是从函数签名上可以看出, 该方法将任意对象映射成一个整型值.调用该方法, 我们就完成了 Object -> int的映射
所以将 key映射成index 的方式可以是
key.hashCode() % table.length
那么HashMap是这样做的吗? 事实上, HashMap定义了自己的散列方法:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
我们知道, int类型是32位的, h ^ h >>> 16 其实就是将hashCode的高16位和低16位进行异或, 这充分利用了高半位和低半位的信息, 对低位进行了扰动, 目的是为了使该hashCode映射成数组下标时可以更均匀, 详细的解释可以参考这里.
另外, 从这个函数中, 我们还可以得到一个意外收获:
HashMap中key值可以为null, 且null值一定存储在数组的第一个位置.
性能提升
前面我们提到, 将hash值转换成数组下标我们可以采用取模运算, 但是取模运算是十分耗时的.
另一方面, 我们知道, 当一个数是 2^n 时, 任意整数对2^n取模等效于:
h % 2^n = h & (2^n -1)
这样我们就将取模操作转换成了位操作, 而位操作的速度远远快于取模操作.
为此, HashMap中, table的大小都是2的n次方, 即使你在构造函数中指定了table的大小, HashMap也会将该值扩大为距离它最近的2的整数次幂的值. 这在我们下面分析构造函数的时候就能看到了.
(完)
查看更多系列文章：系列文章目录
转播
