瘋狂Java學習筆記（42）----------HashTable,HashMap和HashSet

瘋狂Java學習筆記（42）----------HashTable,HashMap和HashSet

本文目錄：

1. HashTable和HashMap的區別

2. HashSet和HashMap的區別

3. HashMap，HashSet工作原理

4. HashSet工作原理

5. 常見問題

1. HashTable和HashMap的區別

---------------------------------------------------------

相信這個是大家最容易混淆的。

HashMap和Hashtable都實現了Map接口，但決定用哪一個之前先要弄清楚它們之間的分別。主要的區別有：線程安全性，同步(synchronization)，以及速度。

HashMap幾乎可以等價于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap?allows one null key and any number of?null?values.，而Hashtable則不行)。這就是說，HashMap中如果在表中沒有發現搜索鍵，或者如果發現了搜索鍵，但它是一個空的值，那么get()將返回null。如果有必要，用containKey()方法來區別這兩種情況。

HashMap是非synchronized，而Hashtable是synchronized，這意味著Hashtable是線程安全的，多個線程可以共享一個Hashtable；而如果沒有正確的同步的話，多個線程是不能共享HashMa的。?即是說，在多線程應用程序中，不用專門的操作就安全地可以使用Hashtable了；而對于HashMap，則需要額外的同步機制。但HashMap的同步問題可通過Collections的一個靜態方法得到解決：

Map Collections.synchronizedMap(Map m)

這個方法返回一個同步的Map，這個Map封裝了底層的HashMap的所有方法，使得底層的HashMap即使是在多線程的環境中也是安全的。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?而而且Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的擴展性更好。

要詳細了解ConcurrentHashMap見《構建一個更好的? HashMap---ConcurrentHashMap》

另一個區別是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以當有其它線程改變了HashMap的結構（增加或者移除元素），將會拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常。但這并不是一個一定發生的行為，要看JVM。這條同樣也是Enumeration和Iterator的區別。

由于Hashtable是線程安全的也是synchronized，所以在單線程環境下它比HashMap要慢。如果你不需要同步，只需要單一線程，那么使用HashMap性能要好過Hashtable。

HashMap不能保證隨著時間的推移Map中的元素次序是不變的。

哈希值的使用不同，HashTable直接使用對象的hashCode，代碼是這樣的：

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

而HashMap重新計算hash值，而且用與代替求模：

int hash = hash(k);

int i = indexFor(hash, table.length);

要注意的一些重要術語：

1) sychronized意味著在一次僅有一個線程能夠更改Hashtable。就是說任何線程要更新Hashtable時要首先獲得同步鎖，其它線程要等到同步鎖被釋放之后才能再次獲得同步鎖更新Hashtable。

2) Fail-safe和iterator迭代器相關。如果某個集合對象創建了Iterator或者ListIterator，然后其它的線程試圖“結構上”更改集合對象，將會拋出ConcurrentModificationException異常。但其它線程可以通過set()方法更改集合對象是允許的，因為這并沒有從“結構上”更改集合。但是假如已經從結構上進行了更改，再調用set()方法，將會拋出IllegalArgumentException異常。

3) 結構上的更改指的是刪除或者插入一個元素，這樣會影響到map的結構。

2. HashSet和HashMap的區別

---------------------------------------------------------

在分析他們的區別之前，我們首先分別來簡單介紹一下他們倆。（后面我會詳細的結合源碼分析他倆）

什么是HashSet？

HashSet實現了Set接口，它不允許集合中有重復的值，當我們提到HashSet時，第一件事情就是在將對象存儲在HashSet之前，要先確保對象重寫equals()和hashCode()方法，這樣才能比較對象的值是否相等，以確保set中沒有儲存相等的對象。如果我們沒有重寫這兩個方法，將會使用這個方法的默認實現。詳見《探索equals()和hashCode()方法》。

public boolean add(Object o)方法用來在Set中添加元素，當元素值重復時則會立即返回false，如果成功添加的話會返回true。

什么是HashMap？

HashMap實現了Map接口，Map接口對鍵值對進行映射。Map中不允許重復的鍵。Map接口有兩個基本的實現，HashMap和TreeMap。TreeMap保存了對象的排列次序，而HashMap則不能。HashMap允許鍵和值為null。HashMap是非synchronized的，但collection框架提供方法能保證HashMap synchronized，這樣多個線程同時訪問HashMap時，能保證只有一個線程更改Map。

public Object put(Object Key,Object value)方法用來將元素添加到map中。

HashSet和HashMap的區別

3. HashMap工作原理

---------------------------------------------------------

實際上，HashSet 和 HashMap 之間有很多相似之處，對于 HashSet 而言，系統采用 Hash 算法決定集合元素的存儲位置，這樣可以保證能快速存、取集合元素；對于 HashMap 而言，系統 key-value 當成一個整體進行處理，系統總是根據 Hash 算法來計算 key-value 的存儲位置，這樣可以保證能快速存、取 Map 的 key-value 對。

在介紹集合存儲之前需要指出一點：雖然集合號稱存儲的是 Java 對象，但實際上并不會真正將 Java 對象放入 Set 集合中，只是在 Set 集合中保留這些對象的引用而言。也就是說：Java 集合實際上是多個引用變量所組成的集合，這些引用變量指向實際的 Java 對象。就像引用類型的數組一樣，當我們把? Java 對象放入數組之時，并不是真正的把 Java 對象放入數組中，只是把對象的引用放入數組中，每個數組元素都是一個引用變量。

HashMap存儲的實現（put()方法）

當程序試圖將多個key-value放入HashMap中是，以如下代碼片段為例：

HashMap map = new HashMap();

map.put("語文" , 80.0);

map.put("數學" , 89.0);

map.put("英語" , 78.2);

當程序執行map.put("語文",80.0)時，系統將調用"語文"（即Key）的hashCode()方法得到其hashCode值---每個java對象都有hashCode()方法，都可以通過該方法獲得它的hashCode值。得到這個對象的hashCode值之后，系統根據hashCode值來決定 該元素的存儲位置。

我們可以看HashMap類的put(K key,V value)方法的源代碼：

public V put(K key, V value)

{

// 如果 key 為 null，調用 putForNullKey 方法進行處理

if (key == null)

return putForNullKey(value);

// 根據 key 的 keyCode 計算 Hash 值

int hash = hash(key.hashCode());

// 搜索指定 hash 值在對應 table 中的索引

int i = indexFor(hash, table.length);

// 如果 i 索引處的 Entry 不為 null，通過循環不斷遍歷 e 元素的下一個元素

for (Entry e = table[i]; e != null; e = e.next)

{

Object k;

// 找到指定 key 與需要放入的 key 相等（hash 值相同

// 通過 equals 比較放回 true）

if (e.hash == hash && ((k = e.key) == key

|| key.equals(k)))

{

V oldValue = e.value;

e.value = value;

e.recordAccess(this);

return oldValue;

}

}

// 如果 i 索引處的 Entry 為 null，表明此處還沒有 Entry

modCount++;

// 將 key、value 添加到 i 索引處

addEntry(hash, key, value, i);

return null;

}

上面方法提供了一個根據 hashCode() 返回值來計算 Hash 碼的方法：hash()，這個方法是一個純粹的數學計算，其方法如下：

static int hash(int h)

{

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

對于任意給定的對象，只要它的 hashCode() 返回值相同，那么程序調用 hash(int h) 方法所計算得到的 Hash 碼值總是相同的。接下來程序會調用 indexFor(int h, int length) 方法來計算該對象應該保存在 table 數組的哪個索引處。indexFor(int h, int length) 方法的代碼如下：

static int indexFor(int h, int length)

{

return h & (length-1);

}

這個方法非常巧妙，它總是通過 h?&(table.length -1) 來得到該對象的保存位置——而 HashMap 底層數組的長度總是 2 的 n 次方，這一點可參看后面關于 HashMap 構造器的介紹。

當 length 總是 2 的倍數時，h?& (length-1)將是一個非常巧妙的設計：假設? h=5,length=16, 那么 h & length - 1 將得到 5；如果 h=6,length=16, 那么 h & length - 1 將得到 6 ……如果 h=15,length=16, 那么 h & length - 1 將得到 15；但是當 h=16 時 , length=16 時，那么 h & length - 1 將得到 0 了；當 h=17 時 , length=16 時，那么 h & length - 1 將得到 1 了……這樣保證計算得到的索引值總是位于 table 數組的索引之內。

根據上面 put 方法的源代碼可以看出，當程序試圖將一個 key-value 對放入 HashMap 中時，程序首先根據該 key 的 hashCode() 返回值決定該 Entry 的存儲位置：如果兩個 Entry 的 key 的 hashCode() 返回值相同，那它們的存儲位置相同。如果這兩個 Entry 的 key 通過 equals 比較返回 true，新添加 Entry 的 value 將覆蓋集合中原有 Entry 的 value，但 key 不會覆蓋。如果這兩個 Entry 的 key 通過 equals? 比較返回 false，新添加的 Entry 將與集合中原有 Entry 形成 Entry 鏈，而且新添加的 Entry 位于 Entry 鏈的頭部——具體說明繼續看 addEntry() 方法的說明。

當向 HashMap 中添加 key-value 對，由其 key 的 hashCode() 返回值決定該 key-value 對（就是 Entry 對象）的存儲位置。當兩個 Entry 對象的 key 的 hashCode() 返回值相同時，將由 key 通過 eqauls() 比較值決定是采用覆蓋行為（返回 true），還是產生 Entry 鏈（返回 false）。

上面程序中還調用了 addEntry(hash, key, value, i); 代碼，其中 addEntry 是 HashMap 提供的一個包訪問權限的方法，該方法僅用于添加一個 key-value 對。下面是該方法的代碼：

void addEntry(int hash, K key, V value, int bucketIndex)

{

// 獲取指定 bucketIndex 索引處的 Entry

Entry e = table[bucketIndex]; // ①

// 將新創建的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entry

table[bucketIndex] = new Entry(hash, key, value, e);

// 如果 Map 中的 key-value 對的數量超過了極限

if (size++ >= threshold)

// 把 table 對象的長度擴充到 2 倍。

resize(2 * table.length); // ②

}

上面方法的代碼很簡單，但其中包含了一個非常優雅的設計：系統總是將新添加的 Entry 對象放入 table 數組的 bucketIndex 索引處——如果 bucketIndex 索引處已經有了一個 Entry 對象，那新添加的 Entry 對象指向原有的 Entry 對象（產生一個 Entry 鏈），如果 bucketIndex 索引處沒有 Entry 對象，也就是上面程序①號代碼的? e 變量是 null，也就是新放入的 Entry 對象指向 null，也就是沒有產生 Entry 鏈。

什么是Map.Entry？

Map是java中的接口，Map.Entry是Map的一個內部接口。

Map提供了一些常用方法，如keySet()、entrySet()等方法，keySet()方法返回值是Map中key值的集合；entrySet()的返回值也是返回一個Set集合，此集合的類型為Map.Entry。

Map.Entry是Map聲明的一個內部接口，此接口為泛型，定義為Entry。它表示Map中的一個實體（一個key-value對）。接口中有getKey(),getValue方法。

由以上可以得出，遍歷Map的常用方法：

1. Map map = new HashMap();

Irerator iterator = map.entrySet().iterator();

while(iterator.hasNext()) {

Map.Entry entry = iterator.next();

Object key = entry.getKey();

//

}

2.Map map = new HashMap();

Set keySet= map.keySet();

Irerator iterator = keySet.iterator;

while(iterator.hasNext()) {

Object key = iterator.next();

Object value = map.get(key);

//

}

另外，還有一種遍歷方法是，單純的遍歷value值，Map有一個values方法，返回的是value的Collection集合。通過遍歷collection也可以遍歷value,如

Map map = new HashMap();

Collection c = map.values();

Iterator iterator = c.iterator();

while(iterator.hasNext()) {

Object value = iterator.next();

}

Map.Entry是Map內部定義的一個接口，專門用來保存key→value的內容。Map.Entry的定義如下：

public?static?interface?Map.Entry

Map.Entry是使用static關鍵字聲明的內部接口，此接口可以由外部通過"外部類.內部類"的形式直接調用。在本接口中提供了如表13-12所示的方法。

表13-12? Map.Entry接口的常用方法

序號

方????法

類型

描????述

1

public boolean equals(Object o)

普通

對象比較

2

public K getKey()

普通

取得key

3

public V getValue()

普通

取得value

4

public int hashCode()

普通

返回哈希碼

5

public V setValue(V value)

普通

設置value的值

從之前的內容可以知道，在Map的操作中，所有的內容都是通過key→value的形式保存數據的，那么對于集合來講，實際上是將key→value的數據保存在了Map.Entry的實例之后，再在Map集合中插入的是一個Map.Entry的實例化對象，如圖13-4所示。

U提示：Map.Entry在集合輸出時會使用到。

在一般的Map操作中（例如，增加或取出數據等操作）不用去管Map.Entry接口，但是在將Map中的數據全部輸出時就必須使用Map.Entry接口

Hash 算法的性能選項

根據上面代碼可以看出，在同一個 bucket 存儲 Entry 鏈的情況下，新放入的 Entry 總是位于 bucket 中，而最早放入該 bucket 中的 Entry 則位于這個 Entry 鏈的最末端。

上面程序中還有這樣兩個變量：

size：該變量保存了該 HashMap 中所包含的 key-value 對的數量。

threshold：該變量包含了 HashMap 能容納的 key-value 對的極限，它的值等于 HashMap 的容量乘以負載因子（load factor）。

從上面程序中②號代碼可以看出，當 size++ >= threshold 時，HashMap 會自動調用 resize 方法擴充 HashMap 的容量。每擴充一次，HashMap 的容量就增大一倍。

上面程序中使用的 table 其實就是一個普通數組，每個數組都有一個固定的長度，這個數組的長度就是 HashMap 的容量。HashMap 包含如下幾個構造器：

HashMap()：構建一個初始容量為 16，負載因子為 0.75 的 HashMap。

HashMap(int initialCapacity)：構建一個初始容量為 initialCapacity，負載因子為 0.75 的 HashMap。

HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的負載因子創建一個 HashMap。

當創建一個 HashMap 時，系統會自動創建一個 table 數組來保存 HashMap 中的 Entry，下面是 HashMap 中一個構造器的代碼：

// 以指定初始化容量、負載因子創建 HashMap

public HashMap(int initialCapacity, float loadFactor)

{

// 初始容量不能為負數

if (initialCapacity < 0)

throw new IllegalArgumentException(

"Illegal initial capacity: " +

initialCapacity);

// 如果初始容量大于最大容量，讓出示容量

if (initialCapacity > MAXIMUM_CAPACITY)

initialCapacity = MAXIMUM_CAPACITY;

// 負載因子必須大于 0 的數值

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException(

loadFactor);

// 計算出大于 initialCapacity 的最小的 2 的 n 次方值。

int capacity = 1;

while (capacity < initialCapacity)

capacity <<= 1;

this.loadFactor = loadFactor;

// 設置容量極限等于容量 * 負載因子

threshold = (int)(capacity * loadFactor);

// 初始化 table 數組

table = new Entry[capacity]; // ①

init();

}

上面代碼中粗體字代碼包含了一個簡潔的代碼實現：找出大于 initialCapacity 的、最小的 2 的 n 次方值，并將其作為 HashMap 的實際容量（由 capacity 變量保存）。例如給定 initialCapacity 為 10，那么該 HashMap 的實際容量就是 16。

initialCapacity 與 HashTable 的容量

創建 HashMap 時指定的 initialCapacity 并不等于 HashMap 的實際容量，通常來說，HashMap 的實際容量總比 initialCapacity 大一些，除非我們指定的 initialCapacity 參數值恰好是 2 的 n 次方。當然，掌握了 HashMap 容量分配的知識之后，應該在創建 HashMap 時將 initialCapacity 參數值指定為 2 的 n 次方，這樣可以減少系統的計算開銷。

程序①號代碼處可以看到：table 的實質就是一個數組，一個長度為 capacity 的數組。

對于 HashMap 及其子類而言，它們采用 Hash 算法來決定集合中元素的存儲位置。當系統開始初始化 HashMap 時，系統會創建一個長度為 capacity 的 Entry 數組，這個數組里可以存儲元素的位置被稱為“桶（bucket）”，每個 bucket 都有其指定索引，系統可以根據其索引快速訪問該 bucket 里存儲的元素。

無論何時，HashMap 的每個“桶”只存儲一個元素（也就是一個 Entry），由于 Entry 對象可以包含一個引用變量（就是 Entry 構造器的的最后一個參數）用于指向下一個 Entry，因此可能出現的情況是：HashMap 的 bucket 中只有一個 Entry，但這個 Entry 指向另一個 Entry ——這就形成了一個 Entry 鏈。如圖 1 所示：

key相同的則產生鏈。

HashMap 的讀取實現（）

當 HashMap 的每個 bucket 里存儲的 Entry 只是單個 Entry ——也就是沒有通過指針產生 Entry 鏈時，此時的 HashMap 具有最好的性能：當程序通過 key 取出對應 value 時，系統只要先計算出該 key 的 hashCode() 返回值，在根據該 hashCode 返回值找出該 key 在 table 數組中的索引，然后取出該索引處的 Entry，最后返回該 key 對應的 value 即可。看 HashMap? 類的 get(K key) 方法代碼：

public V get(Object key)

{

// 如果 key 是 null，調用 getForNullKey 取出對應的 value

if (key == null)

return getForNullKey();

// 根據該 key 的 hashCode 值計算它的 hash 碼

int hash = hash(key.hashCode());

// 直接取出 table 數組中指定索引處的值，

for (Entry e = table[indexFor(hash, table.length)];

e != null;

// 搜索該 Entry 鏈的下一個 Entr

e = e.next) // ①

{

Object k;

// 如果該 Entry 的 key 與被搜索 key 相同

if (e.hash == hash && ((k = e.key) == key

|| key.equals(k)))

return e.value;

}

return null;

}

從上面代碼中可以看出，如果 HashMap 的每個 bucket 里只有一個 Entry 時，HashMap 可以根據索引、快速地取出該 bucket 里的 Entry；在發生“Hash 沖突”的情況下，單個 bucket 里存儲的不是一個 Entry，而是一個 Entry 鏈，系統只能必須按順序遍歷每個 Entry，直到找到想搜索的 Entry 為止——如果恰好要搜索的 Entry 位于該 Entry 鏈的最末端（該 Entry 是最早放入該 bucket? 中），那系統必須循環到最后才能找到該元素。

歸納起來簡單地說，HashMap 在底層將 key-value 當成一個整體進行處理，這個整體就是一個 Entry 對象。HashMap 底層采用一個 Entry[] 數組來保存所有的 key-value 對，當需要存儲一個 Entry 對象時，會根據 Hash 算法來決定其存儲位置；當需要取出一個 Entry 時，也會根據 Hash 算法找到其存儲位置，直接取出該 Entry。由此可見：HashMap 之所以能快速存、取它所包含的 Entry，完全類似于現實生活中母親從小教我們的：不同的東西要放在不同的位置，需要時才能快速找到它。

當創建 HashMap 時，有一個默認的負載因子（load factor），其默認值為 0.75，這是時間和空間成本上一種折衷：增大負載因子可以減少 Hash 表（就是那個 Entry 數組）所占用的內存空間，但會增加查詢數據的時間開銷，而查詢是最頻繁的的操作（HashMap 的 get() 與 put() 方法都要用到查詢）；減小負載因子會提高數據查詢的性能，但會增加 Hash 表所占用的內存空間。

掌握了上面知識之后，我們可以在創建 HashMap 時根據實際需要適當地調整 load factor 的值；如果程序比較關心空間開銷、內存比較緊張，可以適當地增加負載因子；如果程序比較關心時間開銷，內存比較寬裕則可以適當的減少負載因子。通常情況下，程序員無需改變負載因子的值。

如果開始就知道 HashMap 會保存多個 key-value 對，可以在創建時就使用較大的初始化容量，如果 HashMap 中 Entry 的數量一直不會超過極限容量（capacity * load factor），HashMap 就無需調用 resize() 方法重新分配 table 數組，從而保證較好的性能。當然，開始就將初始容量設置太高可能會浪費空間（系統需要創建一個長度為 capacity 的 Entry 數組），因此創建 HashMap 時初始化容量設置也需要小心對待。

4. HashSet工作原理

----------------------------------------------------

對于 HashSet 而言，它是基于 HashMap 實現的，HashSet 底層采用 HashMap 來保存所有元素，因此 HashSet 的實現比較簡單，查看 HashSet 的源代碼，可以看到如下代碼：

public class HashSet

extends AbstractSet

implements Set, Cloneable, java.io.Serializable

{

// 使用 HashMap 的 key 保存 HashSet 中所有元素

private transient HashMap map;

// 定義一個虛擬的 Object 對象作為 HashMap 的 value

private static final Object PRESENT = new Object();

...

// 初始化 HashSet，底層會初始化一個 HashMap

public HashSet()

{

map = new HashMap();

}

// 以指定的 initialCapacity、loadFactor 創建 HashSet

// 其實就是以相應的參數創建 HashMap

public HashSet(int initialCapacity, float loadFactor)

{

map = new HashMap(initialCapacity, loadFactor);

}

public HashSet(int initialCapacity)

{

map = new HashMap(initialCapacity);

}

HashSet(int initialCapacity, float loadFactor, boolean dummy)

{

map = new LinkedHashMap(initialCapacity

, loadFactor);

}

// 調用 map 的 keySet 來返回所有的 key

public Iterator iterator()

{

return map.keySet().iterator();

}

// 調用 HashMap 的 size() 方法返回 Entry 的數量，就得到該 Set 里元素的個數

public int size()

{

return map.size();

}

// 調用 HashMap 的 isEmpty() 判斷該 HashSet 是否為空，

// 當 HashMap 為空時，對應的 HashSet 也為空

public boolean isEmpty()

{

return map.isEmpty();

}

// 調用 HashMap 的 containsKey 判斷是否包含指定 key

//HashSet 的所有元素就是通過 HashMap 的 key 來保存的

public boolean contains(Object o)

{

return map.containsKey(o);

}

// 將指定元素放入 HashSet 中，也就是將該元素作為 key 放入 HashMap

public boolean add(E e)

{

return map.put(e, PRESENT) == null;

}

// 調用 HashMap 的 remove 方法刪除指定 Entry，也就刪除了 HashSet 中對應的元素

public boolean remove(Object o)

{

return map.remove(o)==PRESENT;

}

// 調用 Map 的 clear 方法清空所有 Entry，也就清空了 HashSet 中所有元素

public void clear()

{

map.clear();

}

...

}

由上面源程序可以看出，HashSet 的實現其實非常簡單，它只是封裝了一個 HashMap 對象來存儲所有的集合元素，所有放入 HashSet 中的集合元素實際上由 HashMap 的 key 來保存，而 HashMap 的 value 則存儲了一個 PRESENT，它是一個靜態的 Object 對象。

HashSet 的絕大部分方法都是通過調用 HashMap 的方法來實現的，因此 HashSet 和 HashMap 兩個集合在實現本質上是相同的。

HashMap 的 put 與 HashSet 的 add

由于 HashSet 的 add() 方法添加集合元素時實際上轉變為調用 HashMap 的 put() 方法來添加 key-value 對，當新放入 HashMap 的 Entry 中 key 與集合中原有 Entry 的 key 相同（hashCode() 返回值相等，通過 equals 比較也返回 true），新添加的 Entry 的 value 將覆蓋原來 Entry 的 value，但 key 不會有任何改變，因此如果向 HashSet 中添加一個已經存在的元素，新添加的集合元素（底層由? HashMap 的 key 保存）不會覆蓋已有的集合元素。

掌握上面理論知識之后，接下來看一個示例程序，測試一下自己是否真正掌握了 HashMap 和 HashSet 集合的功能。

下面這個程序其實，我在上篇博客《探索equals()和hashCode()方法》中已經講得很清楚了，但是由于比較重要，我就再把他寫一遍。主要說明的就是重寫equals()方法時，就必須重寫hashCode()方法。

class Name

{

private String first;

private String last;

public Name(String first, String last)

{

this.first = first;

this.last = last;

}

public boolean equals(Object o)

{

if (this == o)

{

return true;

}

if (o.getClass() == Name.class)

{

Name n = (Name)o;

return n.first.equals(first)

&& n.last.equals(last);

}

return false;

}

}

public class HashSetTest

{

public static void main(String[] args)

{

Set s = new HashSet();

s.add(new Name("abc", "123"));

System.out.println(

s.contains(new Name("abc", "123")));

}

}

上面程序中向 HashSet 里添加了一個 new Name("abc", "123") 對象之后，立即通過程序判斷該 HashSet 是否包含一個 new Name("abc", "123") 對象。粗看上去，很容易以為該程序會輸出 true。

實際運行上面程序將看到程序輸出 false，這是因為 HashSet 判斷兩個對象相等的標準除了要求通過 equals() 方法比較返回 true 之外，還要求兩個對象的 hashCode() 返回值相等。而上面程序沒有重寫 Name 類的 hashCode() 方法，兩個 Name 對象的 hashCode() 返回值并不相同，因此 HashSet 會把它們當成 2 個對象處理，因此程序返回 false。

由此可見，當我們試圖把某個類的對象當成 HashMap 的 key，或試圖將這個類的對象放入 HashSet 中保存時，重寫該類的 equals(Object obj) 方法和 hashCode() 方法很重要，而且這兩個方法的返回值必須保持一致：當該類的兩個的 hashCode() 返回值相同時，它們通過 equals() 方法比較也應該返回 true。通常來說，所有參與計算 hashCode() 返回值的關鍵屬性，都應該用于作為 equals()? 比較的標準。

hashCode() 和 equals()

詳見《探索equals()和hashCode()方法》

如下程序就正確重寫了 Name 類的 hashCode() 和 equals() 方法，程序如下：

class Name { private String first; private String last; public Name(String first, String last) { this.first = first; this.last = last; } // 根據 first 判斷兩個 Name 是否相等 public boolean equals(Object o) { if (this == o) { return true; } if (o.getClass() == Name.class) { Name n = (Name)o; return n.first.equals(first); } return false; } // 根據 first 計算 Name 對象的 hashCode() 返回值 public int hashCode() { return first.hashCode(); } public String toString() { return "Name[first=" + first + ", last=" + last + "]"; } } public class HashSetTest2 { public static void main(String[] args) { HashSet set = new HashSet(); set.add(new Name("abc" , "123")); set.add(new Name("abc" , "456")); System.out.println(set); } }

上面程序中提供了一個 Name 類，該 Name 類重寫了 equals() 和 toString() 兩個方法，這兩個方法都是根據 Name 類的 first 實例變量來判斷的，當兩個 Name 對象的 first 實例變量相等時，這兩個 Name 對象的 hashCode() 返回值也相同，通過 equals() 比較也會返回 true。

程序主方法先將第一個 Name 對象添加到 HashSet 中，該 Name 對象的 first 實例變量值為"abc"，接著程序再次試圖將一個 first 為"abc"的 Name 對象添加到 HashSet 中，很明顯，此時沒法將新的 Name 對象添加到該 HashSet 中，因為此處試圖添加的 Name 對象的 first 也是" abc"，HashSet 會判斷此處新增的 Name 對象與原有的 Name 對象相同，因此無法添加進入，程序在①號代碼處輸出? set 集合時將看到該集合里只包含一個 Name 對象，就是第一個、last 為"123"的 Name 對象。

5. 常見問題

--------------------------------------------

“你知道HashMap的工作原理嗎？” “你知道HashMap的get()方法的工作原理嗎？”

答：“HashMap是基于hashing的原理，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象。當我們給put()方法傳遞鍵和值時，我們先對鍵調用hashCode()方法，返回的hashCode用于找到bucket位置來儲存Entry對象。”這里關鍵點在于指出，HashMap是在bucket中儲存鍵對象和值對象，作為Map.Entry。這一點有助于理解獲取對象的邏輯。如果你沒有意識到這一點，或者錯誤的認為僅僅只在bucket中存儲值的話，你將不會回答如何從HashMap中獲取對象的邏輯。這個答案相當的正確，也顯示出面試者確實知道hashing以及HashMap的工作原理。

“當兩個對象的hashcode相同會發生什么？”?從這里開始，真正的困惑開始了，一些面試者會回答因為hashcode相同，所以兩個對象是相等的，HashMap將會拋出異常，或者不會存儲它們。然后面試官可能會提醒他們有equals()和hashCode()兩個方法，并告訴他們兩個對象就算hashcode相同，但是它們可能并不相等。一些面試者可能就此放棄，而另外一些還能繼續挺進，他們回答“因為hashcode相同，所以它們的bucket位置相同，‘碰撞’會發生。因為HashMap使用鏈表存儲對象，這個Entry(包含有鍵值對的Map.Entry對象)會存儲在鏈表中。”這個答案非常的合理，雖然有很多種處理碰撞的方法，這種方法是最簡單的，也正是HashMap的處理方法。但故事還沒有完結，面試官會繼續問：

“如果兩個鍵的hashcode相同，你如何獲取值對象？”?面試者會回答：當我們調用get()方法，HashMap會使用鍵對象的hashcode找到bucket位置，然后獲取值對象。面試官提醒他如果有兩個值對象儲存在同一個bucket，他給出答案:將會遍歷鏈表直到找到值對象。面試官會問因為你并沒有值對象去比較，你是如何確定確定找到值對象的？除非面試者直到HashMap在鏈表中存儲的是鍵值對，否則他們不可能回答出這一題。

其中一些記得這個重要知識點的面試者會說，找到bucket位置之后，會調用keys.equals()方法去找到鏈表中正確的節點，最終找到要找的值對象。完美的答案！

許多情況下，面試者會在這個環節中出錯，因為他們混淆了hashCode()和equals()方法。因為在此之前hashCode()屢屢出現，而equals()方法僅僅在獲取值對象的時候才出現。一些優秀的開發者會指出使用不可變的、聲明作final的對象，并且采用合適的equals()和hashCode()方法的話，將會減少碰撞的發生，提高效率。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個獲取對象的速度，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇。

如果你認為到這里已經完結了，那么聽到下面這個問題的時候，你會大吃一驚。

“如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦？”除非你真正知道HashMap的工作原理，否則你將回答不出這道題。默認的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會創建原來HashMap大小的兩倍的bucket數組，來重新調整map的大小，并將原來的對象放入新的bucket數組中。這個過程叫作rehashing，因為它調用hash方法找到新的bucket位置。如果你能夠回答這道問題，下面的問題來了：

“你了解重新調整HashMap大小存在什么問題嗎？”你可能回答不上來，這時面試官會提醒你當多線程的情況下，可能產生條件競爭(race condition)。

當重新調整HashMap大小的時候，確實存在條件競爭，因為如果兩個線程都發現HashMap需要重新調整大小了，它們會同時試著調整大小。在調整大小的過程中，存儲在鏈表中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發生了，那么就死循環了。這個時候，你可以質問面試官，為什么這么奇怪，要在多線程的環境下使用HashMap呢？：）

”為什么String, Interger這樣的wrapper類適合作為鍵？“?String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用。因為String是不可變的，也是final的，而且已經重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。

“我們可以使用自定義的對象作為鍵嗎？?”這是前一個問題的延伸。當然你可能使用任何對象作為鍵，只要它遵守了equals()和hashCode()方法的定義規則，并且當對象插入到Map中之后將不會再改變了。如果這個自定義對象時不可變的，那么它已經滿足了作為鍵的條件，因為當它創建之后就已經不能改變了。

“我們可以使用CocurrentHashMap來代替Hashtable嗎？”這是另外一個很熱門的面試題，因為ConcurrentHashMap越來越多人用了。我們知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因為它僅僅根據同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable，但是HashTable提供更強的線程安全性。看看查看《HashMap Vs ConcurrentHashMap》Hashtable和ConcurrentHashMap的區別。

這些問題設計哪些知識點：

hashing的概念

HashMap中解決碰撞的方法

equals()和hashCode()的應用，以及它們在HashMap中的重要性

不可變對象的好處

HashMap多線程的條件競爭

重新調整HashMap的大小

好吧今天的HashSet和HashMap就告一段落了，明天講TreeSet和TreeMap。順便介紹介紹一篇博客給大家《20道最常見的java問題(電子商務方向)》。改天我也研究研究。

Reference：

http://www.ibm.com/developerworks/cn/java/j-jtp05273/

http://javarevisited.blogspot.com/2011/09/difference-hashmap-vs-hashset-java.html

http://www.ibm.com/developerworks/cn/java/j-lo-hash/index.html

HashMap Java

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。