时间戳

首页 > 解决方案 > Java HashMap 键散列

java - Java HashMap 键散列

问题描述

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

提前致谢。

标签： javahashmaphashcode

解决方案

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

这可能会导致冲突（不同的哈希值映射到同一索引），这是一个单独的主题，并且还会导致 HashMap 的 O(1) 预期时间的降级。一个警告是假设您的 hashCode() 实现是均匀分布。

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

Java 的 HashMap API 中没有公开可见的“阈值”。您可以获得的最接近的是：

HashMap(int initialCapacity, float loadFactor)

在这里，您提到的阈值相当于loadFactor。根据 Java 文档：

“作为一般规则，默认加载因子 (.75) 在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在 HashMap 类的大多数操作中，包括 get 和put). 在设置它的初始容量时要考虑map中的预期条目数及其负载因子，以尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，不会发生重新哈希操作。”

基本上这意味着如果 HashMap 中有太多冲突，它将扩大其当前数组大小并重新散列所有当前键，从而（希望）产生更均匀的分布。这应该具有在 HashMap 的一系列添加或删除中保持预期的 O(1) 复杂性的效果。

推荐阅读