雙重哈希函數 - 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) 

我相當肯定這是緊挨是正確的，但我只是做一個愚蠢的錯誤或東西。我理解double hash是如何工作的，但上面的代碼不起作用。

該輸出應爲：

[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

你的函數有兩個問題，據我可以告訴：

問題1是，在你的while循環，你正在使用hashkey更新，這意味着的new_hashkey值，如果你的函數未能找到一個合適的在while循環的第一次迭代中給定值的索引，它永遠不會找到它，因爲new_hashkey的值永遠不會改變。此外，通過簡單地將steps加到new_hashkey上，你可能會面臨new_hashkey大於hashtable_size的風險，最終會拋出IndexError。您可以通過將該值取模爲hashtable_size來解決該問題。其次，你的功能迴歸得太早。在您的示例中，它在遇到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]