1.5 散列表

散列表也叫作哈希表，是根據鍵值對（key,value）進行存儲的一種數據結構。它把一對（key,value）通過key的哈希值來映射到數組中，也就是說，它通過把關鍵值映射到表中的一個位置來訪問記錄，以加快查找的速度。這個映射函數叫作散列函數，存放記錄的數組叫作散列表。

舉個例子，為了查找某個好友的微信號，可以按照好友首字母順序查找，在首字母為W的表中查找王姓的好友，顯然比直接查找要快得多。這里使用人名作為關鍵字，取首字母是這個例子中散列函數的函數法則，存放首字母的表對應散列表。關鍵字和函數法則理論上可以任意確定。

1. 沖突處理

由于關鍵字的函數映射關系，散列表難免會出現哈希沖突，也就是不同的key值通過散列函數，可以映射到一個數組中的同一個位置，這就是哈希沖突。哈希沖突不一定是哈希值沖突，也有可能是函數映射的結果出現沖突。比如一個哈希值是654321，另一個哈希值是978321，而哈希函數是取它們的后3位，所以它們通過哈希函數計算的結果都是321。

2. HashMap

關于散列表大家最熟悉的可能就是HashMap了，HashMap實際上是數組加鏈表的一種數據結構，當出現哈希沖突的時候，它會以鏈表的形式存在，如圖1-20所示。

HashMap的哈希映射函數非常簡單，就是用數組的長度減1，然后和哈希值進行與運算，（n-1）&hash，這里n是數組的長度，也是2的冪次方。這個運算非常巧妙，我們來介紹一下它是怎樣把一個數變成不小于它的2的冪次方的。比如傳入17會返回32，傳入32也會返回32，傳入33會返回64，它返回的都是2的冪次方，并且不能小于傳入的值。第一種方式通過while循環，這種方式比較簡單。

第二種方式相當于把一個數的二進制中最左邊的1往右鋪開，最后加上1就變成不小于它的2的冪次方，如圖1-21所示。這里在最開始的時候減1，是為了防止本來就是2的冪次方，通過運算會放大一倍，比如32，在開始運算的時候如果不減1，最后就會變成64。i必需是正整數。

第三種方式，首先判斷如果本來就是2的冪次方，直接返回，2的冪次方在二進制中只有一個1，其他位都是0。否則也是把最左邊的1往右邊鋪開，然后只保留最左邊的1，其他的都減掉，最后往左移一步就行了。

3. ArrayMap

除了HashMap以外，還有一個類是ArrayMap，它是一種純數組的數據結構，由兩個數組構成，一個存放哈希值，另一個存放key和value，其中存放key和value的數組長度是存放哈希值數組長度的2倍，并且存放哈希值的數組是有序的，查找的時候是通過二分法進行查找。當出現哈希沖突的時候，說明哈希值是一樣的，它們在哈希數組中是挨著的，查找的時候如果有相同的哈希值，但key值不一樣，我們還需要往兩邊進行查找，如圖1-22所示。

4. SparseArray

還有一個和ArrayMap非常相似的數據結構，它就是SparseArray，SparseArray也有兩個數組，和ArrayMap不同的是這兩個數組長度都是一樣的，一個數組存放的是key值，另一個數組存放的是value值，大家可能會有疑惑，怎么沒有存放哈希值的，其實這里的key值可以把它看作是哈希值，因為這里的key值必須是int類型，并且存放key值的數組也是有序的，查找的時候也是通過二分法進行查找，如圖1-23所示。