Я всегда пользовался словарями. Я пишу на Питоне.
В чем истинная разница между словарем и хеш-таблицей?
Ответы (6)
Словарь — это общая концепция, которая сопоставляет ключи со значениями. Есть много способов реализовать такое отображение.
Хэш-таблица — это особый способ реализации словаря.
Помимо хеш-таблиц, другим распространенным способом реализации словарей являются красно-черные деревья.
У каждого метода есть свои плюсы и минусы. Красно-черное дерево всегда может выполнять поиск за O(log N). Хеш-таблица может выполнять поиск за время O(1), хотя это может ухудшиться до O(N) в зависимости от ввода.
person
R Samuel Klatchko
schedule
14.01.2010
Словарь — это структура данных, которая отображает ключи в значения.
Хеш-таблица — это структура данных, которая сопоставляет ключи со значениями, беря хэш-значение ключа (путем применения к нему некоторой хэш-функции) и сопоставляя его с сегментом, в котором хранится одно или несколько значений.
ИМО, это аналогично вопросу о разнице между списком и связанным списком.
Для ясности может быть важно отметить, что в настоящее время Python МОЖЕТ реализовать свои словари с использованием хеш-таблиц, и в будущем МОЖЕТ случиться так, что Python изменит этот факт, не заставив их словари перестать быть словарями.
person
danben
schedule
13.01.2010
Разве главное отличие не в том, что словарь также хранит ключи? Таким образом, вы можете запросить словарь для поиска ключей, но не для хеш-таблицы.
- person Martin Beckett; 14.01.2010
@Мартин Беккет: Нет. Оба могут хранить ключи. Словарь общий. Хеш-таблица — это конкретная реализация общей концепции.
- person S.Lott; 14.01.2010
@Martin Beckett: Хм, интересный момент. Обязательно ли словарь хранит ключи, а хеш-таблица — нет? Java
Hashtable хранит ключи - тогда это не хеш-таблица?
- person danben; 14.01.2010
Если подумать, хеш-таблица обязательно должна хранить ключи на случай коллизий!
- person Martin Beckett; 14.01.2010
@danben: Нет. Хранение ключей не является отличительной чертой. Отличительной особенностью является то, что словарь — это общая концепция, а хэш-таблица — фактическая реализация.
- person S.Lott; 14.01.2010
Словарь — это общая концепция — классы, которые хранят и извлекают значения на основе ключей. Словарь (в этой интерпретации — неясный вопрос) — это не структура данных — это слово вообще не подразумевает какой-либо конкретной структуры, а просто простой набор операций (сохранение, извлечение, обычно enumerate), которые предоставляют многие фактические структуры данных.
- person Glenn Maynard; 14.01.2010
@Glenn Maynard: В чем здесь разница между структурой данных и концепцией? Можете ли вы привести пример словаря, который не является структурой данных?
- person danben; 14.01.2010
Было бы более приемлемо говорить об абстрактной структуре данных? Я всегда использовал два взаимозаменяемых. Я думаю, что концепция становится слишком расплывчатой.
- person danben; 14.01.2010
@danben На самом деле хранение ключей необходимо для обнаружения коллизий в любой реализации, где могут быть коллизии (потому что хеш-пространство меньше фактического пространства - это в большинстве случаев)
- person ntg; 03.06.2020
«Словарь» имеет несколько разных значений в программировании, как вам подскажет википедия: - «ассоциативный массив», смысл, в котором Python использует этот термин (также известный как «отображение»), является одним из этих значений (но также важны «словарь данных» и «атаки по словарю» при попытках подбора пароля) .
Хеш-таблицы являются важными структурами данных; Python использует их для реализации двух важных встроенных типов данных, dict и set.
Таким образом, даже в Python вы не можете считать «хеш-таблицу» синонимом «словаря»… поскольку подобная структура данных также используется для реализации «наборов»!-)
person
Alex Martelli
schedule
14.01.2010
Словарь Python внутренне реализован с помощью хеш-таблицы.
person
Nicolás
schedule
13.01.2010
Подкласс dict не является реализацией словаря Python; это твое собственное.
- person Nicolás; 14.01.2010
Хеш-таблица всегда использует некоторую функцию, работающую со значением, чтобы определить, где значение будет храниться. Словарь (как я полагаю, вы его имеете в виду) является более общим термином и просто указывает на механизм поиска, который может быть хэш-таблицей или может быть реализован более простой структурой, которая не учитывает само значение при определении его места хранения.
person
MickeyfAgain_BeforeExitOfSO
schedule
14.01.2010
Словарь реализован с использованием хеш-таблиц. На мой взгляд, разницу между двумя можно рассматривать как разницу между стеками и массивами, где мы будем использовать массивы для реализации стеков.
person
Thunderhashy
schedule
14.01.2010
