Моделирование хэш-таблицы

Question

Я пишу функцию, которая имитирует список вставленных ключей в порядке, указанном в хеш-таблице. Вывод должен быть представлением хэш-таблицы в виде списка (значение None используется для представления неиспользуемой позиции).

Например: list_of_values = [26, 54, 94, 17, 31, 77, 44, 51]

Я написал выше код, но получаю ошибки и проблемы, спасибо за помощь!

def hash_probe(size, key,): 
    hash_key = key % len(size) 
    if size[hash_key] != None: 
     size[hash_key] = key 
    else: 
     while size[hash_key] == None: 
      if hash_key != len(size)- 1: 
       hash_key += 1 
      else: 
       hash_key = 0 
     size[hash_key] = key 
    return size 

Answer 1

Основная проблема в вашем коде, кроме некоторых маленьких опечаток и misnames переменных является то, что вы пытаетесь поставить любое значение в уже занятых позициях. Цикл while size[hash_key] == None: будет искать занятые ячейки, поскольку он пропускает индексы, когда найдено size[hash_key] == None.

Я реструктурировать свой код, чтобы дать вам идею:

def hash_probe(table, key): 
    size = len(table) 
    hash_key = key % size 
    while table[hash_key] is not None: 
     hash_key = (hash_key + 1) % size 
    table[hash_key] = key 
    return table 

list_of_values = [26, 54, 94, 17, 31, 77, 44, 51] 
expected = [26, 51, 54, 94, 17, 31, 44, None, None, None, None, None, 77] 
actual = [None] * 13 
for v in list_of_values: 
    hash_probe(actual, v) 

print(list_of_values) 
print(expected) 
print(actual) 

Обратите внимание, что это еще не реальное решение, так как оно попадет в бесконечный цикл, когда массив получает полный.

Answer 2

Я предполагаю, что вы хотите добавить новый элемент в хэш-таблицу в заданном коде и решить конфликты с помощью linear probing.
В этом случае, есть несколько проблем с ним:

• В этой части - if size[hash_key] != None: size[hash_key] = key, вы потенциально перезапись новых значений на старые.
• Выполняя первое дополнение к списку, код перейдет в бесконечный цикл .
• Хотя это не относится к функционированию кода, имя списка size кажется немного странным.

Правильный код должен быть:

def hash_probe(keys, size): 
    hash_table = [None] * size 

    for key in keys: 
     hash_key = key % size 
     # If we find an empty position, insert it there 
     if hash_table[hash_key] is None: 
      hash_table[hash_key] = key 
     else: 
      i = (hash_key + 1) % size 

      # Find an unused position 
      count = 0 
      while count < size and hash_table[i] is not None: 
       i = (i + 1) % size 
       count += 1 

      # If it is an empty position, insert it 
      if hash_table[i] is None: 
       hash_table[i] = key 
      else: 
       print("No more space in the hash table!!") 

    return hash_table 


keys = [26, 54, 94, 17, 31, 77, 44, 51] 
hash_table = hash_probe(keys, 13) 
print(hash_table)