Java HashMap密钥哈希[重复]

Question

如果我在hashmap中输入一个键和值，并且基于键hashcode生成的索引大于15，并且映射大小仍然小于阈值（即12），会发生什么？

提前谢谢。

Answer 1

让我给你们一个更广阔的图景，而不是只关注Java的特定数据类型HashMap，因为你们的问题包括hashcode标签，在我看来，你们对更一般的图景感兴趣——哈希函数是如何工作的。

这是你需要了解的。

通常，索引规范化的实现方式完全取决于对键的输入进行哈希处理的特定数据结构的实现（如HashTable/HashMap），无论是什么实现，都可以肯定地说：

哈希函数h（x）应该负责始终一致地生成一个整数，该整数位于支持数组的有效索引范围内。

在许多实现中，哈希函数可能会返回相当长（可能是负数）的整数，而这通常是通过索引规范化来解决的，索引规范化只会对长整数进行处理（裁剪、使负数为正等）。

对于Java的HashMap实现，hashCode（）是：

@HotSpotIntrinsicCandidate
public native int hashCode();

这意味着，该实现被委托给底层。

但是在大多数情况下，您可以假设，它将使用支持数组长度的模（桶的数量），这意味着，它永远不会超过该数组的长度（因此，您的hashmap的大小）。

Answer 2

HashMap通常会对hashCode（）方法提供的值执行模数运算，以便将整数的全部范围映射到其内部数组上的有效索引范围上。

这可能会导致冲突（不同的哈希值映射到同一个索引），这是一个单独的主题，并且还会导致哈希映射的O（1）预期时间降低。需要注意的一点是，假设hashCode（）实现是统一的分布。

在一个好的HashMap API中，您不需要担心内部数组大小或冲突。这是由实现以各种方式在内部处理的。

Java的HashMap API中没有公开可见的“阈值”。你能得到的最接近的结果是：

HashMap(int initialCapacity, float loadFactor)

这里，您提到的阈值相当于加载因子。根据Java文档：

“作为一般规则，默认加载因子（.75）在时间和空间成本之间提供了一个很好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括get和put）。在设置初始容量时，应考虑地图中的预期条目数及其负载系数，以尽量减少再灰化操作次数。如果初始容量大于最大入口数除以负载系数，则不会发生再灰化操作。"

基本上这意味着，如果HashMap中有太多冲突，它将扩展其当前数组大小并重新散列所有当前密钥，从而（希望）得到更均匀的分布。这样做的效果是，通过从HashMap中添加或删除一系列内容，可以保持预期的O（1）复杂性。