Python 辞書はハッシュ テーブルの例ですか?
-
02-07-2019 - |
質問
Python の基本的なデータ構造の 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でどのように実装されているかを確認してください そして なぜそのように実装されているのか.
他のヒント
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)
.)
はい。内部的には、Z/2 上の原始多項式に基づくオープン ハッシュとして実装されます (ソース).
noskloの説明をさらに詳しく説明すると、次のようになります。
a = {}
b = ['some', 'list']
a[b] = 'some' # this won't work
a[tuple(b)] = 'some' # this will, same as a['some', 'list']
所属していません StackOverflow