Java使用什么散列函数来实现Hashtable类?

从CLRS这本书(“algorithm简介”)中,有几个哈希函数,比如mod,multiply等。

Java使用什么散列函数将键映射到插槽?

我已经看到这里有一个问题, 在Java语言中使用哈希函数 。 但是这个问题没有回答,我想这个问题的答案是错误的。 它说,hashCode()让你做你自己的Hashtable散列函数,但我认为这是错误的。

hashCode()返回的整数是Hashtble的真正键,然后Hashtable使用散列函数来散列hashCode()。 这个答案意味着Java给了你一个给Hashtable一个哈希函数的机会,但不是,这是错误的。 hashCode()提供了真正的密钥,而不是散列函数。

那么Java使用的哈希函数究竟是什么呢?

当在OpenJDK中向HashMap添加或请求密钥时,执行stream程如下:

  1. 使用开发人员定义的hashCode()方法将密钥转换为32位值。
  2. 然后将32位值通过第二个散列函数 (Andrew的答案包含源代码)转换为散列表内的偏移量。 这第二个散列函数是由HashMap的实现提供的,不能被开发人员覆盖。
  3. 如果密钥在哈希表中还不存在,则哈希表的相应条目包含对链接列表的引用或为空。 如果有碰撞(几个具有相同偏移量的键),那么键和它们的值就被简单地收集在一个单独的链表中。

如果散列表大小被select得适当高,碰撞的数量将受到限制。 因此,一次查找平均只需要一个固定的时间。 这被称为预期的恒定时间 。 但是,如果攻击者能够控制插入到散列表中的密钥以及所使用的散列algorithm的知识,他可以引发大量的散列冲突,从而强制线性查找时间。 这就是为什么一些散列表实现最近被改变,包括一个随机元素,使得攻击者难以预测哪些键会导致冲突。

一些ASCII艺术

 key.hashCode() | | 32-bit value | hash table V +------------+ +----------------------+ HashMap.hash() --+ | reference | -> | key1 | value1 | null | | |------------| +----------------------+ | modulo size | null | | = offset |------------| +---------------------+ +--------------> | reference | -> | key2 | value2 | ref | |------------| +---------------------+ | .... | | +----------------+ V +----------------------+ | key3 | value3 | null | +----------------------+ 

根据hashmap的来源,每个hashCode都使用以下方法进行哈希处理:

  /** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 

每个hashCode再次被散列的原因是为了进一步防止碰撞(见上面的注释)

HashMap也使用一种方法来确定一个哈希码的索引(因为长度总是2的幂,所以你可以用&代替%):

 /** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); } 

put方法看起来像这样:

 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); 

散列码的目的是为给定的对象提供唯一的整数表示。 因此,Integer的hashCode方法简单地返回值是有意义的,因为每个值对于Integer对象都是唯一的。

一般的散列分为两步:a。 HashCode b。 压缩

在步骤a。 会生成一个对应于您的密钥的整数。 这可以由你在Java中修改。

在步骤b。 Java应用压缩技术来映射步骤a返回的整数。 到散列表或散列表中的一个插槽。 这种压缩技术是不能改变的。

我认为这里的概念有些混乱。 散列函数将可变大小的input映射到固定大小的输出(散列值)。 对于Java对象,输出是一个32位有符号整数。

Java的散列表使用散列值作为存储实际对象的数组的索引,并将模算术和冲突考虑在内。 但是,这不是哈希。

java.util.HashMap实现在索引之前对散列值执行一些额外的位交换,以防止在某些情况下发生过度冲突。 它被称为“额外的哈希”,但我不认为这是一个正确的术语。

以一种非常简单的方式,第二次散列只不过是find存储新键值对的桶数组的索引号。 这个映射是为了从key obj的哈希码的较大的int值中获得索引号。 现在,如果两个不相等的密钥对象具有相同的哈希码,则会发生冲突,因为它们将被映射到相同的数组索引。 在这种情况下,第二个键以及它的值将被添加到链表中。 这里数组索引将指向最后添加的节点。