Tuple과 List 중 왜 전자만 딕셔너리의 키로 사용할 수 있나요?

많은 Python초보자들이 종종 이런 질문을 합니다. 왜 Python에는 튜플(tuple)과 리스트(list)의 두 가지 유형이 있습니까? 튜플은 딕셔너리의 키로 사용할 수 있는데 리스트는 왜 사용할 수 없나요? 이 문제를 이해하려면 먼저 Python의 사전이 어떻게 작동하는지 이해해야 합니다.

1. Python의 사전 작동 방식

Python에서 사전은 키를 값으로 매핑하는 하나씩 "매핑"입니다.

# 특정 키 값을 얻을 수 있습니다

value = d[ key]

이 함수를 구현하려면 Python이 키가 주어지면 이 키에 해당하는 값을 찾을 수 있어야 합니다. 먼저 비교적 간단한 구현을 고려해 보겠습니다. 필요할 때마다 목록을 탐색하고 키-값 쌍의 키를 일치시키는 경우 값을 가져옵니다. 그러나 이 구현은 데이터 양이 많을 때 비효율적입니다. 알고리즘 복잡도는 O(n)입니다. 여기서 n은 저장된 키-값 쌍의 수입니다. (해시 테이블의 구체적인 작동 원리는 내 기사를 참조하세요.

이를 위해 Python은 해시 메서드를 사용하여 구현하며, 사전에 저장된 모든 객체는 해시 함수를 구현해야 합니다. 이 함수 이 int 값을 통해 사전에서 객체의 위치를 ​​빠르게 확인할 수 있습니다. 그러나 Hash 충돌이 있기 때문에 Hash 값이 다음과 같은 객체가 두 개 있을 수 있습니다. . 동일하므로 사전을 검색하는 과정에서 해시 값과 해당 값의 값을 비교해야 합니다.

이 쿼리의 일반적인 프로세스는 다음과 같습니다.

def lookup(d, key):

사전 쿼리 프로세스는 다음과 같이 요약됩니다. 3단계:

1. 해시 함수를 통해 키를 해시 값으로 계산합니다. 2. 해시 값을 통해 위치를 결정합니다. 이 위치는

요소를 저장하는 배열입니다. 충돌(여러 곳에서 "버킷"이라고 함, 각 요소는 키-값 쌍입니다. 이상적으로는 이 배열에 요소가 하나만 있습니다.

3. 배열을 순회하여 대상 키를 찾고 해당 값을 반환합니다.

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

이 검색 프로세스가 제대로 작동하려면 해시 함수가 조건을 충족해야 합니다. 두 키가 서로 다른 해시 값을 생성하는 경우 두 키 개체가 동일하지 않습니다. 즉, 모든 i1, i2에 대해

if hash(i1) != hash(i2), then i1 != i2

그렇지 않으면 해시 값은 다르지만 객체는 동일하므로 동일한 객체가 다른 해시 값을 생성하고 잘못된 버킷에 들어갑니다. 검색 시(2단계) 잘못된 버킷에서 원하는 값을 찾을 수 없습니다.

또한 사전에서 높은 검색 효율성을 유지하려면 두 키가 동일한 해시 값을 생성할 때 두 키가 동일한지 확인해야 합니다.

모든 i1, i2에 대해 hash(i1) == hash(i2)이면 i1 == i2입니다.

이 목적은 각 해시 버킷에 요소가 하나만 있다는 것을 만족시키는 것입니다. . 왜 이것을 고려해야 할까요?

def hash(obj):

Return 1

이 해시 함수는 위에서 설명한 첫 번째 조건을 충족합니다. 다르면 두 키 객체가 동일하지 않습니다. 모든 객체에서 생성되는 해시 값이 1이기 때문에 서로 다른 해시 값을 생성할 수 있는 키가 없으며 만족스럽지 못한 상황이 없습니다. 하지만 이것의 단점은 모든 해시 값이 동일하기 때문에 모든 객체가 동일한 위치에 할당된다는 것입니다. 검색 시 세 번째 단계에서는 순회 효율성이 O(n)이 됩니다. 해시 함수는 모든 요소가 각 버킷에 고르게 분산되도록 해야 합니다. 이상적인 상황은 각 위치 요소에 하나의 요소만 있다는 것입니다.

위의 두 가지 원칙 중 첫 번째는 사전에서 찾고 있는 요소를 얻을 수 있다는 것을 보장하고, 두 번째는 쿼리 효율성을 보장합니다.

2. 사전 키가 충족해야 하는 요구 사항

위의 논의 후에 Python이 사전 키에 대해 그러한 요구 사항을 갖는 이유를 이해해야 합니다.
사전 키로 사용하려면 객체가 다음과 같아야 합니다. 해시 함수(예: __hash__), 동등 비교(__eq__ 또는 __cmp__)를 지원하고 위에서 설명한 조건을 충족합니다.

3. List를 키로 사용할 수 없는 이유는 무엇입니까? 이 질문에 대한 가장 직접적인 대답은 list가 __hash__ 메서드를 지원하지 않는다는 것입니다. 그런데 그 이유는 무엇입니까?

리스트의 해시 함수를 구현하는 방법은 다음 두 가지가 있을 수 있습니다.

첫 번째는 ID를 기반으로 합니다. 이는 "해시 값이 다르면 당연히 ID도 다르다"라는 조건을 만족한다. 그러나 목록이 일반적으로 컨테이너로 사용된다는 점을 고려하면 ID 기반 해싱은 다음 두 가지 상황으로 이어질 수 있습니다.

用相同的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 중 왜 전자만 딕셔너리의 키로 사용할 수 있나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!