java - 此示例中有關HashMap哈希算法的說明




collision hashcode (4)

有人可以向我解釋為什麼我要解決我要解決的問題而不是我期望的答案的正確方法嗎?

這是一個巧合

更新

正如其他人已經提到的,與排序的 TreeMap 或保留輸入順序的 LinkHashMap 不同, HashMap 不能在對其內容進行迭代時保證任何順序。 因此,是的,如果您的元素已排序,那隻是一個巧合。

我正在嘗試解決這個問題:

給定只有3個唯一數字的整數數組,將在O(n)時間中按升序(及其各自的頻率)打印數字。

我想不使用 counting sort 算法來解決它,所以我想我可以做一個 for loop 並將數字插入 HashMap ,然後 loop 遍歷 HashMap entrySet 並打印所需的信息。

這是函數:

public static void printOut(int[] arr){
        Map<Integer,Integer> hm=new HashMap<Integer,Integer>();
        for(int num : arr){
            if(hm.containsKey(num)){
                hm.put(num,hm.get(num)+1);
            }else{hm.put(num,1);}
        }
        for(Map.Entry<Integer,Integer> entry : hm.entrySet()){
            System.out.println("Key= "+entry.getKey()+" Value= "+entry.getValue());
        }
}

當我的數組是: [3, 3, 2, 1, 3, 2, 1] 3,3,2,1,1,3,2,1]時,這是個竅門

但是上面的數組不應該導致任何衝突,因此我嘗試使用應該導致衝突的數組,我測試過我的函數的數組之一是: [6,6,9,9,6,3,9] 我的函數仍然按升序打印 Keys ,這讓我感到困惑,因為我認為當 HashMapKey 是整數時,哈希碼應為 hashIndex = key % noOfBuckets 因此當我將數字 hashIndex = key % noOfBuckets 6, 9 and 3 用作我的我認為 HashMap keys 會發生衝突,並且我的函數應該打印(基於上面使用的數組):

Key= 6 Value= 3
Key= 9 Value= 3
Key= 3 Value= 1 

但改為打印:

Key= 3 Value= 1
Key= 6 Value= 3
Key= 9 Value= 3

有人可以向我解釋為什麼我要解決我要解決的問題而不是我期望的答案的正確方法嗎?

謝謝。


  1. 哈希映射/哈希表中的“衝突”一詞是兩個不同鍵具有相同哈希碼的情況。 HashMap的Java實現使用List / RB-tree解決衝突,但是當您真正擁有3個整數鍵時,這絕對不是您的情況。
  2. HashMap不保證元素的插入(或任何其他)順序。 還有其他不同的結構(如LinkedHashMap或TreeMap)可以保證一定的順序。 但是,針對您的案例使用這種結構會產生一些開銷,因為您可以在固定時間內對3個元素的集合進行排序。 您甚至可以使用Map.Entry數組代替HashMap來完成任務。

摘自 HashMap 實現說明

樹箱(即其元素均為TreeNode的箱)為
主要由hashCode排序, 在並列的情況下,如果兩個
元素具有相同的“ C類實現可比較”,
類型,然後使用其compareTo方法進行排序。

對於Integer類,則是後者: implements Comparable<Integer>

整數的哈希碼始終是其整數值。 並且因為僅發生衝突,所以當兩個不同的條目獲得相同的哈希碼時,整數不會發生衝突。
表中節點的順序取決於哈希碼。 整數鍵是否可以預先排序?


正如上面@Serge Harnyk的答案中已經提到的那樣

HashMap不保證元素的插入(或任何其他)順序。

我運行了您在問題中與數組 [66,66,69,69,66,63,63,69] 共享的上述代碼,輸出為

Key= 66 Value= 3
Key= 69 Value= 3
Key= 63 Value= 2

在這裡,您可以看到輸出未按排序順序。 entrySet() 並未按排序順序返回元素的另一個數組是 [10,5,5,10,10,5,10000000]

Key= 5 Value= 3
Key= 10000000 Value= 1
Key= 10 Value= 3

因此,由於HashMap的文檔指定了HashMap的 entrySet() keySet() 返回的元素的順序,因此不能保證其順序為插入/排序。

將根據 哈希表中哈希表中的hashCode()函數生成的特定鍵的哈希碼來確定要對哈希鍵進行哈希處理 哈希索引。 您可以使用 .hashCode() 函數找到鍵的哈希碼

for(Map.Entry<Integer,Integer> entry : hm.entrySet()) {
    System.out.println("key= "+entry.getKey()+" has Hash Code= "+entry.getKey().hashCode()); 
}

數組[66,66,69,69,66,63,63,69]具有輸出

key= 66 has Hash Code= 66
key= 69 has Hash Code= 69
key= 63 has Hash Code= 63

數組[10,5,5,10,10,5,10000000]的輸出

key= 5 has Hash Code= 5
key= 10000000 has Hash Code= 10000000
key= 10 has Hash Code= 10

從這些中您可以看到,對於Integer鍵,哈希碼不是 hashIndex = key % noOfBuckets 。 此外,您可以定義自己的hashCode()方法實現,並將其用於HashMap。 您可以在此處找到實現您的自定義hashCode()函數的詳細說明。

參考。 https://www.geeksforgeeks.org/internal-working-of-hashmap-java/





hashcode