hashCode,实现以及与HashMap的关系

Question

所以我在这里问了另一个相关的问题:带有雪崩效应的java字符串哈希函数,但我现在有一个不同的相关问题.

我在那个问题中建立的是String的hashCode()函数没有雪崩效应.这意味着,例如,如果我有字符串"k1","k2","k3",并且我在每个上调用hashCode(),则返回的值将是连续的.

现在,基于我对数据结构101的回忆,我的印象是这是一件坏事.因为假设HashMap通过算法选择桶,例如:

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

这意味着类似的密钥存储在连续的桶中,导致更高的冲突率,从O(1)降低大O查询时间到......谁知道有多糟糕......可能比O更差(log n ).

我在第一个问题中得到的答案类型是"这里不需要雪崩效应","它仅用于加密哈希函数",而且"字符串的hashCode实现很快,适用于小型哈希映射".

这让我很困惑.当它们很小时,所有数据结构都很快.Sun是否会提供一个适用于大型数据集的默认hashCode函数？那时候HashMap的表现真的很重要,不是吗？

或者,我错过了什么？请赐教.

Answer 1

将密钥存储在连续的存储桶中不会导致性能下降。将密钥存储在同一个存储桶中（例如，链接）即可。当使用链接来解决哈希冲突时：

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

用于哈希表（等）的哈希码不需要雪崩效应。