優化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方法可能會使它的性能惡化。在本教程中，我們研究了使散列快速有效的可能方法。