優化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。默認Object
的hashCode
通常,我們不應該使用默認的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
行為就像它具有整數鍵而不是複雜的對象。
如果我們需要考慮更多字段,情況將變得更加複雜。假設我們要基於id
和name
相等:
@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;
}
現在,我們需要以某種方式組合id
和name
哈希值。
首先,我們將獲得與以前相同的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
方法可能會使它的性能惡化。在本教程中,我們研究了使散列快速有效的可能方法。