欢迎光临杨雨的个人博客站!

杨雨个人网站-杨雨个人博客-杨照佳

杨雨个人博客网站

关注互联网和搜索引擎的个人博客网站

首页 > WEB开发 > Python教程 >

Tuple和List中,为什么只有前者才可以作为字典的key?

发布时间:2019-06-03  编辑:杨雨个人博客网站   点击:   

很多Python初学者经常会有这样的疑问,为什么Python有tuple(元组)和list(列表)两种类型?为什么tuple可以作为字典的key,list不可以?要理解这个问题,首先要明白python的字典工作原理。

PYTHON1.jpg

1.Python的字典是如何工作的

在Python中,字典也就是一个个的“映射”,将key映射到value:

# 对一个特定的key可以得到一个value

value = d[key]

为了实现这个功能,Python必须能够做到,给出一个key,找到哪一个value与这个key对应。先来考虑一种比较简单的实现,将所有的key-value键值对存放到一个list中,每当需要的时候,就去遍历这个list,用key去和键值对的key匹配,如果相等,就拿到value。但是这种实现在数据量很大的时候就变得很低效。它的算法复杂度是O(n),n是存放键值对的数量。(关于Hash表具体的工作原理,可以参考我的这篇文章。

为此,Python使用了hash(哈希)的方法来实现,要求每一个存放到字典中的对象都要实现hash函数,这个函数可以产生一个int值,叫做hash value(哈希值),通过这个int值,就可以快速确定对象在字典中的位置。然而,由于Hash碰撞的存在,可能存在两个对象的Hash值是相同的,所以查找字典的过程中,要比较hash值,还要比较value的值。

这个查询的大致过程如下:

def lookup(d, key):

字典的查询过程概括为下面3步:

1. 通过hash函数将key计算为哈希值.

2. 通过hash值确定一个位置,这个位置是一个存放着

可能存在冲突的元素的数组(很多地方叫做“桶”,bucket),

每一个元素都是一个键值对,理想情况下,这个数组里只有1个元素.

3. 遍历这个数组,找到目标key,返回对应的value.

h = hash(key)                  # step 1
    cl = d.data[h]                 # step 2
    for pair in cl:                # step 3
        if key == pair[0]:
            return pair[1]
    else:
        raise KeyError, "Key %s not found." % key

要使这个查找过程正常工作,hash函数必须满足条件:如果两个key产生了不同的hash value,那么这两个key对象是不相等的。即

for all i1, i2, if hash(i1) != hash(i2), then i1 != i2

否则的话,hash value不同,对象却相同,那么相同的对象产生不同的hash value,查找的时候就会进错桶(step 2),在错误的桶里永远也找不到你要找的value。

另外,要让字典保持高查找效率,还要保证:当两个key产生相同的hash value,那么他们是相等的。

for all i1, i2, if hash(i1) == hash(i2), then i1 == i2

这样做的目的是,尽量满足每个hash桶只有一个元素。为什么要这样呢? 考虑下面这个hash函数。

def hash(obj):

return 1

这个hash函数是满足上面我们谈的第一个条件的:如果两个key的hash value不同,那么两个key对象不相同。因为所有的对象产生的hash value都是1,所以不存在能产生不同hash value的key,也就不存在不满足的情况。但是这样做的坏处是,因为所有的hash value都相同,所以就把所有的对象分到了同一个地方。查找的时候,进行到第三步,遍历的效率就变成了O(n).

Hash函数应该保证所有的元素平均的分配到每一个桶中,理想的情况是,每一个位置只有一个元素。

以上两个原则,第一个保证了你能从字典中拿到要找的元素,第二个保证了查询效率。


2.字典Key要满足的要求

经过上面的讨论,我们应该明白Python为什么对字典的key有这样的要求了:

要作为字典的key,对象必须要支持hash函数(即__hash__),相等比较(__eq__或__cmp__),并且满足上面我们讨论过的条件。

3.List为什么不能作为key

至于这个问题,最直接的答案就是:list没有支持__hash__方法,那么为什么呢?

对于list的hash函数,我们可能有下面两种实现的方式:

第一种,基于id。这满足条件——“如果hash值不同,那么他们的id当然不同”。但考虑到list一般是作为容器,基于id来hash可能会导致下面两种情况:

用相同的list作为key去字典中找某个元素可能会得到不同的结果,因为是基于id hash的,所以即使他们的内容相同,字典依然将他们作为不同的元素对待。创建一个一模一样的list用字典查找永远会得到一个KeyError。

第二种,基于内容。tuple就是这样做的,但是要注意一点,tuple是不可以修改的,但list是可以修改的。当list修改之后,你就永远别想再从字典中拿回来了。见下面的代码。

>>> l = [1, 2]
>>> d = {}
>>> d[l] = 42
>>> l.append(3)
>>> d[l] # 原来的hash值是基于[1, 2]hash的,
         # 现在是基于[1, 2, 3],所以找不到
Traceback (most recent call last):
  File "<interactive input>", line 1, in ?
KeyError: [1, 2, 3]
>>> d[[1, 2]] # 基于hash [1, 2]
              # 但是遍历的时候找不到key相等的键值对
              #(因为字典里的key变成了[1, 2, 3]
Traceback (most recent call last):
  File "<interactive input>", line 1, in ?
KeyError: [1, 2]

鉴于两种实现的方式都存在一定的副作用,所以Python规定:

内置的list不能作为字典的key.

但tuple是不可变,所以tuple可以作为字典的key。

(2018年1月2日更新,上面我说tuple不可变可以作为字典的key,这句话并不是完全正确的。tuple只是相对不可改变的,如果tuple中有元素是可变对象,那么虽然tuple不可改变,那么其中元素所指向的对象是可变的,所以同样会出现上面“list不能作为字典的key”这个问题,即含有可变对象的tuple也不能作为字典的key,举个例子就很好懂了。)

In [11]: li = [1,2,] 
In [12]: d = dict() 
In [13]: t2 = (1,2,)
In [14]: t3 = (1,2,li,) 
In [15]: d[li] = 1
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-15-cc334e53316a> in <module>()
----> 1 d[li] = 1
 
TypeError: unhashable type: 'list'
 
In [16]: d[t2] = 2
 
In [17]: d[t3] = 3
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-17-c9021fe91ba8> in <module>()
----> 1 d[t3] = 3
 
TypeError: unhashable type: 'list'

4.自定义的类型作为字典的Key

用户自定义的类型就可以作为key了,默认的hash(object)是 id(object), 默认的cmp(object1, object2)是cmp(id(object1), id(object2)),同样是可以修改的对象,为什么这里就没有上面说的问题呢?

一般来说,在映射中比较常见的需求是用一个object替换掉原来的,所以id比内容更重要,就可以基于id来hash如果内容重要的话,自定义的类型可以通过覆盖__hash__函数和__cmp__函数或__eq__函数来实现

总结

值得注意的是:将对象和一个value关联起来,更好的做法是将value设置为对象的一个属性。 本文地址:http://itbyc.com/Python/21352.html
转载请注明出处。

分享是一种快乐,也是一种美德:
博客首页 | WEB开发 | 网站运营 | CMS使用教程 滇ICP备14002061号-1