優化HashMap的性能

    1.簡介

    HashMap是一種功能強大的數據結構,具有廣泛的應用,尤其是在需要快速查找時間的情況下。但是,如果我們不注意細節,它可能會變得不理想。

    在本教程中,我們將研究如何使HashMap盡可能快。

    2. HashMap的瓶頸

    HashMap的元素檢索的最佳恆定時間( O(1) )來自散列的能力。對於每個元素, HashMap計算哈希碼並將元素放入與該哈希碼關聯的存儲桶中。由於不相等的對象可以具有相同的哈希碼(這種現象稱為哈希碼衝突),因此存儲桶的大小可能會增加。

    存儲桶實際上是一個簡單的鍊錶。在鏈接列表中查找元素不是很快( O(n) ),但是如果列表很小,這不是問題。當我們遇到很多哈希碼衝突時,問題就開始了,因此,我們有大量的大桶,而不是大量的小桶。

    在最壞的情況下,我們將所有內容都放在一個存儲桶中,我們的HashMap被降級為鏈接列表。因此,我們得到的不是O(1)查找時間,而是非常不令人滿意的O(n)

    3.樹而不是LinkedList

    從Java 8開始, HashMap內置了一種優化當存儲桶變得太大時,它們將被轉換為樹,而不是鍊錶。這將O(n)的悲觀時間帶到O(log(n)) ,這要好得多。為此, HashMap的鍵需要實現Comparable接口。

    這是一個不錯的自動解決方案,但並不完美。 O(log(n))仍然比所需的恆定時間差,並且轉換和存儲樹需要更多的功能和內存。

    4.最佳hashCode實現

    選擇散列函數時,我們需要考慮兩個因素:產生的散列碼的質量和速度。

    4.1。測量hashCode容量

    哈希碼存儲在int變量中,因此可能的哈希數限制為int類型的容量。一定要這樣,因為哈希值用於計算帶有存儲桶的數組的索引。這意味著我們可以在沒有哈希衝突的情況下將數量有限的鍵存儲在HashMap

    為了盡可能避免衝突,我們希望盡可能均勻地散佈哈希。換句話說,我們要實現均勻分佈。這意味著每個哈希碼值都具有與其他任何哈希值相同的機會。

    同樣,糟糕的hashCode方法將具有非常不平衡的分佈。在最壞的情況下,它將始終返回相同的數字。

    4.2。默認ObjecthashCode

    通常,我們不應該使用默認的Object's hashCode方法,因為我們不想在equals方法中使用對象標識。但是,在不太可能發生的情況下,我們真的想對HashMap鍵使用對象標識,則默認的hashCode函數可以正常工作。否則,我們將需要一個自定義實現。

    4.3。自定義hashCode

    通常,我們要覆蓋equals方法,然後還需要覆蓋hashCode 。有時,我們可以利用類的特定身份,並輕鬆地製作一個非常快速的hashCode方法。

    假設我們的對象的身份完全基於其整數id 。然後,我們可以將此id用作哈希函數:

    @Override
    
     public boolean equals(Object o) {
    
     if (this == o) return true;
    
     if (o == null || getClass() != o.getClass()) return false;
    
    
    
     MemberWithId that = (MemberWithId) o;
    
    
    
     return id.equals(that.id);
    
     }
    
    
    
     @Override
    
     public int hashCode() {
    
     return id;
    
     }

    這將非常快,並且不會產生任何碰撞。我們的HashMap行為就像它具有整數鍵而不是複雜的對象。

    如果我們需要考慮更多字段,情況將變得更加複雜。假設我們要基於idname相等:

    @Override
    
     public boolean equals(Object o) {
    
     if (this == o) return true;
    
     if (o == null || getClass() != o.getClass()) return false;
    
    
    
     MemberWithIdAndName that = (MemberWithIdAndName) o;
    
    
    
     if (!id.equals(that.id)) return false;
    
     return name != null ? name.equals(that.name) : that.name == null;
    
     }

    現在,我們需要以某種方式組合idname哈希值。

    首先,我們將獲得與以前相同的id的哈希值。然後,我們將其乘以一些精心選擇的數字,並添加name的哈希值:

    @Override
    
     public int hashCode() {
    
     int result = id.hashCode();
    
     result = PRIME * result + (name != null ? name.hashCode() : 0);
    
     return result;
    
     }

    如何選擇一個數字並不是一個容易回答的簡單問題。從歷史上看,最受歡迎的數字是31.它是質數,它導致分佈良好,很小,並且可以通過位移運算來優化乘以它:

    31 * i == (i << 5) - i

    但是,既然我們不需要為每個CPU週期而戰,那麼可以使用一些更大的素數。例如,也可以優化524287

    524287 * i == i << 19 - i

    並且,它可以提供質量更好的哈希,從而減少碰撞的機會。請注意,這些移位優化是由JVM自動完成的,因此我們不需要使用它們來混淆我們的代碼。

    4.4。 Objects實用程序類

    我們剛剛實現的算法已經很好地建立了,我們通常不需要每次都手動重新創建它。相反,我們可以使用Objects類提供的幫助方法:

    @Override
    
     public int hashCode() {
    
     return Objects.hash(id, name);
    
     }

    在引擎蓋下,它完全使用前面所述的算法(將數字31作為乘法器)。

    4.5。其他哈希函數

    與前面所述的哈希函數相比,有許多哈希函數提供的衝突機會更少。問題在於它們的計算量更大,因此無法提供我們尋求的速度增益。

    如果出於某種原因我們確實需要質量,而又不太在乎速度,那麼可以看一下Guava庫中的Hashing類:

    @Override
    
     public int hashCode() {
    
     HashFunction hashFunction = Hashing.murmur3_32();
    
     return hashFunction.newHasher()
    
     .putInt(id)
    
     .putString(name, Charsets.UTF_8)
    
     .hash().hashCode();
    
     }

    選擇32位函數非常重要,因為無論如何我們都無法存儲更長的哈希。

    5.結論

    現代Java的HashMap是功能強大且經過優化的數據結構。但是,設計hashCode方法可能會使它的性能惡化。在本教程中,我們研究了使散列快速有效的可能方法。