散列表是一種基本的數(shù)據(jù)結(jié)構(gòu)，那么散列表到底是什么樣的一種數(shù)據(jù)結(jié)構(gòu)呢？又有哪些應(yīng)用場景呢宽气？
假如我們要從一本電話本中查找一個人的電話號碼
如果這個電話本不是有序的，那我們每一行去找O(n)
如果是排列有序的潜沦，那我們可以通過二分查找O(logn)
需要注意的是O(n)與O(logn)的運行時間有著天壤之別萄涯，假設(shè)每秒能查找10行，在我們使用簡單查找O(n)與二分查找O(logn)耗時如下表：
如圖二分查找效率已經(jīng)高出很多唆鸡，但是還要去掃描多行涝影，那有沒有更高效、常數(shù)級O(1)的查找呢喇闸？?這就是散列表的用武之地袄琳。
散列函數(shù)
? ? 我通俗解釋為，把輸入映射（轉(zhuǎn)換）到數(shù)字燃乍，并滿足一些條件：
必須是一致的唆樊，相同的輸入必須轉(zhuǎn)換到相同的數(shù)字，例如輸入”張三”時得到的是0刻蟹，那么每次輸入”張三”得到的數(shù)值都必須是0逗旁。
將不同的輸入映射成不同的數(shù)字，最為理想的情況下將不同的輸入映射到不同的數(shù)字舆瘪。
散列函數(shù)又有何用處呢片效？
如上圖，散列函數(shù)準(zhǔn)確的指出了”張三”的存儲位置英古，根本不用查找淀衣，因為：
散列函數(shù)將同樣的輸入映射到了相同的索引。
散列函數(shù)將不同的輸入映射到了不同的索引召调。
散列函數(shù)數(shù)組內(nèi)的有效索引（沒有超過數(shù)組的邊界）膨桥。
沖突
? ? 前面我們假設(shè)的散列函數(shù)總是能將不同的輸入映射到了數(shù)組的不同位置蛮浑。而實際上，幾乎不可能編寫出這樣的散列函數(shù)只嚣。
不同的輸入被分配到了同一個數(shù)組位置上了沮稚，這就是沖突。所以只能在這個索引位置上存儲一個鏈表册舞。
如上圖蕴掏，如果散列表除第3個位置上有存儲了一個列表，其它位置上都是空的调鲸，換而言之就是說盛杰，這個散列表中的所有元素都在這個鏈表上。那性能會很糟糕O(n)藐石。
所以饶唤，散列函數(shù)非常非常重要。
(有興趣的朋友可以研究一下MurmurHash贯钩，https://en.wikipedia.org/wiki/MurmurHash)
一般常見語言都實現(xiàn)了散列表，如Java的HashMap
Go中的map
Python的字典
引伸一下應(yīng)用办素，如Redis中字典的實現(xiàn)：
https://sourcegraph.com/github.com/antirez/redis@fe43406929dbf6e6316f53f891370850cd8e1c3f/-/blob/src/dict.h#L77
dictEntry：哈希表數(shù)組
size：哈希表大小
sizemask：散列表大小的掩碼角雷，用于計算索引值
used：使用節(jié)點的數(shù)量
key：鍵值中的鍵
v：鍵值中的值
next：下一下散列節(jié)點的指針（解決散列函數(shù)的碰撞問題）
Resize 散列表擴容
可以自行參考一下Redis的rehash與漸進式rehash，本文主要介紹一下散列表這種數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)性穿。
