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

Question

[Макс]

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

Comments

[Wexter]

встречный вопрос, что такое связный список и что такое хеш таблица?

Answer 1

[Mercury13]

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

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

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

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

Если у другого животного значением хэша будет 63 — это хэш-коллизия, и в разных реализациях решается по-разному. Я знаю такое: в гнезде лежит не просто один элемент, но связанный список. Главное, что такое слегка снижает производительность, но допустимо.

Answer 2

[Дмитрий]

хеш-таблица - массив с парами ключ\значение (в широком смысле)
связанный список - список, который в каждом из "узлов" содержит не только собственные данные, но и по одной ссылке(связке) на следующий и предыдущий
"by Google"

Answer 3

[Roman K]

В чём разница макарон от сосиски в тесте и есть ли она вообще? Или это одно и то же?

Comments

[Макс]

Вопрос об их отличии. Чем они отличаются?

[Roman K]

Макс, ну как тебе сказать... Всем, например.

[Макс]

Roman Kitaev, Я только что понял тупость свого вопроса.

[Сергей Соколов]

связный список – это как раз сосиски, связка сосисок. Каждая знает только 2 соседние.
хэш-таблица это меню буфета с ценами.

[Roman K]

Сергей Соколов, Серёжа, ты странные сосиски ешь, если они знают соседей.

[pfg21]

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