Java使用什么散列函数来实现Hashtable类？
从CLRS这本书（“algorithm简介”）中，有几个哈希函数，比如mod，multiply等。
Java使用什么散列函数将键映射到插槽？
我已经看到这里有一个问题， 在Java语言中使用哈希函数 。 但是这个问题没有回答，我想这个问题的答案是错误的。 它说，hashCode（）让你做你自己的Hashtable散列函数，但我认为这是错误的。
hashCode（）返回的整数是Hashtble的真正键，然后Hashtable使用散列函数来散列hashCode（）。 这个答案意味着Java给了你一个给Hashtable一个哈希函数的机会，但不是，这是错误的。 hashCode（）提供了真正的密钥，而不是散列函数。
那么Java使用的哈希函数究竟是什么呢？
当在OpenJDK中向HashMap添加或请求密钥时，执行stream程如下：
- 使用开发人员定义的
hashCode()方法将密钥转换为32位值。 - 然后将32位值通过第二个散列函数 （Andrew的答案包含源代码）转换为散列表内的偏移量。 这第二个散列函数是由HashMap的实现提供的，不能被开发人员覆盖。
- 如果密钥在哈希表中还不存在，则哈希表的相应条目包含对链接列表的引用或为空。 如果有碰撞（几个具有相同偏移量的键），那么键和它们的值就被简单地收集在一个单独的链表中。
如果散列表大小被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值中获得索引号。 现在，如果两个不相等的密钥对象具有相同的哈希码，则会发生冲突，因为它们将被映射到相同的数组索引。 在这种情况下，第二个键以及它的值将被添加到链表中。 这里数组索引将指向最后添加的节点。
