在Python中，僅僅只有不可變數(shù)據(jù)類(lèi)型可以被hash,然而每個(gè)自定義的對(duì)象在Python中都可以被hash，默認(rèn)的他們的hash值是由他們的id派生的。也就意味著，同一個(gè)類(lèi)的兩個(gè)不同實(shí)例，默認(rèn)的是得到不同的hash值

>>>classCar():

...velocity=0

...direction=0

...damage=0

...

>>>first_car=Car()

>>>second_car=Car()

>>>hash(first_car)

274643597

>>>hash(second_car)

274643604

哈希表

現(xiàn)在你知道了什么是哈希函數(shù)，現(xiàn)在可以檢測(cè)哈希表，哈希表是一個(gè)數(shù)據(jù)結(jié)構(gòu)可以?xún)?chǔ)存一堆鍵值對(duì)。

在哈希表中，鍵值對(duì)的所有建必須是可以哈希的，因?yàn)榇鎯?chǔ)的對(duì)是通過(guò)使用其鍵的散列索引的。哈希表十分有用，Hashtablesareveryusefulbecausetheaveragenumberofinstructionsthatarenecessarytolookupanelementofthetableisindependentofthenumberofelementsstoredinthetableitself.哈希表非常有用，因?yàn)椴檎冶碇心硞€(gè)元素所需的平均指令數(shù)量與表中存儲(chǔ)的元素?cái)?shù)量無(wú)關(guān)，這就表明了不管你的表增長(zhǎng)到成百上千次，查找特定元素的速度不會(huì)受到影響。

哈希表通常是通過(guò)創(chuàng)建可變數(shù)量的存儲(chǔ)桶來(lái)實(shí)現(xiàn)的，這些存儲(chǔ)桶將包含您的數(shù)據(jù)，并通過(guò)哈希它們的鍵對(duì)這些數(shù)據(jù)進(jìn)行索引。鍵的散列值將確定用于特定數(shù)據(jù)段的正確存儲(chǔ)桶。

importpprint

classHashtable:

def__init__(self,elements):

self.bucket_size=len(elements)

self.buckets=[[]foriinrange(self.bucket_size)]

self._assign_buckets(elements)

def_assign_buckets(self,elements):

forkey,valueinelements:

hashed_value=hash(key)

index=hashed_value%self.bucket_size

self.buckets[index].append((key,value))

defget_value(self,input_key):

hashed_value=hash(input_key)

index=hashed_value%self.bucket_size

bucket=self.buckets[index]

forkey,valueinbucket:

ifkey==input_key:

return(value)

returnNone

def__str__(self):

returnpprint.pformat(self.buckets)#herepformatisusedtoreturnaprintablerepresentationoftheobject

if__name__=="__main__":

capitals=[

('France','Paris'),

('UnitedStates','WashingtonD.C.'),

('Italy','Rome'),

('Canada','Ottawa')

]

hashtable=Hashtable(capitals)

print(hashtable)

print(f"ThecapitalofItalyis{hashtable.get_value('Italy')}")

Moreover,themoreyouincreasethenumberofbucketsyouwillhandle,themorespaceyouwillwaste.Totestthisyoucansimplychangethebucketsizeofyourpreviousexampleusinganumberofbucketsthatistwotimesthelengthoftheinputlist:

此外，處理的桶數(shù)增加越多，浪費(fèi)的空間就越多。要測(cè)試這一點(diǎn)，只需使用輸入列表長(zhǎng)度的兩倍的桶數(shù)來(lái)更改上一個(gè)示例的桶大小

兩個(gè)散列值發(fā)生碰撞，將會(huì)存儲(chǔ)到同一個(gè)桶中，因?yàn)闆_突不可避免，實(shí)現(xiàn)一個(gè)哈希表就得有一個(gè)解決沖突的方法。

通常在哈希表解決沖突的常用策略是：

openaddressing開(kāi)放尋址法

separatechaining鏈地址法

連地址法是您在上面的示例中已經(jīng)實(shí)現(xiàn)的，它由使用另一個(gè)數(shù)據(jù)結(jié)構(gòu)在同一個(gè)bucket中創(chuàng)建一個(gè)值鏈組成。在那個(gè)示例中，您使用了一個(gè)嵌套列表，當(dāng)在超額占用的bucket中查找特定值時(shí)，必須對(duì)該列表進(jìn)行完全掃描。

在開(kāi)放尋址策略中，如果您應(yīng)該使用的bucket是忙碌的，那么您只需繼續(xù)搜索要使用的新bucket。要實(shí)現(xiàn)這個(gè)解決方案，您需要對(duì)為新元素分配bucket的方式和檢索鍵值的方式進(jìn)行一些更改。從assignbuckets()函數(shù)開(kāi)始，您必須使用默認(rèn)值初始化您的bucket，并且如果您應(yīng)該使用的bucket已經(jīng)被占用，則繼續(xù)尋找空的bucket

以上內(nèi)容為大家介紹了Python中可以hash的數(shù)據(jù)類(lèi)型，希望對(duì)大家有所幫助，如果想要了解更多Python相關(guān)知識(shí)，請(qǐng)關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。