Python中可以hash的数据类型

在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培训机构:开发教育。

鹏仔微信 15129739599 鹏仔QQ344225443 鹏仔前端 pjxi.com 共享博客 sharedbk.com