Homework on Double Hashing - python

Question

私は現在、自分のクラスでハッシングを行っています。 リストを受け取り、二重ハッシングを使用して新しいリストを返す二重ハッシュ関数を作成する必要があります。

リストで二重ハッシュを使用する方法を理解していますが、コードの書き留めに問題があります。

hashkey = key % len(list) 
steps = q - (key % q) 
new_hashkey = steps + hashkey 
#q = double_hash_value 

これは私がクラスで学んだ二重ハッシュ関数です。私はちょうどコードでそれを実装するのに問題があります。

これは、これまでの私の試みです：

def double_hashing(keys, hashtable_size, double_hash_value): 
    hashtable_list = [None] * hashtable_size 
    for i in range(len(keys)): 
     hashkey = keys[i] % hashtable_size 
     if hashtable_list[hashkey] is None: 
      hashtable_list[hashkey] = keys[i] 
     else: 
      new_hashkey = hashkey 
      while hashtable_list[new_hashkey] is not None: 
       steps = double_hash_value - (keys[i] % double_hash_value) 
       new_hashkey = hashkey + steps 
      hashtable_list[new_hashkey] = keys[i] 
      return hashtable_list 

values = [26, 54, 94, 17, 31, 77, 44, 51] 
double = double_hashing(values, 13, 5) 
print('Double =', double) 

私は、これは右に近いですが、私はちょうど愚かな間違いか何かを作っているかなり確信しています。私は二重ハッシングの仕組みを理解していますが、上記のコードはうまくいきません。

このため、出力は次のようになります

[26, None, 54, 94, 17, 31, 44, 51, None, None, None, None, 77] 

私の出力は、次のとおり

[26, None, 54, 94, 17, 31, 44, None, None, None, None, None, 77] 

インデックス位置の値51が追加されていません。

何か助けていただければ幸いです。ありがとうございました。

Answer 1

あなたの関数は、私の知る限り2つの問題がある：

問題1は、あなたのwhileループ内で、あなたはあなたの関数は、適切なを見つけることができなかった場合ことを意味new_hashkeyの値を更新するhashkeyを使用していたということですwhileループの最初の反復で与えられた値のインデックス。new_hashkeyの値は決して変更されないので、それを見つけることはありません。また、単にstepsをnew_hashkeyに追加すると、new_hashkeyがhashtable_sizeより大きくなるリスクがあり、最終的にIndexErrorがスローされます。その値をモジュロにして修正することができますhashtable_size。 第2に、関数が早すぎて戻りました。あなたの例では、44に遭遇したとき（すなわち、初めてelseブロックに入ったとき）に戻りました。そのため、出力リストに51が追加されていませんでした。あなたの返信ステートメントはforループが終了した後でなければなりませんので、keysリストのすべての値を出力リストに確実に追加してください。男は私を助けるため

def double_hashing(keys, hashtable_size, double_hash_value): 
    hashtable_list = [None] * hashtable_size 
    for i in range(len(keys)): 
     hashkey = keys[i] % hashtable_size 
     if hashtable_list[hashkey] is None: 
      hashtable_list[hashkey] = keys[i] 
     else: 
      new_hashkey = hashkey 
      while hashtable_list[new_hashkey] is not None: 
       steps = double_hash_value - (keys[i] % double_hash_value) 
       new_hashkey = (new_hashkey + steps) % hashtable_size ## problem 1 is here 
      hashtable_list[new_hashkey] = keys[i] 
    return hashtable_list ## problem 2 is here 


values = [26, 54, 94, 17, 31, 77, 44, 51] 
print(double_hashing(values, 13, 5)) 

[26, None, 54, 94, 17, 31, 44, 51, None, None, None, None, 77]