В чем истинная разница между словарем и хеш-таблицей?

Question

Я всегда использовал словари. Я пишу на Python.

Answer 1

Словарь - это общая концепция, которая сопоставляет ключи со значениями. Есть много способов реализовать такое отображение.

Хеш-таблица - это особый способ реализации словаря.

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

У каждого метода есть свои плюсы и минусы. Красно-черное дерево всегда может выполнить поиск в O (log N). Хеш-таблица может выполнять поиск за время O (1), хотя это может ухудшиться до O (N) в зависимости от входа.

Answer 2

Словарь - это структура данных, которая сопоставляет ключи со значениями.

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

IMO это аналогично запросу разницы между списком и связанным списком.

Для ясности может быть важно отметить, что это МОЖЕТ иметь место, когда Python в настоящее время реализует свои словари, используя хеш-таблицы, и это МОЖЕТ иметь место в будущем, когда Python изменяет этот факт, не заставляя их словари перестать быть словарями.

Answer 3

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

Хеш-таблицы являются важными структурами данных; Python использует их для реализации двух важных встроенных типов данных, dict и set.

Таким образом, даже в Python вы не можете считать "хеш-таблицу" синонимом словаря ... так как аналогичная структура данных также используется для реализации "множеств"! -)

Answer 4

Словарь Python внутренне реализован с помощью хеш-таблицы.

Answer 5

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

Answer 6

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