Java 使用什么哈希函数来实现 Hashtable 类? [英] What hashing function does Java use to implement Hashtable class?

问题描述

从 CLRS(算法导论")一书中，有几个散列函数，例如 mod、multiply 等.

From the book CLRS ("Introduction to Algorithms"), there are several hashing functions, such as mod, multiply, etc.

Java 使用什么哈希函数将键映射到槽?

What hashing function does Java use to map the keys to slots?

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

I have seen there is a question here Hashing function used in Java Language. But it doesn't answer the question, and I think the marked answer for that question is wrong. It says that hashCode() let you do your own hashing function for Hashtable, but I think it is wrong.

hashCode() 返回的整数是 Hashtble 的真正键，然后 Hashtable 使用散列函数对 hashCode() 进行散列.这个答案意味着 Java 给了你一个机会给 Hashtable 一个散列函数，但不，这是错误的.hashCode() 给出了真正的密钥，而不是散列函数.

The integer returned by hashCode() is the real key for Hashtble, then Hashtable uses a hashing function to hash the hashCode(). What this answer implies is that Java give you a chance to give Hashtable a hashing function, but no, it is wrong. hashCode() gives the real key, not the hashing function.

那么 Java 到底使用了什么散列函数?

So what exactly the hashing function does Java use?

推荐答案

在 OpenJDK 中向 HashMap 添加或请求键时，执行流程如下:

When a key is added to or requested from a HashMap in OpenJDK, the flow of execution is the following:

1. 使用开发人员定义的 hashCode() 方法将密钥转换为 32 位值.
2. 然后通过第二个散列函数(安德鲁的回答包含源代码)将 32 位值转换为散列表内的偏移量.第二个哈希函数由 HashMap 的实现提供，开发人员无法覆盖.
3. 哈希表的相应条目包含对链表的引用，如果哈希表中尚不存在键，则为 null.如果存在冲突(具有相同偏移量的多个键)，则键及其值会被简单地收集在一个单向链表中.

1. The key is transformed into a 32-bit value using the developer-defined hashCode() method.
2. The 32-bit value is then transformed by a second hash function (of which Andrew's answer contains the source code) into an offset inside the hash table. This second hash function is provided by the implementation of HashMap and cannot be overridden by the developer.
3. The corresponding entry of the hash table contains a reference to a linked list or null, if the key does not yet exist in the hash table. If there are collisions (several keys with the same offset), the keys together with their values are simply collected in a singly linked list.

如果哈希表的大小选择得适当高，冲突的数量将受到限制.因此，单次查找平均只需要恒定的时间.这称为预期恒定时间.但是，如果攻击者可以控制插入到哈希表中的密钥并了解所使用的哈希算法，他可能会引发大量哈希冲突，从而强制执行线性查找时间.这就是为什么最近更改了一些哈希表实现以包含一个随机元素，使攻击者更难预测哪些键会导致冲突.

If the hash table size was chosen appropriately high, the number of collisions will be limited. Thus, a single lookup takes only constant time on average. This is called expected constant time. However, if an attacker has control over the keys inserted into a hash table and knowledge of the hash algorithm in use, he can provoke a lot of hash collisions and therefore force linear lookup time. This is why some hash table implementations have been changed recently to include a random element that makes it harder for an attacker to predict which keys will cause collisions.

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 |
                                                    +----------------------+

这篇关于Java 使用什么哈希函数来实现 Hashtable 类?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！