首頁  >  文章  >  後端開發  >  Tuple和List中,為什麼只有前者才可以當字典的key?

Tuple和List中,為什麼只有前者才可以當字典的key?

爱喝马黛茶的安东尼
爱喝马黛茶的安东尼轉載
2019-06-03 14:46:103830瀏覽

很多Python初學者常常會有這樣的疑問,為什麼Python有tuple(元組)和list(列表)兩種類型?為什麼tuple可以當字典的key,list不可以?要理解這個問題,首先要明白python的字典運作原理。

Tuple和List中,為什麼只有前者才可以當字典的key?

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):

       字典的問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: &#39;list&#39;
 
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: &#39;list&#39;

   

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

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

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

总结

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

以上是Tuple和List中,為什麼只有前者才可以當字典的key?的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:kawabangga.com。如有侵權,請聯絡admin@php.cn刪除