Всем доброго времени суток. Я относительно недавно начал знакомиться с алгоритмами и нашёл такое понятие, как хэш-таблицы - массивы, где каждому значению принадлежит свой уникальный ключ. Мне не особо понятно, как находятся значения в хэш-таблицах, но считается, что в них поиск элементов происходит быстрее всего.
Почему? Разве в обычном массиве и хэш-таблице не одинаковое количество элементов?
Поиск, по-моему, должен занимать O(n) времени, несмотря на то, сколько значений в массиве и несмотря на то, есть ли в нём ключи или нет. Просто в массиве мы сравниваем каждый элемент с нужным, а в хэш-таблице сравниваем значение каждого ключа с нужным... и в чём тогда разница по времени?
А стоп, пардон)
Только что прочитал, что сложность поиска равна log2 (n), что аналогично бинарному поиску. Получается, хэш-ключи - это числа, отсортированные по возрастанию?
У нас есть определенное строчное значение, по которому мы хотим найти или добавить элемент в хеш-таблице. Сначала нам нужно узнать хеш строки - это уникальное число, которое мы получаем в результате провождения операций хеш-функции над строкой. Мы получили число, и как раз это число мы используем как индекс к хеш-таблице (по сути, это просто массив, в котором время поиска составляет O(1)). А про хеш-функции и коллизии нужно уже читать отдельно
Спасибо за ответ, но мне нужно было узнать, не как получить ключ для значения в хэш-таблице, а как происходит именно сам поиск нужного ключа. Если это действительно занимает всего O(1) времени, то на каком алгоритме это устроено? Мне в голову приходит только простой поиск O(n) и бинарный (это если ключи отсортированы по возрастанию), правда даже в этом случае поиск займёт O(log2 n).
O(1) как получается?
это какой-то винегрет из прочитанного, для начала стоит разобраться как работает поиск в списках/массивах и что-такое бинарные деревья, а потом уже идти дальше.
Хеш-таблица - это не массив. Хотя она может опираться на массив как на базовую структуру хранения (в случае метода открытой адресации). В классическом варианте хеш таблица - это совокупность структур данных в памяти. Массив массивов. Или массив списков (как будет угодно).
Про количество элементов - это сложный вопрос. Хеш таблица (ХТ) обычно резервирует памяти чуть больше чем надо. И экстендится когда памяти не хватает. Там для экстенда есть отдельный алгоритм. Можно считать что оверхед такой хеш-таблицы больше чем у массива. А количество элементов фактически - хранится отдельным счетчиков.
Вообще русская wiki достаточно хорошо описывает ХТ и можно начать читать с нее и далее по ссылкам.
Средний
