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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

Ответ 4

Словарь Python внутренне реализуется с хэш-таблицей.

Ответ 5

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

Ответ 6

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