点击上方“机器学习与python集中营”,星标公众号 重磅干货,第一时间送达
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5iMjVjMwUTMmRGN2YWOyYGM1UmY4UWNkdDZkZmNzATYz8CX0JXZ252bj91Ztl2Lc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
☞机器学习、深度学习、python全栈开发干货 作者:草yang年华 来源:个人原创
前言:我们经常会听见很多的概念,哈希值,哈希表,可哈希对象,不可哈希对象,散列表,字典,映射,等等,那么这么多的概念后面到底又有什么区别和联系,它们的本质又是怎么样的,本此系列文章将针对这些概念进行说明,鉴于篇幅较多,本次系列文章将分为两篇来说明,此为第二篇,会涉及到以下概念,可变对象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,这不正好满足哈希表的性质嘛。如下:
当然了,这不是说哈希值就是id地址,这还是不一样的,参见下面:
再看一个例子:
1.2 什么是不可哈希(unhashable)?
同理,不可哈希的数据类型,即可变的数据结构 (字典dict,列表list,集合set)
对于可变对象而言,比如一个列表,更改列表的值,但是对象的地址本身是不变的,也就是说不同的Key,映射到了相同的Value,这显然是不符合哈希值的特性的,即出现了哈希运算里面的冲突。如下:
如果此时对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 [54]: a=[1,2,3]
In [55]: dir(a)
Out[55]:
[...
'__eq__',
...
'__hash__',
...
']
我们发现一个问题,为什么可变对象list明明是不可哈希的,为什么也有着两个方法呢?
因为所有类型的基类object中实现了这两个魔术方法,但是并不是说有这两个方法就一定是可哈希的,关键是要如何实现__eq__()方法和__hash__()方法,list并没有实现,只是有这几个魔术方法而已,在实现的里面出发了上面的异常。我们可以看一下基类object的魔术方法,如下:
2.2 自定义类型的对象是不是可哈希的呢?
看一下如下代码:
我们发现自定义的类的对象是可哈希的,虽然我们不知道这个哈希值是如何得到的,但是我们知道他的确是可哈希对象。
前面说了哈希值的计算实际上是通过__hash__魔术方法来实现的,我们不妨自定义一下类的魔术方法,如下:
现在对于什么是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?
先来看一个简单的例子:
为什么会触发异常呢?哈希按其地址(对象 id)列出的。在上面的两行代码中,第一行中的key是一个列表对象[1,2],第二行中要访问的的时候的那个key虽然也是[1,2],但是由于列表list是可变对象,虽然这两行的列表值一样,但是他们并不是同一个对象,它们的存储地址是不一样的,即id是不一样的,id不一样也导致了根据id计算得到的哈希值是不一样的,自然没有办法找到原来的那一个[1,2]的哈希值在哪里了。
注意:这需要能够很好的理解可变对象与不可变对象的内存分配才好哦!
(2)为什么不可变对象能作为键Key?
将上面例子中的列表[1,2]换成元组(1,2),先来看一个简单的例子:
为什么这里不会触发异常呢?哈希按其地址(对象 id)列出的。在上面的两行代码中,第一行中的key是一个元组对象(1,2),第二行中要访问的的时候的那个key也是(1,2),但是由于元组tuple是不可变对象,那么这两行的元组值一样,所以它们的存储地址是一样的,即id是一样的,id一样也导致了根据id计算得到的哈希值是一样的,哈希值一样我自然可以搜索得到那个100在哪个地方了。
(3)总结:
字典的key一定要是不可变对象,要是能够哈希的对象,即hashable对象,包括:
数字类型(int,float,bool)字符串str、元组tuple、自定义类的对象,这几类,比如下面的字典:
● 学习笔记:深度学习中的正则化
● 2019:全球十大突破性技术
● 深度神经网络经典模型结构-shufflenet系列
● Python 63个内置函数(上篇),你都ok吗?
● 【用python玩花样】python实现点阵字体
● python十道经典面试题,测试你的python功底!
机器学习与python集中营
有趣的灵魂在等你
长按扫码可关注
你点的每个赞,我都认真当成了喜欢