資訊專欄INFORMATION COLUMN
摘要：級別標簽算法散列表哈希表作者審校團隊本篇將介紹散列表哈希表的相關基礎知識。該數即為散列表數組的下標。因此，散列表的最優情況就是平均情況，時間復雜度為常數級。建議高于時，考慮散列表翻倍擴容優秀的散列函數。
級別： ★☆☆☆☆
標簽：「算法」「Hash」「散列表」「哈希表」
作者： MrLiuQ
審校： QiShare團隊
本篇將介紹散列表（哈希表）的相關基礎知識。
散列表(Hash table，也叫哈希表)是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。 這個映射函數叫做散列函數，存放記錄的數組叫做散列表。（來源360百科）
散列函數：簡單來說是一個函數，傳入一個Key就返回一個固定的數。該數即為散列表數組的下標。（用一句話描述：散列函數將“輸入”映射到“數字”。）
對不同的關鍵字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，這種現象稱為沖突(碰撞)。
常見的解決哈希沖突方案有以下四種：（詳細細節見下篇講解）
開放定址法：為產生沖突的地址H(key)求得一個新的地址序列： Hi =（H(key)+ di）% m （i=1，2，3，...，m-1） 其中H(key)為哈希函數，m為表長，di稱為增量序列。（其中增量di的取值方法也有多種，詳細細節見下篇）
鏈地址法：將所有哈希地址相同的記錄都鏈接在同一鏈表中。
再哈希法：產生沖突時計算**另一個哈希函數（散列函數）**的地址，直到沖突不再發生為止。
建立公共溢出區：把沖突的值都放在另一個溢出表中，不把沖突的值存原表中。
先介紹一個散列表的專有名詞：填裝因子（負載因子）。
這里列出了常見數據結構操作的時間復雜度。
| / | 散列表（最佳情況） | 散列表（最壞情況） | 數組 | 鏈表 |
|---|---|---|---|---|
| 取值 | O(1) | O(n) | O(1) | O(n) |
| 插入 | O(1) | O(n) | O(n) | O(1) |
| 刪除 | O(1) | O(n) | O(n) | O(1) |
可以看出散列表在最佳情況下的性能是很出色的，雖然最壞情況的性能不好，但我們可以通過一些手段避免掉最壞情況。因此，散列表的最優情況就是平均情況，時間復雜度為常數級O(1)。
因此，散列表在使用中需要注意兩點：
較低的填裝因子（或稱負載因子）。（建議：高于0.7時，考慮散列表翻倍擴容）
優秀的散列函數。（盡量減少沖突的發生）
PS：Python的做法是，會設法保證大概還有三分之一的表元是空的，當快要達到這個閥值的時候，會進行擴容，將原散列表復制到一個更大的散列表里。
例如，用散列表實現一個電話薄。
主要功能如下：
加入聯系人及電話號碼。
通過查找對應名稱首字母，得到所有該首字母名稱的聯系人。
圖解如下：
代碼如下：
# 創建一個telBook的散列表
telBook = dict()
# 將A-Z的字母作為telBook的Key，Value還是一個散列表
for ch in xrange(0x41, 0x5A):
telBook[unichr(ch)] = dict()
# 將聯系人加入telBook中，取首字母作為第一個Key，名稱作為第二個Key，電話作為第二個Key的Value。
def addFriend(name, phoneNumber):
telBook[name[0:1]][name] = phoneNumber
addFriend("QiShare1", 13800000000)
addFriend("QiShare2", 13811111111)
addFriend("QiShare3", 13822222222)
addFriend("QiShare4", 13833333333)
addFriend("QiShare5", 13844444444)
addFriend("QiShare6", 13855555555)
addFriend("Police", 110)
addFriend("XiaoMing1", 1)
addFriend("XiaoMing2", 2)
addFriend("XiaoMing3", 3)
# 輸出結果：
for ch in xrange(0x41, 0x5A):
if telBook[unichr(ch)]:
print unichr(ch)+":"
print telBook[unichr(ch)]
打印結果如下：
小編微信：可加并拉入《QiShare技術交流群》。
關注我們的途徑有：
QiShare(簡書)
QiShare(掘金)
QiShare(知乎)
QiShare(GitHub)
QiShare(CocoaChina)
QiShare(StackOverflow)
QiShare(微信公眾號)
推薦文章：
iOS UIButton根據內容自動布局
iOS 指定初始化方法
UIView中的hitTest方法
iOS關于tabBar的幾處筆記
A的女兒是B的女兒的媽媽，A是B的誰？
算法小專欄：選擇排序
iOS Runloop（一）
奇舞周刊
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/6756.html
摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...
摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...
摘要：散列是一種算法通過散列函數，將大型可變長度數據集映射為固定長度的較小整數數據集。在討論散列函數的實現之前，讓我們討論理想的情況完美的散列函數。對于標準二次探測沖突解決方法，當哈希表的時，插入可能失敗。? 目錄 簡介 散列表的關鍵概念 數組和散列表 數組的問題 hash的問題 線性探測 二次探測 雙倍散列 分離鏈接 ...
閱讀 1011·2019-08-30 15:55
閱讀 3451·2019-08-30 13:10
閱讀 1277·2019-08-29 18:45
閱讀 2355·2019-08-29 16:25
閱讀 2116·2019-08-29 15:13
閱讀 2430·2019-08-29 11:29
閱讀 561·2019-08-26 17:34
閱讀 1496·2019-08-26 13:57
