散列表

1.散列函數(shù)

散列函數(shù)是這樣的函數(shù)，即無(wú)論你給它什么數(shù)據(jù)，他都還給你一個(gè)數(shù)字。散列函數(shù)必須滿足一些要求：

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

為此，首先創(chuàng)建一個(gè)空數(shù)組。我們將在這個(gè)數(shù)組中存儲(chǔ)商品的價(jià)格。下面來(lái)將蘋果的價(jià)格加入到這個(gè)數(shù)組中。將apple作為輸入交給散列函數(shù)，散列函數(shù)輸出為3，因此我們將蘋果的價(jià)格存儲(chǔ)在數(shù)組的索引3處。以此類推，填滿整個(gè)數(shù)組。

假設(shè)現(xiàn)在我們需要知道apple的價(jià)格，我們無(wú)需再數(shù)組中查找，只需將apple交給散列函數(shù)，輸出3，我們直接在數(shù)組索引3處就能找到apple的價(jià)格。

我們結(jié)合散列函數(shù)和數(shù)組創(chuàng)建了一種被稱為散列表的數(shù)據(jù)結(jié)構(gòu)。數(shù)組和鏈表都被直接映射到內(nèi)存，但是散列表更復(fù)雜，它使用散列函數(shù)來(lái)確定元素的存儲(chǔ)位置。

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

book = dict() book["apple"] = 0.88 print book print book["apple"]

2.應(yīng)用案例

?2.1 將散列表用于查找

?2.2? 防止重復(fù)

?2.3 將散列表用作緩存

?

轉(zhuǎn)載于:https://www.cnblogs.com/winddogg/p/10811729.html

總結(jié)

以上是生活随笔為你收集整理的图解算法（五）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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