@max10110

В чем разница связаного списка от хеш-таблицы?

В чем разница связаного списка от хеш-таблицы и есть ли она вообще? Или это одно и то же?
  • Вопрос задан
  • 209 просмотров
Решения вопроса 2
@Mercury13
Программист на «си с крестами» и не только
Связанный список решает такую задачу: как хранить коллекцию объектов, добавляя и удаляя туда объекты. (Простите, что я не пишу характеристики того и другого, почитайте это в умных книгах)

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

Хэш-таблица решает другую задачу: наладить отображение ключ→значение. Например, «осёл → иа, петух → кукареку», и так далее. Массив, только индексом будет не цифра, а что-то другое: x[«осёл»] = «иа». Так называемый ассоциативный массив.

Если индексом массива может быть только цифра, поступим так: превратим нашего осла в цифру — например, о+с+ё+л = 4363 (в Юникоде), и пусть 63 — это номер гнезда. В 63-м элементе массива пусть и лежит наше «осёл → иа».

Если у другого животного значением хэша будет 63 — это хэш-коллизия, и в разных реализациях решается по-разному. Я знаю такое: в гнезде лежит не просто один элемент, но связанный список. Главное, что такое слегка снижает производительность, но допустимо.
Ответ написан
@nosochek
самоучка, шакал(иногда картошечка)
хеш-таблица - массив с парами ключ\значение (в широком смысле)
связанный список - список, который в каждом из "узлов" содержит не только собственные данные, но и по одной ссылке(связке) на следующий и предыдущий
"by Google"
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@deliro
Агрессивное программирование
В чём разница макарон от сосиски в тесте и есть ли она вообще? Или это одно и то же?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы