Hausaufgaben auf Double Hashing - Python

Question

Ich mache gerade Hashing in meiner Klasse. Ich muss eine doppelte Hashfunktion erstellen, die eine Liste annimmt und doppeltes Hashing verwendet und eine neue Liste zurückgibt.

Ich verstehe, wie eine Liste doppelt Hashing verwendet, aber ich habe Schwierigkeiten, den Code dafür aufzuschreiben.

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

Dies ist die doppelte Hashing-Funktion, die ich in der Klasse gelernt habe. Ich habe nur Schwierigkeiten, es in den Code zu implementieren.

Dies ist mein Versuch so weit:

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) 

Ich bin ziemlich sicher, dass dies zu sein, direkt in der Nähe ist, aber ich bin nur einen dummen Fehler oder etwas zu machen. Ich verstehe, wie Double Hashing funktioniert, aber dieser Code funktioniert nicht.

sollte die Ausgabe für dieses:

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

aber meine Ausgabe ist:

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

Der Wert 51 in Indexposition nicht hinzugefügt wird.

Jede Hilfe wird geschätzt. Vielen Dank.

Answer 1

Ihre Funktion hat zwei Probleme so weit wie ich kann sagen:

Problem 1 ist, dass in Ihrer while Schleife, Sie hashkey wurden mit dem Wert von new_hashkey zu aktualisieren, was bedeutete, dass, wenn Ihre Funktion nicht gelungen, einen geeigneten zu finden Index für einen gegebenen Wert in der ersten Iteration der while-Schleife, würde es nie finden, da der Wert von new_hashkey würde nie ändern. Auch wenn Sie einfach steps zu new_hashkey hinzufügen, riskieren Sie, dass eine new_hashkey größer als Ihre hashtable_size ist, die schließlich eine IndexError werfen wird. Sie können das beheben, indem Sie den Wert modulo hashtable_size nehmen. Zweitens kehrte Ihre Funktion zu früh zurück. In Ihrem Beispiel wurde es zurückgegeben, nachdem es auf 44 gestoßen ist (d. H. Das erste Mal, als es den Block else betrat). Aus diesem Grund fügten Sie Ihrer Ausgabeliste 51 nicht hinzu. Ihre Return-Anweisung sollte wirklich sein, nachdem die for-Schleife abgeschlossen ist, so dass Sie sicher sind, alle Werte in der keys-Liste zu Ihrer Ausgabeliste hinzuzufügen.

Siehe den aktualisierten Code (geänderten Zeilen sind kommentiert):

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]