每個存儲桶中的單個實例如何在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會幫助你。