Python中可以hash的数据类型

　　在Python中，仅仅只有不可变数据类型可以被hash,然而每个自定义的对象在Python中都可以被hash，默认的他们的hash值是由他们的id派生的。也就意味着，同一个类的两个不同实例，默认的是得到不同的hash值

　　>>> class Car():

　　... velocity = 0

　　... direction = 0

　　... damage = 0

　　...

　　>>> first_car = Car()

　　>>> second_car = Car()

　　>>> hash(first_car)

　　274643597

　　>>> hash(second_car)

　　274643604

　　哈希表

　　现在你知道了什么是哈希函数，现在可以检测哈希表，哈希表是一个数据结构可以储存一堆键值对。

　　在哈希表中，键值对的所有建必须是可以哈希的，因为存储的对是通过使用其键的散列索引的。哈希表十分有用，Hash tables are very useful because the average number of instructions that are necessary to lookup an element of the table is independent of the number of elements stored in the table itself.哈希表非常有用，因为查找表中某个元素所需的平均指令数量与表中存储的元素数量无关，这就表明了不管你的表增长到成百上千次，查找特定元素的速度不会受到影响。

　　哈希表通常是通过创建可变数量的存储桶来实现的，这些存储桶将包含您的数据，并通过哈希它们的键对这些数据进行索引。键的散列值将确定用于特定数据段的正确存储桶。

　　import pprint

　　class Hashtable:

　　def __init__(self, elements):

　　self.bucket_size = len(elements)

　　self.buckets = [[] for i in range(self.bucket_size)]

　　self._assign_buckets(elements)

　　def _assign_buckets(self, elements):

　　for key, value in elements:

　　hashed_value = hash(key)

　　index = hashed_value % self.bucket_size

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

　　def get_value(self, input_key):

　　hashed_value = hash(input_key)

　　index = hashed_value % self.bucket_size

　　bucket = self.buckets[index]

　　for key, value in bucket:

　　if key == input_key:

　　return(value)

　　return None

　　def __str__(self):

　　return pprint.pformat(self.buckets) # here pformat is used to return a printable representation of the object

　　if __name__ == "__main__":

　　capitals = [

　　('France', 'Paris'),

　　('United States', 'Washington D.C.'),

　　('Italy', 'Rome'),

　　('Canada', 'Ottawa')

　　]

　　hashtable = Hashtable(capitals)

　　print(hashtable)

　　print(f"The capital of Italy is {hashtable.get_value('Italy')}")

　　Moreover, the more you increase the number of buckets you will handle, the more space you will waste. To test this you can simply change the bucket size of your previous example using a number of buckets that is two times the length of the input list:

　　此外，处理的桶数增加越多，浪费的空间就越多。要测试这一点，只需使用输入列表长度的两倍的桶数来更改上一个示例的桶大小

　　两个散列值发生碰撞，将会存储到同一个桶中，因为冲突不可避免，实现一个哈希表就得有一个解决冲突的方法。

　　通常在哈希表解决冲突的常用策略是：

　　open addressing 开放寻址法

　　separate chaining 链地址法

　　连地址法是您在上面的示例中已经实现的，它由使用另一个数据结构在同一个bucket中创建一个值链组成。在那个示例中，您使用了一个嵌套列表，当在超额占用的bucket中查找特定值时，必须对该列表进行完全扫描。

　　在开放寻址策略中，如果您应该使用的bucket是忙碌的，那么您只需继续搜索要使用的新bucket。要实现这个解决方案，您需要对为新元素分配bucket的方式和检索键值的方式进行一些更改。从assign buckets()函数开始，您必须使用默认值初始化您的bucket，并且如果您应该使用的bucket已经被占用，则继续寻找空的bucket

　　以上内容为大家介绍了Python中可以hash的数据类型，希望对大家有所帮助，如果想要了解更多Python相关知识，请关注多测师。https://www.e70w.com/xwzx/