[转载]为什么字典中的Key不能是列表¶
1 Python的字典是如何工作的¶
在Python中，字典就是一个个的映射，为了实现这个功能，Python必须能够做到，给出一个Key，找到哪一个Value与这个Key对应。如果我们将Key-value键值对存放到一个List中,每当需要的时候，就去遍历这个List，用Key和键值对对应的Key去进行对比。但是这样实现方法，如果数据量很大的时候就变得很低效。他的算法复杂度是O(n),n是存放键值对的数量。
为此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,查找的时候就会进错桶，在错误的桶里永远也找不到你要找的Value.
另外，要让字典报纸高效率查找，还要保证：当两个Key产生相同的Hash Value，那么他们是相等的。
for all i1,i2,if hash(i1)==hash(i2),then i1==i2
这样做的目的是，尽量满足每个Hash 桶只有一个元素。为什么要这样做？考虑下面这个Hash函数：
这个函数是满足上面我们谈的第一个条件的：如果两个key的Hash Value 不同，那么两个Key对象不相同。因为所有的对象产生的Hash Value 都是1，所以不存在能产生不同Hash Value的Key,也就不存在不满足的情况。但是这样做的坏处是，因为所有的Hash Value都相同，就相当于把所有的Hash对象都分到了同一个地方。查找进行到第三步的时候，遍历的效率就变成了O(n).
Hash 函数应该保证所有的元素平均的分配到每一个桶中，理想的情况是，每一个位置只有一个元素。
以上两个原则，第一个保证了你能从字典中拿到要找的元素，第二个原则保证了你查询时的效率。
2字典Key要满足的要求¶
经过上面的讨论，我们应该明白Python为什么对字典Key有这样的要求了“
要作为字典的Key,对象必须要支持Hash 函数，(即__hash __),相等比较函数(__eq__或__cmp__)，并且满足上面我们讨论的条件
3 List为什么不能作为Key¶
最直接的答案就是：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。
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'
用户自定义的类型就可以作为key了，默认的hash(object)是 id(object), 默认的cmp(object1, object2)是``cmp(id(object1), id(object2))，同样是可以修改的对象，为什么这里就没有上面说的问题呢？
- 一般来说，在映射中比较常见的需求是用一个object替换掉原来的，所以id比内容更重要，就可以基于id来hash
- 如果内容重要的话，自定义的类型可以通过覆盖__hash__函数和__cmp__函数或__eq__函数来实现
值得注意的是：将对象和一个value关联起来，更好的做法是将value设置为对象的一个属性。
如果以内容[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__方法。
[4].https://www.kawabangga.com/posts/1821