在Python中，僅僅只有不可變數據類型可以被hash,然而每個自定義的對象在Python中都可以被hash，默認的他們的hash值是由他們的id派生的。也就意味著，同一個類的兩個不同實例，默認的是得到不同的hash值

>>>classCar():

...velocity=0

...direction=0

...damage=0

...

>>>first_car=Car()

>>>second_car=Car()

>>>hash(first_car)

274643597

>>>hash(second_car)

274643604

哈希表

現在你知道了什么是哈希函數，現在可以檢測哈希表，哈希表是一個數據結構可以儲存一堆鍵值對。

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

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

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:

此外，處理的桶數增加越多，浪費的空間就越多。要測試這一點，只需使用輸入列表長度的兩倍的桶數來更改上一個示例的桶大小

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

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

openaddressing開放尋址法

separatechaining鏈地址法

連地址法是您在上面的示例中已經實現的，它由使用另一個數據結構在同一個bucket中創建一個值鏈組成。在那個示例中，您使用了一個嵌套列表，當在超額占用的bucket中查找特定值時，必須對該列表進行完全掃描。

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

以上內容為大家介紹了Python中可以hash的數據類型，希望對大家有所幫助，如果想要了解更多Python相關知識，請關注IT培訓機構:千鋒教育。