學(xué)習(xí)筆記
學(xué)習(xí)書(shū)目：《算法圖解》- Aditya Bhargava

---

文章目錄

• • • 散列函數(shù)
    • • 防止重復(fù)
    • 沖突
    • 性能
    • • 填裝因子

---

散列函數(shù)

散列函數(shù)是這樣的一個(gè)函數(shù)，即無(wú)論你給它什么樣的數(shù)據(jù)，它都還你一個(gè)數(shù)字。如果用專業(yè)術(shù)語(yǔ)來(lái)表達(dá)的話，我們可以說(shuō)，散列函數(shù)“將輸入映射到數(shù)字”。

我們可以認(rèn)為散列函數(shù)輸出的數(shù)字沒(méi)啥規(guī)律，但是散列函數(shù)還是有一些必須要滿足的要求的：

• 它必須是一致的。例如，假設(shè)你輸入apple時(shí)得到的是4，那么每次輸入apple時(shí)，得到的都必須為4。
• 它應(yīng)將不同的輸入映射到不同的數(shù)字。

散列函數(shù)將輸入映射成數(shù)字，有啥用呢？

為了回答這個(gè)問(wèn)題，我們構(gòu)建一個(gè)空數(shù)組：

假如我有一個(gè)小商店，我要將商品的價(jià)格存儲(chǔ)在這個(gè)數(shù)組中。

現(xiàn)在，我想先把a(bǔ)pple的價(jià)格存入數(shù)組，則我將apple作為輸入交給散列函數(shù)，并得到其輸出為3，那么我們就把a(bǔ)pple的價(jià)格存儲(chǔ)到數(shù)組的索引3處;緊接著，我想將milk的價(jià)格存入數(shù)組，按照同樣的步驟得到散列函數(shù)的輸出0，則我們把milk的價(jià)格存儲(chǔ)到數(shù)組的索引0處.不斷重復(fù)這個(gè)步驟，直至數(shù)組填滿：

如果，我現(xiàn)在想知道pen的價(jià)格，我不用在數(shù)組中查找，只需要將pen作為輸入交給散列函數(shù)，散列函數(shù)告訴我pen的價(jià)格存儲(chǔ)在數(shù)組的索引4處，那么我們就得到了pen的價(jià)格20.5

散列函數(shù)會(huì)準(zhǔn)確的幫助我們找到商品價(jià)格的存儲(chǔ)位置，我們不用自己去查找。之所以散列函數(shù)可以這樣做，是因?yàn)橐韵聨c(diǎn)：

• 散列函數(shù)總是將同樣的輸入映射到相同的索引。
• 散列函數(shù)將不同的輸入映射到不同的索引。
• 散列函數(shù)知道數(shù)組有多大，只返回有效的索引。

我們可以結(jié)合散列函數(shù)和數(shù)組創(chuàng)建一種被稱為散列表的數(shù)據(jù)結(jié)構(gòu)。散列表是一種包含額外邏輯的數(shù)據(jù)結(jié)構(gòu)。數(shù)組和鏈表都被直接映射到內(nèi)存，但散列表更復(fù)雜，它使用散列函數(shù)來(lái)確定元素的存儲(chǔ)位置。在我們之后將學(xué)習(xí)的復(fù)雜數(shù)據(jù)結(jié)構(gòu)中，散列表可能是最有用的，也被稱為散列映射、映射、字典和關(guān)聯(lián)數(shù)組。

Python提供的散列表實(shí)現(xiàn)為字典，我們可使用函數(shù)dict來(lái)創(chuàng)建散列表。

shop = dict()

創(chuàng)建散列表shop之后，我們?cè)谄渲刑砑右恍┥唐芳捌鋬r(jià)格：

shop['apple'] = 3.5 shop['milk'] = 15.0 shop['pen'] = 20.5

我們看一下剛剛創(chuàng)建的字典：

In [67]: shop Out[67]: {'apple': 3.5, 'milk': 15.0, 'pen': 20.5}

再利用字典查看一下pen的價(jià)格：

In [68]: shop['pen'] Out[68]: 20.5

散列表由鍵和值組成。在散列表shop中，鍵為商品名，值為商品價(jià)格。散列表將鍵映射到值。

防止重復(fù)

剛才我已經(jīng)開(kāi)了一個(gè)小商店，我每天要登記新進(jìn)的商品，并把新商品的名稱及其價(jià)格登記在我的散列表中。為了防止登記重復(fù)，我會(huì)在登記新商品之前，先檢查一下散列表中是否已經(jīng)登記過(guò)該商品，如果我發(fā)現(xiàn)已經(jīng)登記了該商品(函數(shù)get返回該商品價(jià)格)，那我就不登記它，如果沒(méi)有登記過(guò)(函數(shù)get返回None)，那我就登記它：

In [70]: print(shop.get('orange')) NoneIn [71]: print(shop.get('pen')) 20.5

現(xiàn)在我們構(gòu)造一個(gè)函數(shù)，來(lái)判斷是否登記過(guò)某商品：

def check_pro(name, price):if shop.get(name) is None:shop[name] = priceprint('Register now')else:print('Item already exists')

控制臺(tái)調(diào)用：

In [78]: check_pro('book', 30) Register nowIn [79]: check_pro('book', 30) Item already exists

沖突

在解釋沖突之前，我想先舉個(gè)例子方便理解。

假設(shè)我有一個(gè)數(shù)組，它有26個(gè)位置。我的散列函數(shù)規(guī)則很簡(jiǎn)單，它按照商品首字母的順序分配商品價(jià)格在數(shù)組中的存儲(chǔ)位置。這時(shí)，我們可能會(huì)提出疑問(wèn)：如果我有兩個(gè)商品book和bunny，它們的首字母都相同，那么我該怎么存儲(chǔ)呢？如果我先存儲(chǔ)了book的價(jià)格，它在數(shù)組的索引1處，那么當(dāng)我存儲(chǔ)bunny的價(jià)格時(shí)，該咋辦呢？這種情況就叫做沖突：給兩個(gè)鍵分配相同的位置。

處理沖突的方法有很多，最簡(jiǎn)單的就是下面這種：

如果兩個(gè)鍵映射到了同一個(gè)位置，就在這個(gè)位置存儲(chǔ)一個(gè)鏈表。

我們看到，book和bunny映射到了同一個(gè)位置，因此在這個(gè)位置存儲(chǔ)一個(gè)鏈表。在查詢apple的價(jià)格時(shí)，速度依然很快，但在查詢bunny的價(jià)格時(shí)，速度要慢些：你必須在相應(yīng)的鏈表中找到bunny.

我們可能會(huì)覺(jué)得這個(gè)鏈表很短，沒(méi)什么大不了的。但是，如果我的商店進(jìn)的大部分商品的商品名稱都是以b開(kāi)頭的，那這個(gè)鏈表將會(huì)相當(dāng)?shù)拈L(zhǎng)，我們用這個(gè)散列表的速度將會(huì)很慢，這是一個(gè)非常糟糕的狀況。

這里總結(jié)了兩點(diǎn)經(jīng)驗(yàn)：

• 散列函數(shù)很重要。前面的散列函數(shù)將所有的鍵都映射到一個(gè)位置，而最理想的情況是，散列函數(shù)將鍵均勻地映射到散列表的不同位置。
• 如果散列表存儲(chǔ)的鏈表很長(zhǎng)，散列表的速度將急劇下降。然而，如果使用的散列函數(shù)很好，這些鏈表就不會(huì)很長(zhǎng)。

散列函數(shù)很重要，好的散列函數(shù)能很少會(huì)導(dǎo)致沖突。

性能

在平均情況下，散列表執(zhí)行各種操作(查找、插入、刪除)的時(shí)間都為$O(1)$. $O(1)$被稱為常量時(shí)間，它并不意味著馬上，而是說(shuō)不管散列表多大，所需的時(shí)間都相同。

下面我們來(lái)比較線性時(shí)間、對(duì)數(shù)時(shí)間和常量時(shí)間：

我們看到上面第三幅圖中，表示運(yùn)行時(shí)間的曲線是水平的。這意味著平均情況下，無(wú)論散列表包含1個(gè)元素還是10億個(gè)元素，從其中獲取數(shù)據(jù)所需的時(shí)間都相同。

但在糟糕的情況下，散列表所有操作的運(yùn)行時(shí)間都為$O(n)$，即線性時(shí)間，這真的是很慢了。因此，為了避免沖突，需要有：

• 較低的填裝因子
• 良好的散列函數(shù)

填裝因子

散列表的填裝因子很容易計(jì)算，即：散列表包含的元素?cái)?shù)/位置總數(shù)。由此可知，填裝因子度量的是散列表中有多少位置是空的。

散列表使用數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)，因此我們需要計(jì)算數(shù)組中被占用的位置數(shù)。例如下面的散列表的填裝因子為2/5：

如果此時(shí)，我們的散列表只有50個(gè)位置，但是我要存儲(chǔ)100件商品的價(jià)格，那么填裝因子將為2.填裝因子大于1則意味著，商品數(shù)量超過(guò)了數(shù)組的位置數(shù)。一旦填裝因子開(kāi)始增大，我們就需要在散列表中添加位置，這被稱為調(diào)整長(zhǎng)度。

例如，假設(shè)我的散列表有4個(gè)位置，我已經(jīng)存儲(chǔ)了3個(gè)商品價(jià)格，那么填裝因子為3/4.此時(shí)，為了調(diào)整長(zhǎng)度，我會(huì)先創(chuàng)建一個(gè)更長(zhǎng)的新數(shù)組(通常將原數(shù)組增長(zhǎng)1倍)，這個(gè)新數(shù)組有8個(gè)位置，接下來(lái)，我需要使用函數(shù)hash將所有的元素都插入到這個(gè)新的散列表中，那么這個(gè)新散列表的填裝因子為3/8,比原來(lái)低得多。填裝因子越小，發(fā)送沖突可能性就越小。一個(gè)不錯(cuò)的經(jīng)驗(yàn)規(guī)則是：一旦填裝因子大于0.7，就調(diào)整散列表的長(zhǎng)度。

總結(jié)

以上是生活随笔為你收集整理的小白的算法初识课堂(part5)--散列表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。