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