Python辞書のハッシュ検索はどのように機能しますか？

Question

どのようにPythonの辞書引きアルゴリズムが内部で動作しますか？

mydi['foo'] 

辞書に1,000,000語がある場合は、ツリー検索が実行されますか？キーストリングの長さや辞書のサイズの観点からパフォーマンスが期待できますか？たぶんすべてを辞書に詰め込むのは、500万字の文字列のツリー検索インデックスを作成するのと同じくらい良いでしょうか？

Answer 1

実際に起こっていることに近い擬似コードがあります。辞書には、キーと値のペアを含むdata属性と、割り当てられたセルの数であるsizeがあるとします。

def lookup(d, key): 
    perturb = j = hash(key) 
    while True: 
     cell = d.data[j % d.size] 
     if cell.key is EMPTY: 
      raise IndexError 
     if cell.key is not DELETED and (cell.key is key or cell.key == key): 
      return cell.value 
     j = (5 * j) + 1 + perturb 
     perturb >>= PERTURB 

perturb値は、ハッシュ衝突を解決するときに、ハッシュコードのすべてのビットが最終的に使用されることを保証するが、それは0に低下した後(5*j)+1は、最終的に、テーブル内のすべてのセルをタップします。

sizeは、実際に使用されているセルの数より常にずっと多く、ハッシュはキーが存在しないときに空のセルにヒットすることが保証されています。検索を終了すべきではないが、現在使用されていないセルを示すためのキーのための削除された値もある。

文字列をハッシュすると文字列のすべての文字が表示されますが、文字列には計算されたハッシュを格納するためのフィールドもあります。だから、毎回異なる文字列を使用して検索を行う場合、文字列の長さには影響がありますが、固定されたキーセットを持ち、同じ文字列を再利用すると、ハッシュは最初に使用された後には再計算されません。 Pythonはほとんどの名前検索で辞書を使用し、各変数や属性名の単一のコピーが内部的に格納されるため、Pythonはこの利点を得ます。したがって、属性x.yにアクセスするたびに辞書検索が行われますが、ハッシュ関数は呼び出されません。

Answer 2

あなたのタイトルで述べたように、dictsはハッシュテーブルです。ツリー検索は使用されません。キーを検索することは、辞書のサイズにかかわらず、ほぼ一定の時間の操作です。

あなたは役に立つこの質問への答えを見つけるかもしれない：How are Python's Built In Dictionaries Implemented

Answer 3

ハッシュ検索は木を使用しないでください。彼らはハッシュテーブルを使用し、一定の時間の検索を行います。彼らは木のように（平均して2倍もあると思うが）より多くのスペースを取るだろうが、ルックアップと挿入時間は勝つ。 oversimplifyする

、アドレスの数をあなたが持っているあなたの鍵のMD5、およびMODを取り、あなたがキーを取得するために保存したり、見ところです。あなたは良いハッシュが回避されます重要な衝突を、持っていないので、それはセットがどのように大きな問題ではありません、それはいつものように長い時間の同じ量がかかります。ここで

Answer 4

は良い説明です：上記のリンクからhttp://wiki.python.org/moin/DictionaryKeys

擬似コード：

def lookup(d, key): 
    '''dictionary lookup is done in three steps: 
     1. A hash value of the key is computed using a hash function. 

     2. The hash value addresses a location in d.data which is 
      supposed to be an array of "buckets" or "collision lists" 
      which contain the (key,value) pairs. 

     3. The collision list addressed by the hash value is searched 
      sequentially until a pair is found with pair[0] == key. The 
      return value of the lookup is then pair[1]. 
    ''' 
    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 

Answer 5

回答1：いいえ、木探索：内部の作業は、このvideo

回答2に説明されていますあなたが辞書に100万のレコードを持っているなら、行なわれません。

回答3：キーの衝突の可能性があるため、キーの文字列の長さではなく、辞書のサイズの観点からパフォーマンスが期待されます。

回答4：配列（連続するメモリ位置）として辞書を検討するが、使用されていないアレイ内のブロックがあるかもしれません。したがって、辞書は木に比べて多くのメモリ空間を無駄にする傾向があります。しかし、実行時のパフォーマンスを向上させるためには、辞書よりも木が良いかもしれません。キーの衝突により、パフォーマンスが低下することがあります。 Consistent Hashingについて読んでください。