java - hashCode、实现和与 HashMap 的关系

Question

所以我在这里问了另一个相关问题:java string hash function with avalanche effect ，但我现在有一个不同的相关问题。

我在那个问题中确定的是 String 的 hashCode() 函数没有雪崩效应。这意味着，例如，如果我有字符串“k1”、“k2”、“k3”，并且我对每个字符串调用 hashCode()，则返回的值将是连续的。

现在，根据我对数据结构 101 的记忆，我的印象是这是一件坏事。因为假设 HashMap 通过类似这样的算法选择桶:

class HashMap {
    private int capacity;
    private int chooseBucket(String key) {
        return key.hashCode() % capacity;
    }
}

这意味着相似的键存储在连续的桶中，导致更高的冲突率，降低 big-O 查找时间从 O(1) 到......谁知道有多糟糕......可能比 O (登录 n)。

我得到的第一个问题的答案类型是“这里不需要雪崩效应”、“它仅用于密码学哈希函数”和“字符串的 hashCode 实现速度很快并且适用于小 HashMap '。

这让我很困惑。所有数据结构在很小的时候都很快。 Sun 不会提供适用于大型 数据集的默认 hashCode 函数吗？那时候 HashMap 的性能真的很重要，不是吗？

或者，我错过了什么吗？请赐教。

Answer 1

将键存储在连续的桶中不会导致性能下降。将 key 存储在相同 存储桶中(例如 chaining)。使用链接解决哈希冲突时:

• 最坏情况:每个散列值都相同，因此所有元素最终都在同一个桶中，在这种情况下，您将获得 O(n) 性能(假设链是链表)
• 最佳情况:每个哈希值都不同，因此每个元素最终都在不同的存储桶中，因此您可以获得预期的 O(1) 性能。

---

用于哈希表(以及类似表)的哈希码不需要需要 avalanche effect .