什么是Python中的哈希表?相信很多沒有經(jīng)驗(yàn)的人對此束手無策,為此本文總結(jié)了問題出現(xiàn)的原因和解決方法,通過這篇文章希望你能解決這個問題。
新沂網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司,新沂網(wǎng)站設(shè)計(jì)制作,有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為新沂1000多家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)公司要多少錢,請找那個售后服務(wù)好的新沂做網(wǎng)站的公司定做!
散列表(哈希表)
散列表:所有的元素之間沒有任何關(guān)系。元素的存儲位置,是利用元素的關(guān)鍵字通過某個函數(shù)直接計(jì)算出來的。這個一一對應(yīng)的關(guān)系函數(shù)稱為散列函數(shù)或Hash函數(shù)。
采用散列技術(shù)將記錄存儲在一塊連續(xù)的存儲空間中,稱為散列表或哈希表(Hash Table)。關(guān)鍵字對應(yīng)的存儲位置,稱為散列地址。
散列表是一種面向查找的存儲結(jié)構(gòu)。它最適合求解的問題是查找與給定值相等的記錄。但是對于某個關(guān)鍵字能對應(yīng)很多記錄的情況就不適用,比如查找所有的“男”性。也不適合范圍查找,比如查找年齡20~30之間的人。排序、最大、最小等也不合適。
因此,散列表通常用于關(guān)鍵字不重復(fù)的數(shù)據(jù)結(jié)構(gòu)。比如python的字典數(shù)據(jù)類型。
設(shè)計(jì)出一個簡單、均勻、存儲利用率高的散列函數(shù)是散列技術(shù)中最關(guān)鍵的問題。
但是,一般散列函數(shù)都面臨著沖突的問題。
沖突:兩個不同的關(guān)鍵字,通過散列函數(shù)計(jì)算后結(jié)果卻相同的現(xiàn)象。collision。
散列函數(shù)的構(gòu)造方法
好的散列函數(shù):計(jì)算簡單、散列地址分布均勻
直接定址法
例如取關(guān)鍵字的某個線性函數(shù)為散列函數(shù):
f(key) = a*key + b (a,b為常數(shù))數(shù)字分析法
抽取關(guān)鍵字里的數(shù)字,根據(jù)數(shù)字的特點(diǎn)進(jìn)行地址分配平方取中法
將關(guān)鍵字的數(shù)字求平方,再截取部分折疊法
將關(guān)鍵字的數(shù)字分割后分別計(jì)算,再合并計(jì)算,一種玩弄數(shù)字的手段。除留余數(shù)法
最為常見的方法之一。
對于表長為m的數(shù)據(jù)集合,散列公式為:
f(key) = key mod p (p<=m)
mod:取模(求余數(shù))
該方法最關(guān)鍵的是p的選擇,而且數(shù)據(jù)量較大的時(shí)候,沖突是必然的。一般會選擇接近m的質(zhì)數(shù)。隨機(jī)數(shù)法
選擇一個隨機(jī)數(shù),取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址。
f(key) = random(key)
總結(jié),實(shí)際情況下根據(jù)不同的數(shù)據(jù)特性采用不同的散列方法,考慮下面一些主要問題:
計(jì)算散列地址所需的時(shí)間關(guān)鍵字的長度散列表的大小關(guān)鍵字的分布情況記錄查找的頻率
處理散列沖突
開放定址法
就是一旦發(fā)生沖突,就去尋找下一個空的散列地址,只要散列表足夠大,空的散列地址總能找到,并將記錄存入。
公式是:
這種簡單的沖突解決辦法被稱為線性探測,無非就是自家的坑被占了,就逐個拜訪后面的坑,有空的就進(jìn),也不管這個坑是不是后面有人預(yù)定了的。
線性探測帶來的最大問題就是沖突的堆積,你把別人預(yù)定的坑占了,別人也就要像你一樣去找坑。
改進(jìn)的辦法有二次方探測法和隨機(jī)數(shù)探測法。
再散列函數(shù)法
發(fā)生沖突時(shí)就換一個散列函數(shù)計(jì)算,總會有一個可以把沖突解決掉,它能夠使得關(guān)鍵字不產(chǎn)生聚集,但相應(yīng)地增加了計(jì)算的時(shí)間。
鏈接地址法
碰到?jīng)_突時(shí),不更換地址,而是將所有關(guān)鍵字為同義詞的記錄存儲在一個鏈表里,在散列表中只存儲同義詞子表的頭指針,如下圖:
這樣的好處是,不怕沖突多;缺點(diǎn)是降低了散列結(jié)構(gòu)的隨機(jī)存儲性能。本質(zhì)是用單鏈表結(jié)構(gòu)輔助散列結(jié)構(gòu)的不足。
公共溢出區(qū)法
其實(shí)就是為所有的沖突,額外開辟一塊存儲空間。如果相對基本表而言,沖突的數(shù)據(jù)很少的時(shí)候,使用這種方法比較合適。
散列表查找實(shí)現(xiàn)
下面是一段簡單的實(shí)現(xiàn)代碼:
#!/usr/bin/env python # -*- coding:utf-8 -*- # Author: Liu Jiang # Python 3.5 # 忽略了對數(shù)據(jù)類型,元素溢出等問題的判斷。 class HashTable: def __init__(self, size): self.elem = [None for i in range(size)] # 使用list數(shù)據(jù)結(jié)構(gòu)作為哈希表元素保存方法 self.count = size # 最大表長 def hash(self, key): return key % self.count # 散列函數(shù)采用除留余數(shù)法 def insert_hash(self, key): """插入關(guān)鍵字到哈希表內(nèi)""" address = self.hash(key) # 求散列地址 while self.elem[address]: # 當(dāng)前位置已經(jīng)有數(shù)據(jù)了,發(fā)生沖突。 address = (address+1) % self.count # 線性探測下一地址是否可用 self.elem[address] = key # 沒有沖突則直接保存。 def search_hash(self, key): """查找關(guān)鍵字,返回布爾值""" star = address = self.hash(key) while self.elem[address] != key: address = (address + 1) % self.count if not self.elem[address] or address == star: # 說明沒找到或者循環(huán)到了開始的位置 return False return True if __name__ == '__main__': list_a = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34] hash_table = HashTable(12) for i in list_a: hash_table.insert_hash(i) for i in hash_table.elem: if i: print((i, hash_table.elem.index(i)), end=" ") print("\n") print(hash_table.search_hash(15)) print(hash_table.search_hash(33))
散列表查找性能分析
如果沒發(fā)生沖突,則其查找時(shí)間復(fù)雜度為O(1),屬于最極端的好了。
但是,現(xiàn)實(shí)中沖突可不可避免的,下面三個方面對查找性能影響較大:
散列函數(shù)是否均勻處理沖突的辦法散列表的裝填因子(表內(nèi)數(shù)據(jù)裝滿的程度)
看完上述內(nèi)容,你們掌握什么是Python中的哈希表的方法了嗎?如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容,歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道,感謝各位的閱讀!