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