Python 为什么list不能作为字典的key？

Posted on 2017年1月12日 by laixintao 14 Comments

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

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

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

# 对一个特定的key可以得到一个value
value = d[key]

1 2	# 对一个特定的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

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

1	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

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

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

def hash(obj):
    return 1

1 2	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]

>>> 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'

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设置为对象的一个属性。

“Python 为什么list不能作为字典的key？”已经有14条评论

初学python，你说的没看太懂，不明白你这里说的id是指什么，就是类似一个对象的引用，指针吗？看廖雪峰的教程：http://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/00143167793538255adf33371774853a0ef943280573f4d000
最后有这么一句话：“tuple虽然是不变对象，但试试把(1, 2, 3)和(1, [2, 3])放入dict或set中，并解释结果。”我测试了一下：（1，2，3）是可以作为dict的key的，而（1，[2,3]）是不可以作为dict的key的，这是不是就是说明python中dict，set这些数据结构的key 就是根据内容进行hash的呢？

你好，这里的id就是指对象的id，是一串数字。在python里运行 id(object)就可以查看对象的id。

你提到的这个实验，我是这么理解的。（1,2,3)是不可变的对象，所以可以进行hash，不会违背本文中提到的两种原则。但(1,[2,3])包含可变的对象，就类似本文的这种情况了，无论是基于内容hash还是基于id hash都不太合适。所以Python就禁止使用(1,[2,3])作为key。

但是这些不足以说明这是基于内容hash的，因为Python对tuple基于id hash也是可以的。怎么证明对tuple是基于内容hash呢？请看下面的代码：

In [1]: a = (1,2,3)

In [2]: id(a)
Out[2]: 139811389379440

In [3]: b=(1,2,3)

In [4]: id(b)
Out[4]: 139811389416944

In [5]: d = {}

In [6]: d[a] = 'hello'

In [7]: d
Out[7]: {(1, 2, 3): 'hello'}

In [8]: d[b] = 'world'

In [9]: d
Out[9]: {(1, 2, 3): 'world'}

In [1]: a = (1,2,3)

In [2]: id(a)

Out[2]: 139811389379440

In [3]: b=(1,2,3)

In [4]: id(b)

Out[4]: 139811389416944

In [5]: d = {}

In [6]: d[a] = 'hello'

In [7]: d

Out[7]: {(1, 2, 3): 'hello'}

In [8]: d[b] = 'world'

In [9]: d

Out[9]: {(1, 2, 3): 'world'}

在这段代码中，a和b的id明显是不一样的，但是字典的值却被替换了（也就是说，a和b产生了相同的hash value），这样才能证明，tuple是基于内容hash的。欢迎继续讨论：）

Reply

clearbug on 2017年2月21日 at 11:38 said:

Thanks！稍微有点理解了。。
Reply

Charles on 2017年6月7日 at 21:39 said:

我想问一下，为什么用户自定义变量是可以进行哈希的（你文章里最后的解释我没看明白）？
我是这么想的，对内容进行哈希计算，在这一点上，list和用户变量没有任何差别。因为list虽然是可变的，但就像用户变量一样，在某一个时刻它是固定不变的。例如：

x=2 d={} d[x]='a' x=3 print(d.get(x,-1)) print(d.get(2,-1))

1
2
3
4
5
6

x=2
d={}
d[x]='a'
x=3
print(d.get(x,-1))
print(d.get(2,-1))

在字典d中，对数字2进行哈希，然后将对象字符a存入，其key-value是2-‘a’。
在第一个打印结果里，返回是-1。因为x的值变为了3，对3进行哈希计算，得到的哈希值在字典中查找不到对应结果；在第二条打印结果里，返回值是字符a，不再赘述。

我的疑问是，仿照上面的这个例子，使用list来替换变量x，应该也是可以的呀，因为按照内容进行哈希，都是对“内容”进行的计算，只要这个“内容”是固定的，就没有问题呀，道理就像上面举的例子一样。假如有一个list，比如是[1,2,3]，尽管它确实是可以改变的（就像用户自定义变量一样），但在进行字典初始化的时候，它是一个确确实实的数值，既然是一个确确实实的数值，那为什么不能进行哈希计算呢？
- Reply
  
  laixintao on 2017年6月8日 at 22:45 said:
  
  有意思的问题。
  
  上文中有一个lookup函数表示了字典根据key查找一个值的过程，先通过hash值找到桶，然后从桶里面找到和key相同的那个key-value键值对。（为什么这样？因为如果两个对象产生了相同的hash值，那么这两个对象也都是可以存进字典并且不会覆盖的，就是因为分了桶。在字典中，相同hash值的放在同一个桶，找的时候先找出来目标桶，再根据对象的相等来找目标key-value键值对，如果你看明白上面的lookup函数，应该就会理解括号的内容了）。
  
  然后你再看上文list不用以内容来hash那段，如果以内容[1,2]来hash，当然可以存进字典（假设是l=[1,2]; d[l]=’a’），但是注意，一旦这个list变了(l.append(3))，你就再也拿不到这个键值对了。d[[1,2]]和d[l]的hash值相同，但是step3失败，因为list不再相等。d[[1,2,3]]会在第二步失败，因为hash值就不一样。
  
  —
  为什么自定义的对象就可以？
  这里的主要区别是，我们可以实现对象的__eq__方法，__hash__方法，比如说，让[1,2]==[1,2,3]，这样第三步就不会失败；或者让hash([1,2])和hash([1,2,3])的hash值相等，这样第一步不会失败。
  
  而对于list，我们不会改变list的__hash__方法和__eq__方法，因为这样做会影响所有的list。区别就在此：是否可以自定义__hash__方法和__eq__方法。
  
  希望我能说明白了，如果还有问题欢迎继续讨论：）
  - Reply
    
    Charles on 2017年6月20日 at 09:25 said:
    
    谢谢博主的耐心解答！
    我还有两个问题，想咨询一下：
    1，python对各种数据类型是怎样做的hash运算呢？你在文章中有写“默认的hash(object)是 id(object),”，那么，除了默认对数据类型的id做hash，有没有其他特殊的类型是对内容做hash的呢？
    2，你在解释“为什么可变对象例如list不能hash”的时候，重点是这一个理由“假设是l=[1,2]; d[l]=’a’），但是注意，一旦这个list变了(l.append(3))，你就再也拿不到这个键值对了。”这一点我是看明白了，但是还有个疑问（原谅我喜欢钻牛角尖!^_^），就是，拿不到就拿不到了，本来就不该拿到的，因为第一次是对key [1,2]做的hash，而第二次是对[1,2,3]做的hash，两次的key不同，自然hash值不同，所以是取不到对于的value值的。要想取回，可以两种选择，一是把[1,2,3]改回到原来的[1,2]；一是新建一个list赋值为[1,2]，这样的话，key相同了，计算出hash值，查找到桶，再从桶中取出value。如果python这样设计，可行吗？
    - Reply
      
      laixintao on 2017年6月20日 at 09:57 said:
      
      最高兴的事情就是写的文章有人认真看啦 >_< 1. 对于自定义的类型，hash的方法要根据需求来定。比如一个对象（Person）我想针对name和age（假定我们的需求是根据name和age就可以确定一个人）进行hash，那么让hash方法是name+age。一般来说推荐使用内容做hash，Python的内置类型tuple应该就是基于内容hash的，我实验得出的结论，并不一定准确。参考下面代码。
      In [1]: d = {}
      In [2]: t1 = (1,2)
      In [3]: d[t1] = ‘hello’
      In [4]: t2 = (1,2)
      In [5]: d[t2]
      Out[5]: ‘hello’
      
      2. 第一种做法，[1,2,3]改回去，是可行的。第二种是错误的，因为新建一个list还是会有原来的问题：基于[1,2]hash但是要等于[1,2,3]，这是不可能的，除了改回原来的list没有其他的办法。虽然第一种方法可行，但是基本上不会有人把对象存入dict，然后要用的时候还必须将原对象改回去再取值。因为所有后面对list进行很多操作，然后肯定记不住原来hash时候的list到底是哪个对象（对象经过了很多赋值的话）、list hash的时候具体值是什么。所以Python就直接把list作为key给禁止了。
      
      In [6]: d[[1,2]] = ‘world’
      TypeError: unhashable type: ‘list’
Reply

Vicnn on 2018年1月31日 at 23:58 said:

写得很清楚，感谢！
- Reply
  
  laixintao on 2018年2月1日 at 09:44 said:
  
  ^ ^
Pingback: Python 为什么list不能作为字典的key？ - 算法网
Reply

23f067181a97c963715b3193cba25bde on 2021年11月21日 at 07:33 said:

我觉得，如果从设计理念的角度来看，哈希表需要完成的操作是，当我们用一个键存入数据，我们希望用“同样的”键可以取出这个数据。关键是如何定义“同样的”，对于列表这种可变的基础引用类型来说，我们很难有一个不令人困惑且让大多数人认同的定义。不管是__hash__,__eq__还是__cmp__，都是为了判断两个对象是否相同，但对于Python列表，两个列表变量名可能有相同的地址，但是在不同的时期有不同的值。也有可能两个列表的变量名有不同的地址，但是有相同值。Python的官方无法给出列表相同的定义，因此拒绝将列表作为可哈希对象。
- Reply
  
  laixintao on 2021年11月22日 at 10:46 said:
  
  是的。
Pingback: Python 为什么list不能作为字典的key？ - 算法网
Pingback: Python 为什么list不能作为字典的key？ - 算法网