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

问题描述

这本书CLRS（算法导论），有几个散列函数，如mod，繁殖等。

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语言散列函数>。但它并没有回答这个问题，我认为这个问题的答案明显是错误的。它说，散列code（）让你做你自己的哈希函数的哈希表，但我认为这是不对的。

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.

通过散列code（）返回的整数是真正的关键Hashtble，然后哈希表使用散列函数哈希散列code（）。什么这个答案意味着是Java给你一个机会给Hashtable的哈希函数，但是没有，这是错误的。哈希code（）给出了真正的关键，而不是哈希函数。

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. 关键是转变为使用开发人员定义的散code（）方法的32位值。
2. 在32位的值，然后一个第二散列函数（其中，安德鲁的回答包含源$ C ​​$ C）到一个哈希表内的偏移改变。此第二散列函数由HashMap中的执行提供和不能被显影剂所覆盖。
3. 的哈希表的相应条目包含对一个链表空或者，如果该键尚未在哈希表中存在。如果有冲突（几个按键采用相同的偏移量），键以及它们的值被简单地收集在一个单向链表。

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.

如果散列表的大小被适当选择高，碰撞次数将受到限制。因此，单个查找只需要一定的时间上的平均值。他们称这种预期的固定时间。然而，如果用户在使用散列算法的知识，他可以激起大量的散列值冲突的，因此迫使线性查找时间，从而有可能使整个系统不能忍受缓慢。这就是为什么有些哈希表实现最近已更改为包括一个随机元素，使得它更难攻击者predict哪些键会引起冲突。

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. They call this "expected constant time". However, if a user has knowledge of the hash algorithm in use, he can provoke a lot of hash collisions and therefore force linear lookup time, thus possibly rendering whole systems unbearably slow. 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 |
                   |          |------------|    +----------------------+
                   |          | null       |
                   | offset   |------------|    +---------------------+
                   +--------> | reference  | -> | key1 | value1 | ref |
                              |------------|    +---------------------+
                              |    ....    |                       |
                                                  +----------------+
                                                  V
                                                +----------------------+
                                                | key2 | value2 | null |
                                                +----------------------+

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