30
Я всегда пользовался словарями. Я пишу на Python.В чем разница между словарем и хеш-таблицей?
A
ответ
130
Словарь - это общая концепция, которая отображает ключи в значения. Существует множество способов реализации такого сопоставления.
Хэш-таблица - это особый способ реализации словаря.
Кроме хештейнов, еще один распространенный способ реализации словарей - red-black trees.
У каждого метода есть свои плюсы и минусы. Красно-черное дерево всегда может выполнять поиск в O (log N). Хэш-таблица может выполнять поиск в O (1) раз, хотя это может ухудшиться до O (N) в зависимости от ввода.
8
Словарь Python внутренне реализован с помощью хеш-таблицы.
+0
Подкласс dict не является реализацией словаря Python; это ваше собственное. –
22
Словарь - это структура данных, которая отображает ключи в значения.
Хэш-таблица - это структура данных, которая отображает ключи к значениям, принимая значение хэша ключа (путем применения к нему некоторой хеш-функции) и сопоставления с ведром, в котором хранится одно или несколько значений.
IMO это аналогично заданию разницы между списком и связанным списком.
Для ясности может быть важно отметить, что МОЖЕТ быть в таком случае, что Python в настоящее время реализует свои словари с использованием хеш-таблиц, и в будущем возможно, что Python изменит этот факт, не заставляя словари перестать быть словарями ,
+0
Не было ли главное отличие в том, что словарь также хранит ключи? Таким образом, вы можете запросить словарь для ключей ключей - вы не можете использовать хэш-таблицу –
+1
@Martin Beckett: Нет. Оба могут хранить ключи. Словарь является общим. Хэш-таблица - это конкретная реализация общей концепции. –
+0
@ Мартин Беккет: Хм, интересный момент. Обязательно ли это, что словарь хранит ключи и хеш-таблицу? Java 'Hashtable' хранит ключи - не это ли хэш-таблица? – danben
13
«Словарь» имеет несколько различных значений в программировании, так как wikipedia расскажет вам - «ассоциативный массив», смысл, в котором Python использует термин (также известный как «сопоставление»), является одним из тех Также важны значения (но «словарь данных» и «словарные атаки» в попытках угадывания пароля).
Хэш-таблицы являются важными структурами данных; Python использует их для реализации двух важных встроенных типов данных: dict и set.
Таким образом, даже в Python, вы можете не считать «хэш-таблицей», чтобы быть синонимом «словарь» ... так как подобная структура данных также используются для реализации «наборов» -!)
0
Словарь реализуется с использованием хеш-таблиц. На мой взгляд, разницу между двумя можно рассматривать как разницу между Stacks и Arrays, где мы будем использовать массивы для реализации Stacks.
1
Хэш-таблица всегда использует некоторую функцию, действующую на значение, чтобы определить, где будет храниться значение. Словарь (как я полагаю, вы его намереваетесь) является более общим термином и просто указывает механизм поиска, который может быть хеш-таблицей или может быть реализован более простой структурой, которая не учитывает само значение при определении места хранения.
Смежные вопросы
- 1. В чем разница между словарем и массивом?
- 2. Разница между объектом и словарем?
- 3. В чем разница между хеш-таблицей и словарем в C
- 4. В чем разница между коллекцией ассоциаций и словарем в Smalltalk?
- 5. В чем разница между словарем и картой в Javascript 6?
- 6. В чем разница между словарем схемы и данных?
- 7. разница между IEnumerable и словарем C#
- 8. F #: Разница между Словарем, Hashtable и Map
- 9. Разница между HashMap и словарем ADT
- 10. Разница между словарем и orderdict в python
- 11. В чем разница между хэш-картой, хэш-множеством, хеш-словарем?
- 12. разница между хэшем Perl и словарем python
- 13. swift: разница между массивом 2d и словарем
- 14. В чем разница между dict() и {}?
- 15. В чем разница между «и»?
- 16. В чем разница между `{}` и `[]`?
- 17. В чем разница между == и ===?
- 18. В чем разница между «+» и «\ +»?
- 19. В чем разница между + = и = +?
- 20. В чем разница между/* ... */и/** ... */
- 21. В чем разница между: и +:
- 22. В чем разница между $ {} и # {}
- 23. В чем разница между $ _. и $ _
- 24. В чем разница между = и: =
- 25. В чем разница между && и &?
- 26. В чем разница между $ {} и # {}?
- 27. В чем разница между + и%?
- 28. В чем разница между + = и = +
- 29. В чем разница между # {} $ {} и% {}?
- 30. В чем разница между «» и «»?
Хотел бы я проголосовать за него один раз. – LJM
Я заново его подниму. –