双重哈希函数 - 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]