Почему в хеш-таблицах поиск выполняется за время O(1), а не за O(N)? Программирование

Question

Почему в хеш-таблицах поиск выполняется за время O(1), а не за O(N)? Программирование

Андрей Иванов Профи (705), закрыт 8 лет назад

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

Answer 1

The Cat Искусственный Интеллект (116174) 8 лет назад

Это означает, что имея хеш, вы сразу получаете значение, без перебора, и это время не зависит от N.

Андрей ИвановПрофи (705) 8 лет назад

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

The Cat Искусственный Интеллект (116174) Представьте себе массив A. Чтобы получить пятый элемент, мы пишем A[4] (элементы обычно нумеруются с нуля). Не имеет значения, сколько элементов в массиве A, мы всегда будем получать A[4] с одинаковой быстротой. Так и с хеш-таблицами -- то же самое, только вместо числового индекса -- хеш.

Answer 2

Капитан Гугл Искусственный Интеллект (146235) 8 лет назад

Потому что ты не прочитал, что такое хеш-таблица, а писать тебе тут определение из интернета бессмысленно - ты же в интернете его не прочитал, а значит, и тут не прочитаешь.

Андрей ИвановПрофи (705) 8 лет назад

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

Капитан Гугл Искусственный Интеллект (146235) Вот в этом и проблема: там значительно больше написано, а ты прочитал только три строчки и требуешь, чтобы все остальное тебе написали тут. А ты снова не будешь читать, а прочтешь только три строчки...

Answer 3

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

допустим (как очень хреновый пример), список имён.

можно тупо раскидать по длине имени.
само собой, повторы могу быть.
ну так добавим туда код первого символа.
уже вариантов повтора меньше станет
но есть же люди с абсолютно одинаковыми именами
как же быть?
а не как... каждый такой вариант получит одинаковый хэш
но среди повторов выбрать нужный будет куда проще, чем из всей кучи

ну и поскольку реальные алгоритмы хеширования не на столько примитивны, то и вероятность повторов можно считать "нулевой"

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