发表文章之后,发现很多图片显示不了,请阅读我的公众号文章,以获得本文最佳体验:
为什么Java String哈希乘数为31?
前面简单介绍了[ 经典的Times 33 哈希算法 ],这篇我们通过分析Java 1.8 String类的哈希算法,继续聊聊对乘数的选择。
String类的hashCode()源码
/** Cache the hash code for the string */
private int hash;
/**
Returns a hash code for this string. The hash code for a String object is computed as
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
using int arithmetic, where s[i] is the ith character of the string,
n is the length of the string, and ^ indicates exponentiation.
(The hash value of the empty string is zero.)
*/
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
可以看到,String的哈希算法也是采用了Times 33的思路,只不过乘数选择了31。
其中
- hash默认值为0.
- 判断h == 0是为了缓存哈希值.
- 判断value.length > 0是因为空字符串的哈希值为0.
用数据说话
前一篇我们提到:
这个神奇的数字33,为什么用来计算哈希的效果会比其他许多常数(无论是否为质数)更有效,并没有人给过足够充分的解释。因此,Ralf S. Engelschall尝试通过自己的方法解释其原因。通过对1到256中的每个数字进行测试,发现偶数的哈希效果非常差,根据用不了。而剩下的128个奇数,除了1之外,效果都差不多。这些奇数在分布上都表现不错,对哈希表的填充覆盖大概在86%。
从哈希效果来看(Chi^2应该是指卡方分布),虽然33并不一定是最好的数值。但17、31、33、63、127和129等相对其他的奇数的一个很明显的优势是,由于这些奇数与16、32、64、128只相差1,可以通过移位(如1 << 4 = 16)和加减1来代替乘法,速度更快。
那么接下来,我们通过实验数据,来看看偶数、奇数,以及17、31、33、63、127和129等这些神奇数字的哈希效果,来验证Ralf S. Engelschall的说法。
环境准备
个人笔记本,Windows 7操作系统,酷睿i5双核64位CPU。
测试数据:CentOS Linux release 7.5.1804的/usr/share/dict/words字典文件对应的所有单词。
由于CentOS上找不到该字典文件,通过yum -y install words进行了安装。
/usr/share/dict/words共有479828个单词,该文件链接的原始文件为linux.words。
计算冲突率与哈希耗时
测试代码
/**
* 以1-256为乘数,分别计算/usr/share/dict/words所有单词的哈希冲突率、总耗时.
*
* @throws IOException
*/
@Test
public void testHash() throws IOException {
List<String> words = getWords();
System.out.println();
System.out.println("multiplier, conflictSize, conflictRate, timeCost, listSize, minHash, maxHash");
for (int i = 1; i <=256; i++) {
computeConflictRate(words, i);
}
}
/**
* 读取/usr/share/dict/words所有单词
*
* @return
* @throws IOException
*/
private List<String> getWords() throws IOException {
// read file
InputStream is = HashConflictTester.class.getClassLoader().getResourceAsStream("linux.words");
List<String> lines = IOUtils.readLines(is, "UTF-8");
return lines;
}
/**
* 计算冲突率
*
* @param lines
*/
private void computeConflictRate(List<String> lines, int multiplier) {
// compute hash
long startTime = System.currentTimeMillis();
List<Integer> hashList = computeHashes(lines, multiplier);
long timeCost = System.currentTimeMillis() - startTime;
// find max and min hash
Comparator<Integer> comparator = (x,y) -> x > y ? 1 : (x < y ? -1 : 0);
int maxHash = hashList.parallelStream().max(comparator).get();
int minHash = hashList.parallelStream().min(comparator).get();
// hash set
Set<Integer> hashSet = hashList.parallelStream().collect(Collectors.toSet());
int conflictSize = lines.size() - hashSet.size();
float conflictRate = conflictSize * 1.0f / lines.size();
System.out.println(String.format("%s, %s, %s, %s, %s, %s, %s", multiplier, conflictSize, conflictRate, timeCost, lines.size(), minHash, maxHash));
}
/**
* 根据乘数计算hash值
*
* @param lines
* @param multiplier
* @return
*/
private List<Integer> computeHashes(List<String> lines, int multiplier) {
Function<String, Integer> hashFunction = x -> {
int hash = 0;
for (int i = 0; i < x.length(); i++) {
hash = (multiplier * hash) + x.charAt(i);
}
return hash;
};
return lines.parallelStream().map(hashFunction).collect(Collectors.toList());
}
执行测试方法testHash(),稍等片刻后,我们将得到一份测试报告。
哈希冲突率降序排序
通过对哈希冲突率进行降序排序,得到下面的结果。
结果分析
- 偶数的冲突率基本都很高,只有少数例外。
- 较小的乘数,冲突率也比较高,如1至20。
- 乘数1、2、256的分布不均匀。Java哈希值为32位int类型,取值范围为[-2147483648,2147483647]。
哈希冲突率降序排序
哈希耗时降序排序
我们再对冲突数量为1000以内的乘数进行分析,通过对执行耗时进行降序排序,得到下面的结果。
分析17、31、33、63、127和129
- 17在上一轮已经出局。
- 63执行计算耗时比较长。
- 31、33的冲突率分别为0.13%、0.14%,执行耗时分别为10、11,实时基本相当。
- 127、129的冲突率分别为0.01%、0.004%,执行耗时分别为9、10。
总体上看,129执行耗时低,冲突率也是最小的,似乎先择它更为合适?
哈希耗时降序排序
哈希分布情况
将整个哈希空间[-2147483648,2147483647]分为128个分区,分别统计每个分区的哈希值数量,以此来观察各个乘数的分布情况。每个分区的哈希桶位为2^32 / 128 = 33554432。
之所以通过分区来统计,主要是因为单词数太多,尝试过画成图表后密密麻麻的,无法直观的观察对比。
计算哈希分布代码
@Test
public void testHashDistribution() throws IOException {
int[] multipliers = {2, 17, 31, 33, 63, 127, 73, 133, 237, 161};
List<String> words = getWords();
for (int multiplier : multipliers) {
List<Integer> hashList = computeHashes(words, multiplier);
Map<Integer, Integer> hashMap = partition(hashList);
System.out.println("\n" + multiplier + "\n,count");
hashMap.forEach((x, y) -> System.out.println(x + "," + y));
}
}
/**
* 将整个哈希空间等分成128份,统计每个空间内的哈希值数量
*
* @param hashs
*/
public static Map<Integer, Integer> partition(List<Integer> hashs) {
// step = 2^32 / 128 = 33554432
final int step = 33554432;
List<Integer> nums = new ArrayList<>();
Map<Integer, Integer> statistics = new LinkedHashMap<>();
int start = 0;
for (long i = Integer.MIN_VALUE; i <= Integer.MAX_VALUE; i += step) {
final long min = i;
final long max = min + step;
int num = (int) hashs.parallelStream().filter(x -> x >= min && x < max).count();
statistics.put(start++, num);
nums.add(num);
}
// 为了防止计算出错,这里验证一下
int hashNum = nums.stream().reduce((x, y) -> x + y).get();
assert hashNum == hashs.size();
return statistics;
}
生成数据之后,保存文本为csv后缀,通过Excel打开。再通过Excel的图表功能,选择柱状图,生成以下图表。
乘数2乘数17乘数31乘数33乘数73乘数127乘数133乘数161乘数237
除了2和17,其他数字的分布基本都比较均匀。
总结
现在我们基本了解了Java String类的哈希乘数选择31的原因了,主要有以下几点。
- 31是奇素数。
- 哈希分布较为均匀。偶数的冲突率基本都很高,只有少数例外。较小的乘数,冲突率也比较高,如1至20。
- 哈希计算速度快。可用移位和减法来代替乘法。现代的VM可以自动完成这种优化,如31 * i = (i << 5) - i。
- 31和33的计算速度和哈希分布基本一致,整体表现好,选择它们就很自然了。
当参与哈希计算的项有很多个时,越大的乘数就越有可能出现结果溢出,从而丢失信息。我想这也是原因之一吧。
尽管从测试结果来看,比31、33大的奇数整体表现有更好的选择。然而31、33不仅整体表现好,而且32的移位操作是最少的,理论上来讲计算速度应该是最快的。
最后说明一下,我通过另外两台Linux服务器进行测试对比,发现结果基本一致。但以上测试方法不是很严谨,与实际生产运行可能存在偏差,结果仅供参考。
几个常用实现选项
values chosen to initialize h and a for some of the popular implementations
其中
- INITIAL_VALUE:哈希初始值。Java String的初始值hash=0。
- a:哈希乘数。Java String的哈希乘数为31。
参考
https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier
https://segmentfault.com/a/1190000010799123
https://en.wikipedia.org/wiki/Universal_hashing
《Effective Java中文版本》第2版
转载请注明来源:http://zhanjia.iteye.com/blog/2426892
个人公众号
二进制之路
相关推荐
### Java哈希表性能优化 #### 一、引言 随着现代软件开发中对高性能数据结构的需求日益增加,Java作为一种广泛应用的编程语言,其内置的数据结构优化变得尤为重要。Java的`java.util`包中提供了多种数据结构,其中...
在 Java 中,我们可以使用 String 的 getBytes() 方法将输入字符串转换为字节序列,然后使用 MessageDigest 类将字节序列转换为哈希值。 然而,在 Java 中实现哈希算法时,我们需要考虑速度和安全性两个方面。速度...
哈希表 哈希表.java Java对哈希表的操作
在软件开发和信息安全领域,哈希算法扮演着至关重要的角色,它能够将任意长度的数据转换为固定长度的输出,这个输出被称为哈希值。哈希计算工具能够帮助开发者快速地对数据进行验证、存储和比较。 哈希算法的特点...
在这个名为"Java_Datastructure.rar"的压缩包中,我们主要关注的是"java 哈希"和"java 哈希表"的相关知识。 哈希,也称为散列,是一种快速查找数据的方法,它通过计算一个叫做哈希函数的过程将任意长度的输入(也...
哈希函数是一种将任意长度输入(也叫做预映射)通过特定算法转化为固定长度输出的函数。这个输出通常被称为哈希值或消息摘要。哈希函数的重要特性包括:不可逆性、碰撞避免和均匀分布。在Java中,最常见的哈希函数库...
在Java编程领域,哈希计算工具是至关重要的,它们用于生成数据唯一标识,常用于数据校验、存储索引和快速查找。这个"java-hash.7z"压缩包包含了一个Java实现的哈希计算工具,这是一份经典的学习资源,可以帮助开发者...
在Java编程语言中,String类型扮演着至关重要的角色。它被广泛用于表示和操作文本,因为它是不可变的,这确保了字符串的安全性和效率。本文将深入探讨Java中的String类,包括其特性、构造方法、常用方法以及与其他...
在Java编程中,哈希遍历(Hash Traversal)通常是指对哈希表或映射数据结构(如HashMap)中的键值对进行访问的过程。哈希表是一种高效的数据存储方式,它通过计算对象的哈希码来快速定位数据,使得查找、插入和删除...
在Java编程语言中,`String`类是使用最频繁的类之一,它代表不可变的字符序列。本文将深入解析`String`类的一些常用方法,帮助开发者更好地理解和使用这个核心类。 1. **构造方法** - `String()`:创建一个空字符...
### Java String对象的经典问题 #### 一、String 类与对象机制概述 在Java中,`String`类是一个非常重要的类,它提供了丰富的功能用于处理文本数据。`String`类是不可变的(immutable),这意味着一旦一个`String`...
在IT领域,哈希(Hash)函数是一种将任意长度的数据转换为固定长度输出的函数,通常用于数据的校验、加密以及数据索引等场景。Java作为一种广泛使用的编程语言,提供了丰富的API来支持哈希计算。这个“获取哈希及...
在Java中,我们通常使用`HashMap`类来实现哈希表,但这里提到的是自定义实现哈希表的Java代码。这个压缩包包含三个文件:`HashTable.java`、`Info.java`和`TestHashTable.java`,分别代表哈希表的实现、存储的数据...
JOhm 是一个 Java 的对象哈希映射库,用于在 Redis 中存储 Java 对象。JOhm 基于 Jedis 开发。 示例代码: jedisPool = new JedisPool(new Config(), "localhost"); JOhm.setPool(jedisPool); User ...
JAVA源码哈希计算工具java-hash
java资源哈希计算工具 java-hash提取方式是百度网盘分享地址
String在Java中被实现为一个final类,这意味着它不能被继承。此外,它的构造函数创建了一个字符数组,并将其保存在名为value的私有final字段中。由于final关键字的使用,这个数组的引用不能改变,也就意味着字符串...
在Java编程中,MD5(Message-Digest Algorithm 5)是一种常用的哈希算法,能将任意长度的信息映射为128位的二进制数,通常以32位十六进制数表示,因此被称为32位哈希值。 标题"MD5Util_newspaper4pi_java_哈希值_MD...
本篇将深入探讨Java中的哈希算法和其在Java-hash.zip压缩包中的应用。 首先,哈希(Hash)函数是将任意长度的输入(也叫做预映射pre-image)通过特定算法转换成固定长度输出的过程,这个输出就是哈希值或散列值。在...
字符串在Java中被视为不可变对象,这意味着一旦创建了一个`String`对象,就不能更改它的值。下面我们将深入探讨`String`类的一些关键知识点,以及如何通过练习来熟练掌握它们。 1. **创建String对象**: - 字面量...