[TOC] ## 一 線性查找 哈希表查找，是一種用空間換時間的查找算法，時間復雜度能達到：`O(1)`，最壞情況下退化到查找鏈表：`O(n)`。但均勻性很好的哈希算法以及合適空間大小的數組，在很大概率避免了最壞情況 哈希表在添加元素時會進行伸縮，會造成較大的性能消耗，所以有時候會用到其他的查找算法：樹查找算法。 ## 二 散列查找 也稱哈希查找，是一種空間換時間的查找算法， 依賴的數據結構稱為哈希表或散列表：`HashTable` 散列查找: 1. 鍵進行`hash`計算得出一個大整數，然后與數組長度進行取余 2. 利用數組索引快的特征，用空間換時間的思路，使得查找的速度快于線性查找 3. 取數據時按同樣的步驟進行查找。 有兩種方式實現哈希表：線性探測法和拉鏈法。 ### 線性探測法 [不推薦] 線性探測法實現的哈希表是一個大數組。 首先，哈希表數據結構會初始化`N`個大小的數組，然后存取鍵`key`時，會求鍵的哈希值`hash(key)`，這是一個整數。然后與數組的大小進行取余：`hash(key)%N`，將會知道該鍵值對要存在數組的哪個位置。 如果數組該位置已經被之前的鍵值對占領了，也就是哈希沖突，那么會偏移加1，探測下個位置是否被占用，如果下個位置為空，那么占位，否則繼續探測。查找時，也是查看該位置是否為該鍵，不是則繼續往該位置的下一個位置查找。因為這個步驟是線性的，所以叫線性探測法。  因為線性探測法很少使用，我們接下來主要分析拉鏈法。 ### 哈希表：拉鏈法 拉鏈法實現的哈希表是一個數組鏈表，也就是數組中的元素是鏈表。數組鏈表很像一條條拉鏈，所以又叫拉鏈法查找。 首先，哈希表數據結構會初始化`N`個大小的數組，然后存取鍵`key`時，會求鍵的哈希值`hash(key)`，這是一個整數。然后與數組的大小進行取余：`hash(key)%N`，將會知道該鍵值對要存在數組的哪個位置。 如果數組該位置已經被之前的鍵值對占領了，也就是哈希沖突，那么鍵值對會追加到之前鍵值對的后面，形成一條鏈表。 比如鍵`51`的哈希`hash(51)`假設為`4`，那么`hash(51) % 4 = 4 % 4 = 0`，所以放在數組的第一個位置，同樣鍵`43`的哈希`hash(43)`假設為`8`，那么`hash(43) % 4 = 8 % 4 = 0`，同樣要放在數組的第一個位置。 因為哈希沖突了，所以鍵`43`鏈接在鍵`51`后面。  查找的時候，也會繼續這個過程，比如查找鍵`43`，進行哈希后得到位置`0`， 定位到數組第一位，然后遍歷這條鏈表，先找到鍵`51`，發現不到，往下找，直到找到鍵`43`。 `Golang`內置的數據類型：字典`map`就是用拉鏈法的哈希表實現的，但相對復雜，感興趣的可參考標準庫`runtime`下的`map.go`文件。 ### 哈希函數 當哈希沖突十分嚴重的時候，每個數組元素對應的鏈表會越來越長，即使定位到數組的某個下標，也要遍歷一條很長很長的鏈表，就退化為查找鏈表了，時間復雜度為：`O(n)`。  實際上`hash(key) % len`的分布是和`len`有關的，一組均勻分布的`hash(key)`在`len`是素數時才能做到均勻,但是為了數組擴容和計算更方便，仍然還是使用`2^x`的數組長度 ### 實現拉鏈哈希表