在Python中，僅僅只有不可變數(shù)據(jù)類型可以被hash,然而每個自定義的對象在Python中都可以被hash，默認(rèn)的他們的hash值是由他們的id派生的。也就意味著，同一個類的兩個不同實例，默認(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)在可以檢測哈希表，哈希表是一個數(shù)據(jù)結(jié)構(gòu)可以儲存一堆鍵值對。

在哈希表中，鍵值對的所有建必須是可以哈希的，因為存儲的對是通過使用其鍵的散列索引的。哈希表十分有用，Hashtablesareveryusefulbecausetheaveragenumberofinstructionsthatarenecessarytolookupanelementofthetableisindependentofthenumberofelementsstoredinthetableitself.哈希表非常有用，因為查找表中某個元素所需的平均指令數(shù)量與表中存儲的元素數(shù)量無關(guān)，這就表明了不管你的表增長到成百上千次，查找特定元素的速度不會受到影響。

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

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ù)增加越多，浪費的空間就越多。要測試這一點，只需使用輸入列表長度的兩倍的桶數(shù)來更改上一個示例的桶大小

兩個散列值發(fā)生碰撞，將會存儲到同一個桶中，因為沖突不可避免，實現(xiàn)一個哈希表就得有一個解決沖突的方法。

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

openaddressing開放尋址法

separatechaining鏈地址法

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

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

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