私はコマンドラインパーサーを作っていて、どんな種類のハッシュアルゴリズムpython dictを使っているのだろうかと疑問に思っていましたか？Pythonの辞書マッピングではどのようなハッシュアルゴリズムが使用されますか？
私はそれをセットアップした方法で、トークン化された入力シーケンスを辞書キーと照合するパターンマッチアルゴリズムを持っています。キーの中には比較的長いものがあります（6〜7文字の長さの5または6タプル）。私は、長い辞書のキーが重要な検索の効率を大幅に低下させる点があるかどうか疑問に思っていました。
使用するハッシュは、キーとして使用されるオブジェクトによって異なります。各クラスは独自の__hash __（）メソッドを定義でき、特定のインスタンスに対して返される値は辞書に使用される値です。
Python自体は、str型とtuple型のハッシュ実装を提供します。ソースをすばやく見て、それらの正確なアルゴリズムを明らかにする必要があります。
タプルのハッシュは、その内容のハッシュに基づいています。文字列の
def hash(tuple):
mult = 1000003
x = 0x345678
for index, item in enumerate(tuple):
x = ((x^hash(item)) * mult) & (1<<32)
mult += (82520 + (len(tuple)-index)*2)
return x + 97531
、すべての文字を超える通訳も反復し、この（再び、少し簡略化）アルゴリズムと組み合わせる：
def hash(string):
x = string[0] << 7
for chr in string[1:]:
x = ((1000003 * x)^chr) & (1<<32)
return x
大きな問題アルゴリズムは、基本的にこの（やや簡素化）であります心配するには、ハッシュの衝突を避けることです。ハッシュキーが衝突すると、ディクショナリが新しいオブジェクトを格納する場所を見つけようとするときに線形検索が行われます（セキュリティ問題として認識されています）。
よろしいですか？私は何らかの理由で、Pythonがすべてのデータ型に対して汎用のバイトコードハッシュアルゴリズムを使用したと仮定しました。ハッシュキーが衝突する限り、私は鍵の数が（比較的）小さく、おそらく数千になるので、それは問題になるとは思わない。私の知覚を許してください。しかし、衝突するハッシュや線形検索はセキュリティの問題となるでしょうか？ –
@Joel Cornett：これはハッシュテーブルがバケットを使用してキーを格納し、同じハッシュコードを持つ キーが同じバケットにハッシュされるため、ハッシュテーブルで強制的にリニア検索を実行するためセキュリティ上の問題です。キーは、キーの数が多い場合、非常に非効率的であり（サービス拒否を引き起こす可能性もあります）。プログラムが同じハッシュコードにハッシュする異なるキーを持つハッシュテーブルに遭遇すると、サービス拒否攻撃が発生する可能性があります。 –
攻撃者が辞書で使用されているキーを制御できる場合、数百または数千の衝突キーを挿入できるため、挿入操作が非常に遅くなります。場合によっては、これによりマシンが応答しなくなるか、データベースが使用不能になる可能性があります.Dos攻撃 –
[Objects/dictnotes.txt]（http://hg.python.org/cpython/file/2.7/Objects/dictnotes.txt） – jfs
[この質問を見てください]（http://stackoverflow.com/questions/ 2070276/where-can-i-find-source-or-algorithm-of-pythons-hash-function）を参照してください。 [このページ]（http://effbot.org/zone/python-hash.htm）へのリンクがあり、pythonがいくつかの異なるタイプをどのようにハッシュするかを説明しています。 – srgerg