Хеш-таблица, метод цепочек. Я правильно его понял и реализовал?

Question

Хеш-таблица, метод цепочек. Я правильно его понял и реализовал?

Celtic Hammer Мудрец (16712), закрыт 7 месяцев назад

Точно понял что смысл там в том что для мгновенного доступа к элементу массива по ключу хешируем ключ в индекс массива и ячейке с этим индексом присваиваем значение. Чтобы не искать линейным обходом. Но если хэши ключей совпадают - в ячейку кладем односвязный или двусвязный список и ищем значение в нем. Тут одинаковый хеш 4 получается у Bill, Ronald и John
Вот это моё решение походит на реализацию "метода цепочек". Вроде всё работает, вводим например Ronald, получаем Reagan

 mass = [[[None],[None]] for _ in range(10)] 
  
def to_hash(x):      
    res = [bin(ord(i)) for i in x]  
    res = ''.join([i[2:] for i in res])  
    x = int(res, 2) % len(mass)  
    return x 
 
def add_after(ind, val): 
    global mass 
    i = len(mass[ind][0]) - 1 
    mass[ind][0] += [val] 
    mass[ind][1] += [mass[ind][1][i]] 
    mass[ind][1][i] = len(mass[ind][0]) - 1 
 
 
add_after(to_hash('Bill'), 'Bill:Clinton') 
add_after(to_hash('Ronald'), 'Ronald:Reagan') 
add_after(to_hash('John'), 'John:Fitzgerald Kennedy') 
add_after(to_hash('Harry'),  'Harry:S. Truman') 
add_after(to_hash('Joe'), 'Joe:Biden') 
add_after(to_hash('Jimmy'), 'Jimmy:Carter') 
add_after(to_hash('Barack'), 'Barack:Obama') 
add_after(to_hash('Theodore'), 'Theodore:Roosevelt') 
add_after(to_hash('James'), 'James:Garfield') 
add_after(to_hash('Lyndon'), 'Lyndon:Johnson') 
 
def find_in_list(name): 
    ind = to_hash(name)     
    k = 0     
    while mass[ind][1][k] is not None:         
        #print(mass[ind][0][k + 1]) 
        result = mass[ind][0][k + 1].split(':')         
        if result[0] == name: 
            return result[1] 
        k = mass[ind][1][k] 
      
print(find_in_list(input('Name of president ').capitalize()))

Дополнен 7 месяцев назад

Похоже что k=mass[ind][1][k] нужно было написать несколькими строками выше. И не понадобилось бы k + 1

Answer 1

 mass = [[] for _ in range(11)] # простое число даёт меньше коллизий

def to_hash(x): return sum(map(ord, x)) % len(mass) # зачем переусложнять?

def add_hash(key, val):
  global mass
  mass[to_hash(key)].append((key, val, ))

def find_in_hash(key):
  for v in mass[to_hash(key)]:
    if key == v[0]: return v[1]
  return None

add_hash('Bill', 'Clinton')
add_hash('Ronald', 'Reagan')
...
print(find_in_hash(input('Name of president ').capitalize()))

Answer 2

Андрей Степанов Новичок (0) 7 месяцев назад

Да