@Rild2

Как работает поиск в хэш-таблицах?

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

Почему? Разве в обычном массиве и хэш-таблице не одинаковое количество элементов?
Поиск, по-моему, должен занимать O(n) времени, несмотря на то, сколько значений в массиве и несмотря на то, есть ли в нём ключи или нет. Просто в массиве мы сравниваем каждый элемент с нужным, а в хэш-таблице сравниваем значение каждого ключа с нужным... и в чём тогда разница по времени?
  • Вопрос задан
  • 92 просмотра
Пригласить эксперта
Ответы на вопрос 3
Anopeng
@Anopeng
Веб-программист, учу фронт и бек
У нас есть определенное строчное значение, по которому мы хотим найти или добавить элемент в хеш-таблице. Сначала нам нужно узнать хеш строки - это уникальное число, которое мы получаем в результате провождения операций хеш-функции над строкой. Мы получили число, и как раз это число мы используем как индекс к хеш-таблице (по сути, это просто массив, в котором время поиска составляет O(1)). А про хеш-функции и коллизии нужно уже читать отдельно
Ответ написан
SilenceOfWinter
@SilenceOfWinter
та еще зажигалка...
это какой-то винегрет из прочитанного, для начала стоит разобраться как работает поиск в списках/массивах и что-такое бинарные деревья, а потом уже идти дальше.
Ответ написан
Комментировать
@mayton2019
Bigdata Engineer
Хеш-таблица - это не массив. Хотя она может опираться на массив как на базовую структуру хранения (в случае метода открытой адресации). В классическом варианте хеш таблица - это совокупность структур данных в памяти. Массив массивов. Или массив списков (как будет угодно).

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

Вообще русская wiki достаточно хорошо описывает ХТ и можно начать читать с нее и далее по ссылкам.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы