详解Python中的可哈希对象与不可哈希对象（二）
前言：我们经常会听见很多的概念，哈希值，哈希表，可哈希对象，不可哈希对象，散列表，字典，映射，等等，那么这么多的概念后面到底又有什么区别和联系，它们的本质又是怎么样的，本此系列文章将针对这些概念进行说明，鉴于篇幅较多，本次系列文章将分为两篇来说明，此为第二篇，会涉及到以下概念，可变对象mutable与不可变对象inmutable，可哈希hashable与不可哈希unhashable，为什么字典dict的键Key一定要是可哈希的？前一篇文章参考：https://blog.csdn.net/qq_27825451/article/details/102820692一、可哈希对象与不可哈希对象的直观理解前提：能够较好地理解什么是可变对象mutable与不可变对象inmutable。以及明白哈希值value的唯一性。1.1 什么是可哈希(hashable)？简要的说可哈希的数据类型，即不可变的数据结构(数字类型（int，float，bool）字符串str、元组tuple、自定义类的对象)。（1）为什么不可变数据类型是可哈希hashable的呢？哈希有啥作用？对于不可变类型而言，不同的值意味着不同的内存，相同的值存储在相同的内存，如果将我们的不可变对象理解成哈希表中的Key,将内存理解为经过哈希运算的哈希值Value，这不正好满足哈希表的性质嘛。如下：a=100b=100c=101id(a) #1420082496id(b) #1420082496 # a,b是一样的id(c) #1420082528 # c是不一样的当然了，这不是说哈希值就是id地址，这还是不一样的，参见下面：In [21]: hash(a)Out[21]: 100 # 并不是说哈希值就是它本身哈，一个对象的哈希值是什么取决于__hash__魔术方法的运算过程In [22]: hash(b)Out[22]: 100In [23]: hash(c)Out[23]: 101再看一个例子：In [24]: x="ilove"In [25]: y="i"+"love"In [26]: z="iloveyou"In [27]: id(x),id(y),id(z)Out[27]: (3122841661600, 3122841661600, 3122841929584)# x,y的id是一样的In [28]: hash(x),hash(y),hash(z)Out[28]: (4255912298523051991, 4255912298523051991, -3820205610162521985) # x,y 的哈希值是一样的1.2 什么是不可哈希(unhashable)？同理，不可哈希的数据类型，即可变的数据结构 (字典dict，列表list，集合set)对于可变对象而言，比如一个列表，更改列表的值，但是对象的地址本身是不变的，也就是说不同的Key,映射到了相同的Value，这显然是不符合哈希值的特性的，即出现了哈希运算里面的冲突。如下：a=[1,2,3]print(id(a))def func(p): p.append(4) return pb=func(a)print(id(b))'''2399750863880 是一样的哦2399750863880'''如果此时对a和b使用hash函数，则会出错，如下：TypeError: unhashable type: 'list'总结：上面的说明仅仅是感性上的认识哦，并不是本质原因哈！二、从实质上来理解hashable和unhashable对象2.1 什么是hashable(可哈希性)An object is hashable if it has a hash value which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__()or __cmp__() method). Hashable objects which compare equal must have the same hash value.如果一个对象是可哈希的,那么在它的生存期内必须不可变(而且该对象需要一个哈希函数),而且可以和其他对象比较(需要比较方法).比较值相同的对象一定有相同的哈希值，即一个对象必须要包含有以下几个魔术方法：[*]__eq__():用于比较两个对象是否相等
[*]__cmp__():用于比较两个对象的大小关系，它与__eq__只要有一个就可以了
[*]__hash__()：实际上就是哈希函数（散列函数），返回经过运算得到的哈希值
前面既然说了整数int是可哈希对象，不放我们看一下它具不具备这几个魔术方法：In [51]: a=100In [52]: dir(a)Out[52]:[... '__eq__', ... '__hash__',...]我们发现他的确具有上面说的这几个魔术方法。列表是不可哈希的，我们看一下列表的魔术方法有哪一些：In [54]: a=[1,2,3]In [55]: dir(a)Out[55]:[... '__eq__',... '__hash__',...']我们发现一个问题，为什么可变对象list明明是不可哈希的，为什么也有着两个方法呢？因为所有类型的基类object中实现了这两个魔术方法，但是并不是说有这两个方法就一定是可哈希的，关键是要如何实现__eq__()方法和__hash__()方法，list并没有实现，只是有这几个魔术方法而已，在实现的里面出发了上面的异常。我们可以看一下基类object的魔术方法，如下：In [56]: dir(object)Out[56]:[... '__eq__', ... '__hash__',...]2.2 自定义类型的对象是不是可哈希的呢？看一下如下代码：class Animal: def __init__(self, name): self.name=name def eat(self): print("i love eat !")a=Animal("dog")print(hash(a))# 83529594295我们发现自定义的类的对象是可哈希的，虽然我们不知道这个哈希值是如何得到的，但是我们知道他的确是可哈希对象。前面说了哈希值的计算实际上是通过__hash__魔术方法来实现的，我们不妨自定义一下类的魔术方法，如下：class Animal: def __init__(self, name): self.name=name def __hash__(self):# 自定义哈希函数 return 1000 # 注意哈希函数的返回值要是integer哦！ def eat(self): print("i love eat !")a=Animal("dog")print(hash(a))# 返回 1000现在对于什么是python的可哈希对象和哈希函数如何实现应该有了比较清楚的了解了。三、为什么字典 key 必须是不可变的（可哈希hashable）？3.1 字典如何在 CPython 中实现？CPython 的字典实现为可调整大小的哈希表。与 B-树相比，这在大多数情况下为查找（目前最常见的操作）提供了更好的性能，并且实现更简单。字典的工作方式是使用 hash() 内置函数计算字典中存储的每个键的 hash 代码。hash 代码根据键和每个进程的种子而变化很大；例如，"Python" 的 hash 值为-539294296，而"python"(一个按位不同的字符串)的 hash 值为 1142331976。然后，hash 代码用于计算内部数组中将存储该值的位置。假设您存储的键都具有不同的 hash 值，这意味着字典需要恒定的时间 -- O(1)，用 Big-O 表示法 -- 来检索一个键。3.2 字典 key 必须是不可变的（可哈希hashable）字典的哈希表实现使用从键值计算的哈希值来查找键。（1）为什么可变对象不能作为键Key？先来看一个简单的例子：d = {[1, 2]: '100'}# 构造一个字典，key是列表[1,2] ，是一个可变对象，是不可哈希的print(d[[1, 2]]) # 通过key去访问字典的值，触发keyerror异常为什么会触发异常呢？哈希按其地址（对象 id）列出的。在上面的两行代码中，第一行中的key是一个列表对象,第二行中要访问的的时候的那个key虽然也是，但是由于列表list是可变对象，虽然这两行的列表值一样，但是他们并不是同一个对象，它们的存储地址是不一样的，即id是不一样的，id不一样也导致了根据id计算得到的哈希值是不一样的，自然没有办法找到原来的那一个的哈希值在哪里了。注意：这需要能够很好的理解可变对象与不可变对象的内存分配才好哦！（2）为什么不可变对象能作为键Key？将上面例子中的列表换成元组（1,2），先来看一个简单的例子：d = {(1, 2): '100'}# 构造一个字典，key是元组(1,2) ，是一个不可变对象，是可哈希的print(d[(1, 2)]) # 通过key去访问字典的值，打印 '100'为什么这里不会触发异常呢？哈希按其地址（对象 id）列出的。在上面的两行代码中，第一行中的key是一个元组对象（1,2），第二行中要访问的的时候的那个key也是（1,2），但是由于元组tuple是不可变对象，那么这两行的元组值一样，所以它们的存储地址是一样的，即id是一样的，id一样也导致了根据id计算得到的哈希值是一样的，哈希值一样我自然可以搜索得到那个100在哪个地方了。（3）总结：字典的key一定要是不可变对象，要是能够哈希的对象，即hashable对象，包括：数字类型（int，float，bool）字符串str、元组tuple、自定义类的对象，这几类，比如下面的字典：class Animal: def __init__(self, name): self.name=name def __hash__(self):# 自定义哈希函数 return 1000 # 注意哈希函数的返回值要是integer哦！ def eat(self): print("i love eat !")a=Animal("dog")d={100:"a", # 整数作为key 100.1:"b", # 浮点数作为key True:"c", # 布尔值作为key "name":"d",# 字符串作为key (1,2):"e", # 元组作为key a:"f"} # 自定义对象作为keyfor k in d.keys(): print(d)'''abcdef'''
https://cloud.tencent.com/developer/article/1534815
页:
[1]