在一個列表中查找某值是非常耗費資源的，隨機存取的列表是遍歷查找，順序存儲列表是鏈表查找，或者是Collections的二分法查找，但這都不夠快，畢竟都是遍歷嘛，最快的還要數以Hash開頭的集合（如HashMap、HashSet等類）查找，我們以HashMap為例，看看它是如何查找Key值的，代碼如下：
public static void main（Stringargs）{
int size=10000；
List＜String＞list=new ArrayList＜String＞（size）；
//初始化
for（int i=0；i＜size；i++）{
list.add（\"value\"+i）；
}
//記錄開始時間，單位納秒
long start=System.nanoTime（）；
//開始查找
list.contains（\"value\"+（size-1））；
//記錄結束時間，單位納秒
long end=System.nanoTime（）；
System.out.println（\"list執行時間：\"+（end-start）+\"ns\"）；
//Map的查找時間
Map＜String, String＞map=new HashMap＜String, String＞（size）；
for（int i=0；i＜size；i++）{
map.put（\"key\"+i，\"value\"+i）；
}
start=System.nanoTime（）；
map.containsKey（\"key\"+（size-1））；
end=System.nanoTime（）；
System.out.println（\"map執行時間：\"+（end-start）+\"ns\"）；
}
兩個不同的集合容器，一個是ArrayList，一個是HashMap，都是插入10000個元素，然後判斷是否包含最後一個加入的元素。邏輯相同，但是執行的時間差別卻非常大，結果如下：
list執行時間：982527ns
map執行時間：21231ns
HashMap比ArryList快了40多倍！兩者的contains方法都是判斷是否包含指定值，為何差距如此巨大呢？而且如果數據量增大，差距也會非線性地增大。
我們先來看ArrayList，它的contains就是一個遍歷對比，for循環逐個進行遍歷，判斷equals的返回值是否為true，為true即找到結果，不再遍歷，這很簡單，不再多說。
我們再來看看HashMap的containsKey方法是如何實現的，代碼如下：
public boolean containsKey（Object key）{
//判斷getEntry是否為空
return getEntry（key）！=null；
}
getEntry方法會根據key值查找它的鍵值對（也就是Entry對像），如果沒有找到，則返回null。我們再來看看該方法又是如何實現的，代碼如下：
final Entry＜K, V＞getEntry（Object key）{
//計算key的哈希碼
int hash=（key==null）?0：hash（key.hashCode（））；
//定位Entry, indexFor方法是根據hash定位數組的位置的
for（Entry＜K, V＞e=table[indexFor（hash, table.length）]；e！=null；e=e.next）{
Object k；
//哈希碼相同，並且鍵也相等才符合條件
if（e.hash==hash＆＆（（k=e.key）==key||（key！=null＆＆key.equals（k））））
return e；
}
return null；
}
注意看加粗字體部分，通過indexFor方法定位Entry在數組table中的位置，這是HashMap實現的一個關鍵點，怎麼能根據hashCode定位它在數組中的位置呢？
要解釋清楚這個問題，還需要從HashMap的table數組是如何存儲元素的說起。首先要說明以下三點：
table數組的長度永遠是2的N次冪。
table數組中的元素是Entry類型。
table數組中的元素位置是不連續的。
table數組為何如此設計呢？下面逐步來說明。先來看HashMap是如何插入元素的，代碼如下：
public V put（K key, V value）{
//null鍵處理
if（key==null）return putForNullKey（value）；
//計算hash碼，並定位元素
int hash=hash（key.hashCode（））；
int i=indexFor（hash, table.length）；
for（Entry＜K, V＞e=table[i]；e！=null；e=e.next）{
Object k；
//哈希碼相同，並key相等，則覆蓋
if（e.hash==hash＆＆（（k=e.key）==key||key.equals（k）））{
V oldValue=e.value；
e.value=value；
e.recordAccess（this）；
return oldValue；
}
}
modCount++；
//插入新元素，或者替換同哈希的舊元素並建立鏈表
addEntry（hash, key, value, i）；
return null；
}
注意看，HashMap每次增加元素時都會先計算其哈希碼，然後使用hash方法再次對hashCode進行抽取和統計，同時兼顧哈希碼的高位和低位信息產生一個唯一值，也就是說hashCode不同，hash方法返回的值也不同。之後再通過indexFor方法與數組長度做一次與運算，即可計算出其在數組中的位置，簡單地說，hash方法和indexFor方法就是把哈希碼轉變成數組的下標，源代碼如下：
static int hash（int h）{
h^=（h＞＞＞20）^（h＞＞＞12）；
return h^（h＞＞＞7）^（h＞＞＞4）；
}
static int indexFor（int h, int length）{
return h＆（length-1）；
}
這兩個方法相當有深度，讀者有興趣可以深入研究一下，這已經超出了本書範疇，不再贅述。順便說明一下，null值也是可以作為key值的，它的位置永遠是在Entry數組中的第一位。
現在有一個很重要的問題擺在面前了：哈希運算存在著哈希衝突問題，即對於一個固定的哈希算法f（k），允許出現f（k1）=f（k2），但k1≠k2的情況，也就是說兩個不同的Entry，可能產生相同的哈希碼，HashMap是如何處理這種衝突問題的呢？答案是通過鏈表，每個鍵值對都是一個Entry，其中每個Entry都有一個next變量，也就是說它會指向下一個鍵值對——很明顯，這應該是一個單向鏈表，該鏈表是由addEntry方法完成的，其代碼如下：
void addEntry（int hash, K key, V value, int bucketIndex）{
//取得當前位置元素
Entry＜K, V＞e=table[bucketIndex]；
//生成新的鍵值對，並進行替換，建立鏈表
table[bucketIndex]=new Entry＜K, V＞（hash, key, value, e）；
//判斷是否需要擴容
if（size++＞=threshold）
resize（2*table.length）；
}
這段程序涵蓋了兩個業務邏輯：如果新加入的鍵值對的hashCode是唯一的，那直接插入的數組中，它Entry的next值則為null；如果新加入的鍵值對的hashCode與其他元素衝突，則替換掉數組中的當前值，並把新加入的Entry的next變量指向被替換掉的元素——於是，一個鏈表就生成了，可以用圖5-1來表示。
圖 5-1 HashMap存儲結構圖
HashMap的存儲主線還是數組，遇到哈希衝突的時候則使用鏈表解決。瞭解了HashMap是如何存儲的，查找也就一目瞭然了：使用hashCode定位元素，若有哈希衝突，則遍歷對比，換句話說在沒有哈希衝突的情況下，HashMap的查找則是依賴hashCode定位的，因為是直接定位，那效率當然就高了！
知道HashMap的查找原理，我們就應該很清楚：如果哈希碼相同，它的查找效率就與ArrayList沒什麼兩樣了，遍歷對比，性能會大打折扣。特別是在那些進度緊張的項目中，雖重寫了hashCode方法但返回值卻是固定的，此時如果把這些對像插入到HashMap中，查找就相當耗時了。
注意 HashMap中的hashCode應避免衝突。