哈希表

Python 中set,dict都是基于哈希表的數(shù)據(jù)結(jié)構(gòu)，這兩個(gè)數(shù)據(jù)結(jié)構(gòu)有著廣泛的應(yīng)用。因此很有必要弄懂哈希表的原理。

哈希表

數(shù)組和鏈表是數(shù)據(jù)結(jié)構(gòu)的兩大基石，這個(gè)在前面我們多次提到過(guò)。哈希表的實(shí)現(xiàn)也正是基于數(shù)組和鏈表。

哈希表最大特點(diǎn)O(1)時(shí)間內(nèi)確定某元素是否位于容器中。下面探討它是如何基于數(shù)組和鏈表實(shí)現(xiàn)的。

實(shí)現(xiàn)原理

O(1)內(nèi)確定元素在不在的實(shí)現(xiàn)原理，一句話(huà)總結(jié)：

通過(guò)一種方法將元素值轉(zhuǎn)化為數(shù)組的index，如果index位置處為None則不存在，不為None則表明存在。

原理圖解

創(chuàng)建如下一個(gè)數(shù)組，長(zhǎng)度為9：

現(xiàn)在想把python字符串存儲(chǔ)到數(shù)組中，哈希表的一種做法如下：

• 使用Python的hash函數(shù)，

• 然后對(duì)數(shù)組長(zhǎng)度取余數(shù)，得到2，

• 最后將python存儲(chǔ)到數(shù)組索引2處

因此，判斷字符串python是否位于數(shù)組中時(shí)，

只需重復(fù)上面的先hash再取余，檢查索引2處是否為None，故時(shí)間復(fù)雜度為O(1).

鏈表解決哈希沖突

當(dāng)存儲(chǔ)10時(shí)，如上相同的存儲(chǔ)原理，計(jì)算后等于索引2，但是2處已經(jīng)有數(shù)據(jù)，

此時(shí)發(fā)生哈希沖突：

其中一種解決方法，在索引2處建立鏈表，鏈接到已有數(shù)據(jù)尾部：

以上就是哈希表最核心知識(shí)的扼要總結(jié)。原創(chuàng)不易，歡迎點(diǎn)贊支持。