Хеш-таблица, метод цепочек. Я правильно его понял и реализовал?
Точно понял что смысл там в том что для мгновенного доступа к элементу массива по ключу хешируем ключ в индекс массива и ячейке с этим индексом присваиваем значение. Чтобы не искать линейным обходом. Но если хэши ключей совпадают - в ячейку кладем односвязный или двусвязный список и ищем значение в нем. Тут одинаковый хеш 4 получается у Bill, Ronald и John
Вот это моё решение походит на реализацию "метода цепочек". Вроде всё работает, вводим например Ronald, получаем Reagan
1234567891011121314151617181920212223242526272829303132333435363738
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())) Похоже что k=mass[ind][1][k] нужно было написать несколькими строками выше. И не понадобилось бы k + 1
По дате
По Рейтингу
1234567891011121314151617
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())) Да
Больше по теме