HashMap

HashMap可以說是Java中最常用的集合類框架之一，是Java語言中非常典型的數(shù)據(jù)結(jié)構(gòu)，我們總會在不經(jīng)意間用到它，很大程度上方便了我們?nèi)粘ｉ_發(fā)。

在很多Java的筆試題中也會被問到，最常見的，“HashMap和HashTable有什么區(qū)別？”，這也不是三言兩語能說清楚的，這種筆試題就是考察你來筆試之前有沒有復習功課，隨便來個快餐式的復習就能給出簡單的答案。

言歸正傳，了解HashMap之前，我們需要知道Object類的兩個方法hashCode和equals，我們先來看一下這兩個方法的默認實現(xiàn)：

/** JNI，調(diào)用底層其它語言實現(xiàn) */
public native int hashCode();
/** 默認同==，直接比較對象 */
public boolean equals(Object obj) {
	return (this == obj);
}

equals方法我們太熟悉了，我們經(jīng)常用于字符串比較，String類中重寫了equals方法，比較的是字符串值，看一下源碼實現(xiàn)：

public boolean equals(Object anObject) {
	if (this == anObject) {
		return true;
	}
	if (anObject instanceof String) {
		String anotherString = (String) anObject;
		int n = value.length;
		if (n == anotherString.value.length) {
			char v1[] = value;
			char v2[] = anotherString.value;
			int i = 0;
			// 逐個判斷字符是否相等
			while (n-- != 0) {
				if (v1[i] != v2[i])
						return false;
				i++;
			}
			return true;
		}
	}
	return false;
}

重寫equals要滿足幾個條件：

• 自反性：對于任何非空引用值 x，x.equals(x) 都應返回 true。
• 對稱性：對于任何非空引用值 x 和 y，當且僅當 y.equals(x) 返回 true 時，x.equals(y) 才應返回 true。
• 傳遞性：對于任何非空引用值 x、y 和 z，如果 x.equals(y) 返回 true，并且 y.equals(z) 返回 true，那么 x.equals(z) 應返回 true。
• 一致性：對于任何非空引用值 x 和 y，多次調(diào)用 x.equals(y) 始終返回 true 或始終返回 false，前提是對象上 equals 比較中所用的信息沒有被修改。
• 對于任何非空引用值 x，x.equals(null) 都應返回 false。

Object 類的 equals 方法實現(xiàn)對象上差別可能性最大的相等關系；即，對于任何非空引用值 x 和 y，當且僅當 x 和 y 引用同一個對象時，此方法才返回 true（x == y 具有值 true）。當此方法被重寫時，通常有必要重寫 hashCode 方法，以維護 hashCode 方法的常規(guī)協(xié)定，該協(xié)定聲明相等對象必須具有相等的哈希碼。

下面來說說hashCode方法，這個方法我們平時通常是用不到的，它是為哈希家族的集合類框架(HashMap、HashSet、HashTable)提供服務，hashCode 的常規(guī)協(xié)定是：

• 在 Java 應用程序執(zhí)行期間，在同一對象上多次調(diào)用 hashCode 方法時，必須一致地返回相同的整數(shù)，前提是對象上 equals 比較中所用的信息沒有被修改。從某一應用程序的一次執(zhí)行到同一應用程序的另一次執(zhí)行，該整數(shù)無需保持一致。 
• 如果根據(jù) equals(Object) 方法，兩個對象是相等的，那么在兩個對象中的每個對象上調(diào)用 hashCode 方法都必須生成相同的整數(shù)結(jié)果。 
• 以下情況不 是必需的：如果根據(jù) equals(java.lang.Object) 方法，兩個對象不相等，那么在兩個對象中的任一對象上調(diào)用 hashCode 方法必定會生成不同的整數(shù)結(jié)果。但是，程序員應該知道，為不相等的對象生成不同整數(shù)結(jié)果可以提高哈希表的性能。

當我們看到實現(xiàn)這兩個方法有這么多要求時，立刻凌亂了，幸好有IDE來幫助我們，Eclipse中可以通過快捷鍵alt+shift+s調(diào)出快捷菜單，選擇Generate hashCode() and equals()，根據(jù)業(yè)務需求，勾選需要生成的屬性，確定之后，這兩個方法就生成好了，我們通常需要在JavaBean對象中重寫這兩個方法。

好了，這兩個方法介紹完之后，我們回到HashMap。HashMap是最常用的集合類框架之一，它實現(xiàn)了Map接口，所以存儲的元素也是鍵值對映射的結(jié)構(gòu)，并允許使用null值和null鍵，其內(nèi)元素是無序的，如果要保證有序，可以使用LinkedHashMap。HashMap是線程不安全的，下篇文章會討論。

HashMap的類關系如下：

java.util Class HashMap<K,V>

java.lang.Object
  |--java.util.AbstractMap<K,V>
      |--java.util.HashMap<K,V>

所有已實現(xiàn)的接口：

Serializable,Cloneable,Map<K,V>

直接已知子類：

LinkedHashMap,PrinterStateReasons

HashMap中我們最長用的就是put(K, V)和get(K)。我們都知道，HashMap的K值是唯一的，那如何保證唯一性呢？我們首先想到的是用equals比較，沒錯，這樣可以實現(xiàn)，但隨著內(nèi)部元素的增多，put和get的效率將越來越低，這里的時間復雜度是O(n)，假如有1000個元素，put時最差情況需要比較1000次。

實際上，HashMap很少會用到equals方法，因為其內(nèi)通過一個哈希表管理所有元素，哈希是通過hash單詞音譯過來的，也可以稱為散列表，哈希算法可以快速的存取元素，當我們調(diào)用put存值時，HashMap首先會調(diào)用K的hashCode方法，獲取哈希碼，通過哈希碼快速找到某個存放位置，這個位置可以被稱之為 bucketIndex，但可能會存在多個元素找到了相同的 bucketIndex，有個專業(yè)名詞叫 碰撞，當碰撞發(fā)生時，這時會取到 bucketIndex位置已存儲的元素，最終通過equals來比較，equals方法就是碰撞時才會執(zhí)行的方法，所以前面說HashMap很少會用到equals。

HashMap通過hashCode和equals最終判斷出K是否已存在，如果已存在，則使用新V值替換舊V值，并返回舊V值，如果不存在 ，則存放新的鍵值對<K, V>到 bucketIndex位置。文字描述有些亂，通過下面的流程圖來梳理一下整個put過程。

現(xiàn)在我們知道，執(zhí)行put方法后，最終HashMap的存儲結(jié)構(gòu)會有這三種情況，我們當然期望情形3是最少發(fā)生的（效率最低）。到目前為止，我們了解了兩件事：

• HashMap通過鍵的hashCode來快速的存取元素。
• 當不同的對象發(fā)生碰撞時，HashMap通過單鏈表來解決，將新元素加入鏈表表頭，通過next指向原有的元素。單鏈表在Java中的實現(xiàn)就是對象的引用(復合)。

來鑒賞一下HashMap中put方法源碼：

public V put(K key, V value) {
	// 處理key為null，HashMap允許key和value為null
	if (key == null)
		return putForNullKey(value);
	// 得到key的哈希碼
	int hash = hash(key);
	// 通過哈希碼計算出bucketIndex
	int i = indexFor(hash, table.length);
	// 取出bucketIndex位置上的元素，并循環(huán)單鏈表，判斷key是否已存在
	for (Entry<K,V> e = table[i]; e != null; e = e.next) {
		Object k;
		// 哈希碼相同并且對象相同時
		if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
			// 新值替換舊值，并返回舊值
			V oldValue = e.value;
			e.value = value;
			e.recordAccess(this);
			return oldValue;
		}
	}
	// key不存在時，加入新元素
	modCount++;
	addEntry(hash, key, value, i);
	return null;
}

到這里，我們了解了HashMap工作原理的一部分，那還有另一部分，如，加載因子及rehash，HashMap通常的使用規(guī)則，多線程并發(fā)時HashMap存在的問題等等，這些會留在下一章說明。

到此這篇關于Java中的HashMap集合深度解析的文章就介紹到這了,更多相關Java中的HashMap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論