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

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

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

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

为了实现这个功能,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的值。

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

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

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

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

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

这个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修改之后,你就永远别想再从字典中拿回来了。见下面的代码。

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

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

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

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

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

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

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

值得注意的是:将对象和一个value关联起来,更好的做法是将value设置为对象的一个属性。



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

  1. 初学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呢?请看下面的代码:

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

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

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

    我的疑问是,仿照上面的这个例子,使用list来替换变量x,应该也是可以的呀,因为按照内容进行哈希,都是对“内容”进行的计算,只要这个“内容”是固定的,就没有问题呀,道理就像上面举的例子一样。假如有一个list,比如是[1,2,3],尽管它确实是可以改变的(就像用户自定义变量一样),但在进行字典初始化的时候,它是一个确确实实的数值,既然是一个确确实实的数值,那为什么不能进行哈希计算呢?

    • 有意思的问题。

      上文中有一个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__方法。

      希望我能说明白了,如果还有问题欢迎继续讨论:)

      • 谢谢博主的耐心解答!
        我还有两个问题,想咨询一下:
        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这样设计,可行吗?

        • 最高兴的事情就是写的文章有人认真看啦 >_< 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’

  3. 我觉得,如果从设计理念的角度来看,哈希表需要完成的操作是,当我们用一个键存入数据,我们希望用“同样的”键可以取出这个数据。关键是如何定义“同样的”,对于列表这种可变的基础引用类型来说,我们很难有一个不令人困惑且让大多数人认同的定义。不管是__hash__,__eq__还是__cmp__,都是为了判断两个对象是否相同,但对于Python列表,两个列表变量名可能有相同的地址,但是在不同的时期有不同的值。也有可能两个列表的变量名有不同的地址,但是有相同值。Python的官方无法给出列表相同的定义,因此拒绝将列表作为可哈希对象。

Leave a comment

您的电子邮箱地址不会被公开。 必填项已用*标注