java - 每个存储桶中的单个实例如何在 java Hashmap 中产生最佳性能？

Question

我在一本书中读到，如果哈希函数为每个不同的对象返回唯一的哈希值，那么它最有效。如果类中的 hashcode() 方法为每个不同的对象提供唯一的哈希值，并且我想在 Hashmap 中存储该类的 n 个不同的实例，那么将有 n 个存储桶来存储 n 个实例。时间复杂度将为 O( n).那么每个hash值的single entry(instance)如何产生更好的性能呢？是不是跟bucket的数据结构有关呢？

Answer 1

您似乎认为对于 n 个元素有 n 个桶，时间复杂度将是 O(n)，这是错误的。

举个不同的例子，假设你有一个包含 n 个元素的 ArrayList，执行 get(index) 需要多少时间？ O(1) 对吗？

现在想想HashMap，ArrayList 例子中的这个index 实际上就是map 的hashCode .当我们插入 HashMap 以查找该元素所在位置(桶)时，我们使用哈希码(索引)。如果每个桶都有一个条目 - 从映射中搜索值的时间是 O(1)。

但即使在单个桶中有多个值，HashMap 的一般搜索复杂度仍然是O(1)。

桶的数据结构也很重要。例如，对于最坏的情况。在当前的 HashMap 实现中，它使用两种类型:LinkedNode 和 TreeNode；取决于一些事情，比如此时桶中有多少。链接很容易:

next.next.next...

树节点是

    - left
node   
    - right

它是一棵红黑树。在这样的数据结构中，搜索复杂度为 O(logn)，这比 O(n) 好得多。