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

46

В чем разница между Hashи Dictionary?

Исходя из сценариев, я чувствую, что они похожи, но я хотел выяснить точные различия. Поиск в Google мне не сильно помог.

data-structures hashing dictionary difference hashtable Сайрам
источник

Ответы:

92

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

Dictionaryявляется «правильным» именем интерфейса (= ADT ), то есть ассоциативным контейнером, который отображает (обычно уникальные) ключи на (не обязательно уникальные) значения.

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

Такая реализация имеет два важных свойства:

  1. ключи должны быть хэшируемыми и сопоставимыми по равенству .
  2. записи появляются в определенном порядке в словаре.

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

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

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

Конрад Рудольф
источник
4
Чтобы привести пример в C ++, стандартные ассоциативные шаблоны контейнеров не могут быть реализованы в виде хэшей, хотя следующий стандарт будет иметь то, что фактически является хеш-таблицами. Они призваны unordered_mapпоказать, что они делают, а не то, что они есть.
Дэвид Торнли
6
«Правильно» в соответствии с каким авторитетом? В некоторых языках, таких как Ruby и Perl, официальное - читайте «правильно» - название для этих структур - «хэш».
nohat
11
@nohat: обратите внимание на мое использование цитат. Кроме того, я уже объяснил , почему имя выбрано неудачно, не так ли? Так что, если вам требуется авторитет, я скажу, что это авторитет полиции теоретической информатики.
Конрад Рудольф
9
Интересно, что в Ruby 1.9 фактически невозможно реализовать Hashкласс с хэш-таблицей, поскольку Ruby 1.9 Hashсохраняет порядок вставки, а хеш-таблица - нет. Итак, в Ruby 1.9 имя Hashдаже не отражает реализацию.
Йорг Миттаг
7
@hippietrail Вы не правы - во-первых, это объективные описания. В конце концов, я понимаю, почему наименование плохое и неправильное (см. Ниже). «Слишком ленивый» - это художественная лицензия с моей стороны, но суть в том, что причина сокращения имени является внутренней, то есть нет причин использовать здесь короткое имя, кроме как для сокращения имени. И вы ошибаетесь насчет «словаря»: это просто официальное название структуры данных. Ваше определение «словарь» неверно в контексте информатики, и название предшествует Python на десятилетия.
Конрад Рудольф
8

«Словарь» - это название понятия. Хеш-таблица является возможной реализацией.

dan_waterworth
источник
1
Хеш также ADT. HashTable является реализацией Hash
Sairam
3
@Sairam Я думаю, что для хеш-функции гораздо более характерно хэш-функция, а не хеш-таблица.
JK.
@jk На самом деле «хэш» является результатом применения «хэш-функции / алгоритма» к некоторому входу. Omehoe «хэш-таблицы» или «хэш-карты» связывает и хешируемый объект с каким-либо объектом (объект в общей форме, не ограничиваясь ООП)
Йоханнес
Есть языки, которые используют Hash для ссылки на структуру словарного типа, а не просто на операцию хэш-функции. Руби, например .
Шон Бертон,
7

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

aufather
источник
Хеш также ADT. Есть ли какая-то особая разница между Hash и Dictionary ADT?
Сайрам
2
@Sairam: Нет, хеш - это вывод алгоритма определенного вида (хеш-функция).
5

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

т.е. (KEY => VALUE)

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

т.е. KEY => HASH FUNCTION => VALUE

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

Лучшее место для поиска: Википедия ( ассоциативный массив и хеш-таблица )

Росс
источник