Почему в хеш-таблицах поиск выполняется за время O(1), а не за O(N)? Программирование
Ведь для поиска элемента мы должны перебрать все элементы в таблице и найти нужный, в худшем случае.
Это означает, что имея хеш, вы сразу получаете значение, без перебора, и это время не зависит от N.
Потому что ты не прочитал, что такое хеш-таблица, а писать тебе тут определение из интернета бессмысленно - ты же в интернете его не прочитал, а значит, и тут не прочитаешь.
что есть хеш? это какое-то определённое число полученное обработкой каким-то определённым образом занесённой в таблицу величины
алгоритм вычисления хеша позволяет якобы каждой записи присвоить какое-то своё число.
допустим (как очень хреновый пример), список имён.
можно тупо раскидать по длине имени.
само собой, повторы могу быть.
ну так добавим туда код первого символа.
уже вариантов повтора меньше станет
но есть же люди с абсолютно одинаковыми именами
как же быть?
а не как... каждый такой вариант получит одинаковый хэш
но среди повторов выбрать нужный будет куда проще, чем из всей кучи
ну и поскольку реальные алгоритмы хеширования не на столько примитивны, то и вероятность повторов можно считать "нулевой"
и вот когда тебе надо найти какое-то имя, хэш твоего запроса мигом считается и получается число, которое по сути номер записи в таблице.
вот и получается что никаких переборов и никаких O(N) не будет
