在《算法导论》（CLRS）一书中，有几种哈希函数，例如mod、multiply等。
Java使用何种哈希函数将键映射到槽中呢？
我看到这里有一个问题：Hashing function used in Java Language。但它没有回答这个问题，而且我认为该问题的标记答案是错误的。它说hashCode()让你为Hashtable编写自己的哈希函数，但我认为这是错误的。
由hashCode()返回的整数才是Hashtable的真正键，然后Hashtable使用哈希函数来哈希hashCode()。这个答案暗示了Java给你一个机会为Hashtable提供一个哈希函数，但不，这是错误的。hashCode()给出了真正的键，而不是哈希函数。
那么Java究竟使用了哪个哈希函数呢？
hashCode()方法将键转换为32位值。如果哈希表的大小选择得足够高，则冲突数量将受到限制。因此，平均一个查找只需要恒定的时间。这被称为期望的恒定时间。然而，如果攻击者控制要插入哈希表的键并且知道正在使用的哈希算法，他可以引发大量哈希冲突，从而强制进行线性查找。这就是为什么一些哈希表实现最近已经改变以包括一个随机元素，使攻击者更难预测哪些键会导致冲突。
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 |
+----------------------+
/**
* 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还使用一种方法来确定哈希码的索引（Java版本<8）（由于长度始终是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. 哈希码 b. 压缩
在a步骤中，会生成与您的键对应的整数。您可以在Java中对其进行修改。
在b步骤中，Java会应用一种压缩技术将由a步骤返回的整数映射到哈希表中的槽位。这种压缩技术无法更改。
/**
* 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.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这是Java中hashMap类所使用的最新哈希函数。
我认为这里有一些概念上的混淆。哈希函数将可变大小的输入映射到固定大小的输出（哈希值）。在Java对象的情况下，输出是一个32位有符号整数。
Java的Hashtable使用哈希值作为索引，进而找到实际存储对象的数组，考虑取模算术和冲突。然而，这不是哈希。
java.util.HashMap实现在索引之前对哈希值进行了一些额外的位交换，以防止某些情况下过多的冲突。它被称为“附加哈希”，但我认为这不是正确的术语。