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

Question

我读过一本书，如果一个散列函数为每个不同的对象返回唯一的散列值，它是最有效的。如果类中的hashcode（）方法为每个不同的对象提供了一个唯一的哈希值，并且我想将该类中的n个不同的实例存储在一个Hashmap中，那么将有n个存储区用于存储n个实例。时间复杂度为O N）。那么每个散列值的单个条目（实例）如何产生更好的性能？它是否与存储桶的数据结构有关？

Answer 1

你似乎认为有n buckets for n elements，时间复杂度将是O(n)，这是错误的。

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

现在想想HashMap，这指数在ArrayList例子实际上是hashCode的地图。当我们插入一个HashMap来查找该元素到达的位置（存储桶）时，我们使用散列码（索引）。如果每个桶有条目 - 地图上的值的搜索时间为O(1)。

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

存储桶的数据结构也很重要。例如，对于更糟糕的情况。在目前实施的HashMap中，它使用两种类型：LinkedNode和TreeNode;取决于一些事情，比如在这个时间点有多少桶。链接很简单：

next.next.next... 

树节点是

- left 
node 
    - right 

这是一个red-black树。在这样的数据结构中，搜索复杂度是O(logn)，这比O(n)好得多。

Answer 2

Java HashMap将Key k与Value关联起来v每个Java Object都有一个方法hashCode（），它产生一个不一定唯一的整数。

我读过一本书，如果一个散列函数为每个不同的对象返回唯一的散列值，它是最有效的。

另一个定义是最好的散列函数是产生最小冲突的散列函数。

如果哈希码（）的一类方法给出了每个不同对象的唯一的散列值和予想存储在一个HashMap该类的n个不同的情况下，那么将有N个区段用于存储N个instances.The时间复杂度将是O（n）。

在我们的案例中，HashMap包含一个具有一定大小的桶的表，比方说我们的目的> = n。它使用对象的hashCode作为关键字，并通过Hash函数返回表的索引。如果我们有n个对象，并且哈希函数返回n个不同的索引，我们就有0个碰撞。这是最佳情况，找到并获取任何对象的复杂度是O（1）。

现在，如果哈希函数为2个不同的键（对象）返回相同的索引，那么我们发生冲突，并且该索引上的表桶已经包含一个值。在这种情况下，表桶将指向另一个新分配的桶。按照该顺序，在发生碰撞的索引上创建一个列表。所以最坏情况下的复杂度将是O（m），其中m是最大列表的大小。

总之，HashMap的性能取决于碰撞的次数。越少越好。

我相信这个video会帮助你。