python - Python辞書はハッシュテーブルの例ですか?

Question

Python の基本的なデータ構造の 1 つはディクショナリです。ディクショナリを使用すると、任意の型の「値」を検索するための「キー」を記録できます。これは内部的にハッシュ テーブルとして実装されていますか? そうでない場合、それは何ですか?

Answer 1

はい、ハッシュ マッピングまたはハッシュ テーブルです。ここで、Tim Peters によって書かれた python の dict 実装の説明を読むことができます。

そのため、リストのように「ハッシュできない」ものを dict キーとして使用することはできません。

>>> a = {}
>>> b = ['some', 'list']
>>> hash(b)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable
>>> a[b] = 'some'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable

ハッシュ テーブルの詳細を読んだり、pythonでの実装方法やそのように実装されている理由を確認したりできます。

Answer 2

はい。内部的には、Z/2 上の原始多項式 ( source )に基づくオープン ハッシュとして実装されます。

Answer 3

noskloの説明を拡張するには：

a = {}
b = ['some', 'list']
a[b] = 'some' # this won't work
a[tuple(b)] = 'some' # this will, same as a['some', 'list']