タプルとリストのうち、前者だけが辞書のキーとして使用できるのはなぜですか?

ManyPython初心者はよくこの質問をしますが、Python にはなぜタプル (タプル) とリスト (リスト) の 2 つの型があるのですか?タプルは辞書のキーとして使用できるのに、リストは使用できないのはなぜですか?この問題を理解するには、まず Python の辞書がどのように機能するかを理解する必要があります。

1. Python の辞書の仕組み

Python では、辞書は単なる「マッピング」であり、キーと値をマッピングします。 :

# 特定のキーの値を取得できます

value = d[key]

この関数を実装するには、Python が必要です。キー、このキーに対応する値を見つけます。まず、比較的単純な実装を考えてみましょう。すべてのキーと値のペアをリストに保存します。必要に応じて、リストを走査し、キーを使用してキーと値のペアのキーを照合します。それらが等しい場合は、値を取得します。ただし、データ量が多い場合、この実装は非効率になります。そのアルゴリズムの複雑さは O(n) です。ここで、n は保存されているキーと値のペアの数です。 (ハッシュ テーブルの具体的な動作原理については、私の記事を参照してください。

この目的を達成するために、Python はハッシュ (ハッシュ) メソッドを使用してそれを実装し、ディクショナリに格納されている各オブジェクトがハッシュ関数。この関数は、ハッシュ値と呼ばれる int 値を生成できます。この int 値を通じて、辞書内のオブジェクトの位置をすばやく決定できます。ただし、ハッシュの衝突が存在するため、2 つのオブジェクトが存在する可能性があります。 value は同じであるため、辞書を検索するプロセスでは、ハッシュ値と value の値を比較する必要があります。

このクエリの一般的なプロセスは次のとおりです:

def lookup(d, key):

辞書クエリのプロセスは、次の 3 つの手順に要約されます。

1. ハッシュ関数を使用して、キーをハッシュ値として計算します。

2. ハッシュ値から位置を決定します。この位置は、競合する可能性のある要素を格納する配列 (多くの場所で「バケット」と呼ばれます) です。はキーと値のペアです。理想的には、この配列には要素が 1 つだけあります。

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

この検索プロセスが適切に機能するには、ハッシュ関数が条件を満たす必要があります: 2 つのキーが異なるハッシュ値を生成する場合、2 つのキー オブジェクトは等しくありません。つまり

すべての i1、i2、if hash(i1) != hash(i2), then i1 != i2

それ以外の場合、ハッシュ値が異なっていてもオブジェクトが同じであれば、同じオブジェクトは異なるハッシュ値が生成されます。検索時に間違ったバケットを入力すると (ステップ 2)、間違ったバケットで探している値を見つけることはできません。

さらに、高い検索効率を維持するために、 2 つのキーが同じハッシュ値を生成する場合、それらは等しいことを確認する必要があります。

すべての i1、i2 について、hash(i1) == hash(i2) の場合、i1 = = i2

この目的は、各ハッシュ バケットに要素が 1 つだけあることを確認することです。なぜですか? 次のハッシュ関数を考えてください。

def hash(obj):

return 1

このハッシュ関数は、上で説明した最初の条件を満たします。2 つのキーのハッシュ値が異なる場合、2 つのキー オブジェクトは一致しません。同じ。すべてのオブジェクトが生成するハッシュ値は 1 であるため、異なるハッシュ値を生成できるキーが存在せず、不満足な状況は発生しません。ただし、これの欠点は、すべてのハッシュ値が同じであるため、すべてのオブジェクトが同じ場所に割り当てられることです。検索時、3 番目のステップでは、走査効率は O(n) になります。

ハッシュ関数では、すべての要素が各バケットに均等に分散されるようにする必要があります。理想的な状況は、各バケットに要素が 1 つだけ存在することです。位置。

上記の 2 つの原則は、1 つ目は辞書から探している要素を確実に取得できることを保証し、2 つ目はクエリの効率を保証します。

2. 辞書キーが満たさなければならない要件

上記の議論の後、理解する必要があります。 Python 辞書キーにそのような要件があるのはなぜですか: 辞書キーとして使用するには、オブジェクトがハッシュ関数 (つまり __hash__)、等価比較 (__eq__ または __cmp__) をサポートし、説明した要件を満たしている必要があります。以上の合格条件。

3.リストをキーとして使用できない理由

この質問についての最も直接的な答えは、「リストは __hash__ メソッドをサポートしていないのに、なぜですか?」です。 リストのハッシュ関数については、次の 2 つの方法で実装できます。

最初の方法は ID に基づきます。これは「ハッシュ値が違えば当然IDも違う」という条件を満たします。ただし、一般にリストがコンテナとして使用されることを考慮すると、ID に基づいてハッシュ化すると、次の 2 つの状況が発生する可能性があります。

用相同的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设置为对象的一个属性。

以上がタプルとリストのうち、前者だけが辞書のキーとして使用できるのはなぜですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。