Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

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

Celtic Hammer Мудрец (16681), закрыт 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
Лучший ответ
Андрей Высший разум (463546) 7 месяцев назад
 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()))
Celtic HammerМудрец (16681) 7 месяцев назад
Ну я только сегодня задумался как все это реализовать. И то что сделал это почти с ходу - уже хорошо
Андрей Высший разум (463546) Celtic Hammer, Если первая попытка, то да - нормально.
Остальные ответы
Похожие вопросы