背景简单来说，当我们尝试在Python中使用列表作为键值时，会提示“unhashable（不可散列）”的错误。在[1]中：la=[1,2]在[2]中：d={}在[3]中：d[la]=3--------------------------------------------------------------------TypeErrorTraceback(mostrecentcalllast)in---->1d[la]=3TypeError:unhashabletype:'list'moreextensive那说过了，对于Python中所有内置的可变类型（列表、字典、集合），我们不能将它们作为字典的键和值。要回答原因，我们将从列表和字典的一般工作方式开始，然后探讨它们为什么不工作。可变类型和不可变类型我们首先需要了解可变类型和不可变类型的概念。Python中的可变类型和不可变类型其实对应于其他语言中的“值类型”和“引用类型”。Python中的数据类型分为可变的和不可变的。不可变类型有数字（int、float）、字符串（str）、布尔（bool）、元组（tuple），可变类型有列表（list）、字典（dict）、集合（set）。当然，也有用户自定义的类。Python中的不可变类型在语义上和实现上都是不可变的。比如我们给一个整型对象a赋值或者修改值的时候，会发现a的id变了，因为number是一个不可变类型。当我们修改变量a的值时，原来修改的内存空间中不会存入88888这个值。而是销毁原来内存中的88888，然后开辟新的内存空间写入9999赋值给对象a。In[40]:a=88888In[41]:id(a)Out[41]:140691892091152In[42]:a=9999In[43]:id(a)Out[43]:140691892092048其修改将在原始内存空间。因为listla对象是一个可变对象，也就是其他语言中的引用对象。在存放对象la的内存空间中，并没有直接存放la的内容，而是包含一个指向实际存放la内容的地址的指针。在[44]中：la=[1,2]在[45]中：id(la)Out[45]：140691892029824在[46]中：la[1]=3在[47]中：id(la)Out[47]：140691892029824In[48]:la.append(4)In[49]:id(la)Out[49]:140691892029824变量类型有一个明显的特点，如果直接传给其他对象，不管是new变量，在函数内部或作为另一个容器或类的成员。传递的对象可以修改其值（即其内容）并影响原始可变对象。也就是说，可变对象直接传递给其他对象后，这些对象会共享同一个值，它们的修改会相互影响。以下示例演示了这一点。在[72]中：la=[1,2]在[73]中：lb=laIn[74]：lc=[4,5,6,la]在[75]中：defchange_la(la):...:la.append(999)...:In[76]:change_la(la)In[77]:laOut[77]:[1,2,999]In[78]:lbOut[78]:[1,2,999]In[79]:lcOut[79]:[4,5,6,[1,2,999]]字典是如何工作的我们将简要地谈谈哈希函数和字典是如何工作的。哈希函数的含义哈希函数的数学定义是将任意长度的输入数据通过哈希算法转化为固定长度的输出，输出即为哈希值。如果同一个哈希函数输出两个不同的哈希值，那么它们的输入也会不同。但是两个不同的输入可能会产生相同的输出，这称为散列冲突。具体到软件工程中，哈希函数常被用作判断两个对象是否相同的方法，对一个对象中的一些重要属性（值、内存地址等）进行哈希运算，得到一个固定长度的值，这个值可以看作是一种类似于物体的“指纹”和“摘要”的身份信息。因为哈希值的数据结构和长度是固定的，所以比较容易。如果两个对象的哈希值相同，我们可以暂时认为它们是同一个对象，但是由于哈希冲突的存在，我们需要进一步判断两个对象的重要属性是否相同。字典的作用和实现字典（dict）是哈希表和哈希表。它是一种利用散列函数特性的数据结构，可以实现最快时间复杂度为O(1)的查询操作。一种常见的实现方式是，哈希表会先开辟一个桶数组，对插入的键值对的键进行哈希值运算，然后再进行进一步的运算，比如取哈希值和长度bucketarray剩下的操作最终决定将键值对放入哪个bucket。桶可以是链表或数组等容器。由于散列冲突，桶通常可以容纳多个键值对。在进行查询操作时，我们对插入时的key进行相同的计算，可以立即在多个桶中找到存放目标数据的桶的下标（这也是哈希表高效的主要原因），以及然后在桶中查找键对应的值。我们把查询过程细化一下，参考Python官方wiki翻译一下。字典查找过程可以用下面的查找函数来展示。当然，实际上字典的设计要比这复杂的多，我们只需要了解这里的概念即可。deflookup(d,key):'''字典的查找分三步完成1.使用哈希函数计算key的哈希值。2.通过散列到字典桶数组（d.data）中的一个位置，我们应该能够得到一个称为桶或冲突列表的数组。它包含键值对((key,value))。3.遍历名为bucket或冲突列表的数组，如果bucket中存在键值等于输入参数键（key）的键值对，则返回值（value）作为返回值。'''h=hash(key)#步骤1cl=d.data[h]#步骤2forpairincl:#步骤3ifkey==pair[0]:returnpair[1]else:raiseKeyError,“找不到密钥%s。"%key可以注意到，查询一个key，关键点就是获取它的hash值，通过hash值在bucket数组中寻址，然后比较是否有与传入的key值相同的keybucket中的key值对，最后返回键值对的值，再回到Python本身的讨论，参考Python官方的说法：要用作字典键，对象必须支持hash函数（例如通过hash__），等式比较（例如通过__eq或__cmp__），并且必须满足上述正确性条件。要用作字典键的数据类型，对象必须同时支持散列（例如通过__hash__方法）和等式确定（例如，通过__eq__或__cmp__方法）这两个操作。在[80]中：hash(la)------------------------------------------------------------------------TypeError回溯（最近调用last）在---->1hash(la)TypeError:unhashabletype:'list'至于文章的标题，我们其实可以在这里回答。即列表类型没有实现__hash__方法，所以不能取hash值，从而不能作为字典键。但是如果我们再深入一点，我们想讨论一下为什么没有实现__hash__方法。允许列表取hash值带来的问题对于字典来说，如果我们再抽象一下它的功能，可以描述为。向字典中插入一个键值对后，我们希望通过“相同”的键将值取出来。如何定义两个键（或对象）同样是哈希函数的事情。问题由此而来，因为列表和哈希函数的特性，我们很难对列表的“相同性”做出一个直观的、不混淆的定义。你可能会想说，如果两个列表的内容，即元素的长度和顺序相同，就说明这两个列表是相同的。这个定义不是很容易给出吗？其实list确实支持判断相等的操作（实现了__eq__方法），但是作为hash表的key值还是有很多问题。直截了当，考虑设计这样一个列表，它支持和原来列表一样的判断相等操作，它的hash方法也是计算内容的。正如我们想象的那样，两个具有相同内容的列表将具有相同的哈希值。类MyList(object):def__init__(self,value):self.value=valuedef__repr__(self):返回str(self.value)def__str__(self):返回str(self.value)def__eq__(self,other):返回self.value==other.valuedef__hash__(self):#将列表转换为字符串，然后将字符串的每个字符转换为数字#例如：[1,2]->"[1,2]"->914944325093hashValue=""forcinstr(self.value):hashValue+=str(ord(c))returnint(hashValue)用法如下In[47]:ml1=mylist.MyList([1,2])In[48]:ml1Out[48]:[1,2]In[49]:d1={}In[50]:d1[ml1]=999In[51]:print(d1){[1,2]:999}In[52]:ml2=mylist.MyList([1,2])In[53]:d1[ml2]Out[53]:999看起来这很符合我们的想象，但是如果我们修改ml1呢？在[54]中：ml1.value.append(3)在[55]中：ml1Out[55]:[1,2,3]在[56]中：ml2Out[56]:[1,2]在[57]中：print(d1){[1,2,3]:999}在[58]:d1[ml1]-----------------------------------------------------------------------KeyError回溯（最近调用last）in---->1d1[ml1]KeyError:[1,2,3]In[59]:d1[ml2]----------------------------------------------------------------------KeyErrorTraceback（最近调用最后）in---->1d1[ml2]KeyError:[1,2]我们可以发现，如果我们修改ml1，字典d1中的键值也会发生变化。这是因为列表是一个可变对象，多个引用使用一个修改影响所有引用。如果此时我们再想通过ml1取值，就会提示错误。原因是修改后的ml1内容变了，hash值也变了。字典无法传递新的哈希值。定位到原来存放键值对的位置。另外，如果我们试图通过内容和哈希值与变化前的ml1相同的ml2获取d1的值，也是错误的。因为字典查询不仅需要计算hash找到bucket的下标，还要检查querykey和bucket中的key是否真的相等，避免hash碰撞。此时字典中的key被ml1修改了，但是相应的发生了变化，所以ml2的值不等于bucket中的key值，取不到值。我们也可以考虑其他的hash方法，比如通过对象的id，也就是内存地址来计算hash，但是这样会有比较明显的问题。查询字典的key只能根据最初插入的对象的引用。具有相同值的对象和字面量将永远找不到想要的结果，因为它们的内存地址不同。虽然实际上对用户自定义类的对象内存地址进行散列是默认操作，但是在面向对象的思想中更容易使用。对于内置列表的基本类型，使用这种方案是违反直觉的。在[98]中：ml1=mylist.MyList([1,2])在[99]中：ml2=mylist.MyList([1,2])在[100]中：ml3=ml1在[101]中：print(id(ml1),id(ml2),id(ml3))140172863009408140172873557376140172863009408In[102]:ml1==ml2==ml3Out[102]:TrueIn[103]:d1={}In[104]:d1[ml1]=999In[105]:print(d1){[1,2]:999}In[106]:d1[ml1]Out[106]:999In[107]:d1[ml3]Out[107]:999In[108]:d1[ml2]--------------------------------------------------------------------------KeyErrorTraceback(最近一次调用last)in>---->1d1[ml2]KeyError:[1,2]In[109]:d1[mylist.MyList([1,2])]--------------------------------------------------------------------KeyErrorTraceback(最近一次调用last)in---->1d1[mylist.MyList([1,2])]KeyError:[1,2]原因是用于索引的哈希值是在某个时间根据对象的某个属性生成的，是静态的。找到对应的bucket后，从bucket中找到与传入key相匹配的key-valuepair，就是根据对象本身。对于不可变类型，它们在桶中的哈希值和键值对是不变的。对于变量类型，它们的变化会导致桶中的键值对动态变化，但哈希索引仍然是静态的，这就产生了矛盾。该解决方案使用元组而不是列表。元组是不可变类型，其哈希函数是根据内容本身以直观的方式生成的。参考[1]WhyListsCan'tBeDictionaryKeys[2]为什么我不能在python中使用列表作为dictkey？
