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

Question

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

Answer 1

はい、それはハッシュ マッピングまたはハッシュ テーブルです。Tim Peters が書いた Python の 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

Python 辞書には、hash() でのテーブル検索以上の機能が必要です。残酷な実験によって私はこれを見つけました ハッシュ衝突:

>>> hash(1.1)
2040142438
>>> hash(4504.1)
2040142438

それでも、辞書を破ることはありません。

>>> d = { 1.1: 'a', 4504.1: 'b' }
>>> d[1.1]
'a'
>>> d[4504.1]
'b'

サニティーチェック：

>>> for k,v in d.items(): print(hash(k))
2040142438
2040142438

おそらく、辞書キー間の衝突を回避する hash() 以外の別の検索レベルがある可能性があります。あるいは、dict() が別のハッシュを使用している可能性があります。

(ちなみにこれはPython 2.7.10でのものです。Python 3.4.3 と 3.5.0 でも同じことが発生し、衝突が発生しました。 hash(1.1) == hash(214748749.8).)

Answer 3

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

Answer 4

noskloの説明をさらに詳しく説明すると、次のようになります。

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