Каково истинное различие между словарем и хэш-таблицей?
6 ответов
Словарь - это общая концепция, которая отображает ключи к значениям. Есть много способов реализации такого отображения.
Hashtable - это определенный способ реализации словаря.
Помимо HASHTABLES, еще один распространенный способ реализации словарей красно-черные деревья .
Каждый метод имеет свои собственные плюсы и минусы. Красное черное дерево всегда может выполнить поиск в O (log n). Hashtable может выполнять поиск в O (1) время, хотя это может ухудшить до O (n) в зависимости от ввода.
«Словарь» имеет несколько разных значений в программировании, как Wikipedia скажет вам - «ассоциативный массив», смысл, в котором Python использует термин (также Известен как «картографирование»), является одним из тех значений (но «словарь данных», а также «словарные атаки» в попытках угадывания пароля также важны).
Хэш-таблицы являются важными структурами данных; Python использует их для реализации двух важных встроенных типов данных, Dict и и .
Итак, даже в Python, вы не можете рассмотреть «хэш-таблица», чтобы быть синонимом «словаря» ... поскольку аналогичная структура данных также используется для реализации «множеств»! -)
Словарь Python внутренне реализован с помощью Hashtable.
Словарь - это структура данных, которая отображает ключи к значениям.
Таблица HASH - это структура данных, которая отображает ключи от значений, принимая значение хеширования ключа (путем нанесения некоторой хэш-функции к нему) и отображение этого в ведро, где хранятся одно или несколько значений.
ИМО Это аналогично задавать разницу между списком и связанным списком.
Для ясности может быть важно отметить, что это может быть тот случай, когда Python в настоящее время реализует свои словари с использованием хэш-таблиц, и это может быть в будущем, что Python изменяет этот факт, не вызывая их словари, чтобы перестать быть словарями.
Тахнетная таблица всегда использует некоторую функцию, работающую на значении, чтобы определить, где будет сохранено значение. Словарь (поскольку я считаю, что вы намереваетесь его) - это более общий термин, и просто указывает на механизм поиска, который может быть хеш-таблицей или может быть реализован упрощенной структурой, которая не учитывает самого значения в определении его хранения.
словарь реализуется с использованием хеш-таблиц. На мой взгляд, разница между 2 может рассматриваться как разница между стеками и массивами, где мы будем использовать массивы для реализации стеков.