Hashtable与HashMap中的哈希函数? [英] Hashing function in Hashtable vs. HashMap?

问题描述

我知道Hashtable和HashMap之间的区别.但是，这两个类似乎都在使用哈希函数来完成工作. Hashtable中使用的哈希函数与HashMap中使用的哈希函数之间有区别吗?

I know the difference between Hashtable and HashMap. However, both these classes seemingly are using a hash function to get the job done. Is there a difference between the hash function used in Hashtable, and the hash function used in HashMap?

特别是，它们使用的哈希算法之间有区别吗?在这两个类中用于哈希的公式是什么?

In particular, is there a difference between the hashing algorithm they use? What is the formula used to hash in these two classes?

换句话说，索引(哈希值)的计算方法是否不同?

In other words, is the way for calculating index (hash value) different?

推荐答案

特别是，它们使用的哈希算法之间有区别吗?在这两个类中用于哈希的公式是什么?

In particular, is there a difference between the hashing algorithm they use? What is the formula used to hash in these two classes?

将对象用作哈希表键时使用的主要哈希函数是对象的hashCode()方法.实现一个不错的哈希函数取决于关键类.

The primary hash function used when you use an object as a hash table key is the object's hashCode() method. It is up the to the key class to implement a decent hash function.

Hashtable和HashMap类获取键的哈希码值，并将其转换为主哈希表链数组中的索引.但是，Hashtable和HashMap之间的发生方式有所不同.

The Hashtable and HashMap classes take the key's hashcode value and convert it to an index in the primary hashtable array-of-chains. However, there are differences in how this happens between Hashtable and HashMap.

• 对于Hashtable(Java 8)，代码是这样的:

• For Hashtable (Java 8) the code is this:

 hash = key.hashCode();
 index = (hash & 0x7FFFFFFF) % tab.length;

对于HashMap(Java 8)，代码(有效)是这样的:

For HashMap (Java 8) the code is (effectively) this:

 // (I have restructured the code for ease of comparison.)
 int h;
 hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 index = (tab.length - 1) & hash;

如您所见，HashMap正在加扰键的哈希码函数返回的哈希码值.在源代码中对此进行了如下解释:

As you can see, HashMap is scrambling the hashcode value returned by the key's hashcode function. This is explained in the source code as follows:

[此方法]计算key.hashCode()并将哈希的较高位(XOR)扩展为较低.因为该表使用2的幂次掩码，所以仅在当前掩码上方的位中发生变化的哈希集将始终发生冲突. (众所周知的示例是在小表中包含连续整数的Float键集.)因此，我们应用了将向下扩展较高位的影响的变换.在速度，实用性和位扩展质量之间需要权衡.由于许多常见的哈希集已经合理分布(因此不能从扩展中受益)，并且由于我们使用树来处理容器中的大量冲突集，因此我们仅以最便宜的方式对一些移位后的位进行XOR，以减少系统损失，并结合了最高位的影响，否则由于表范围的限制，这些位将永远不会用于索引计算.

[This method] computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don't benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

注意:

1. &与%的区别在于，在Hashtable中，哈希数组的大小是质数，而在HashMap(Java 8)中，哈希数组的大小是2的幂.

1. The & versus % difference is because in Hashtable the hash array size is a prime number, but in HashMap (Java 8) the size is a power of 2.

在Java 8 HashMap中，如果键类实现了Comparable，则该实现会将长哈希链变成二叉树.

In Java 8 HashMap, the implementation will turn a long hash chain into a binary tree if the key class implements Comparable.

HashMap处理null键，但Hashtable不处理.

---

但是，仅当您的键类的设计/实现方法设计不佳或实施某项操作……或者有人故意尝试设计哈希冲突时，HashMap中所有这些额外的复杂性才会发挥作用.

---

However, all of this extra complexity in HashMap only comes into play if your key class has a poorly designed / implemented hashCode() method ... or if someone is deliberately trying to engineer hash collisions.

换句话说，如果您的密钥类设计合理，则差异无关紧要.

In other words, if your key class is well designed, the differences should not matter.

这篇关于Hashtable与HashMap中的哈希函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！