Хеш-таблица это не О(1)

[hard2018]

Тут такое дерьмо тормозное.

[shlmzl]

Непонятно за что минусов накидали автору в рейтинг статьи. Может за то что публично усомнился в общепринятой догме. Народ на всяких тестах, олимпиадных задачках бизнес построил, а тут пришел непонятный перец и публично заявил - Сомневаюсь я, однако. Или может где-то ляпнул что-то невпопад такое специфическое, что как бы нехорошо его там же отминусовать, поэтому минусуют тут. Как бы актуально для меня, и рад бы минусаторов не травмировать морально, но не очень понимаю как этого достичь.

[Tam1SH]

Я, конечно, не "минусатор", но мне, человеку, который знаком с внутренностями мейнстримных хеш-таблиц лишь поверхностно, кажется статья как рваной, так и неполной.

Может за то что публично усомнился в общепринятой догме

Думаю, что "догмой" это является для тех, кто не имеет представление о самом приниципе работы хеш-функции - преобразование данных неограниченной длины в данные с длиной фиксированной и из чего следует при таком сужении, что автор и написал, - коллизия. А дальше он начал реализовывать свой велосипед, выбрал простой метод борьбы с ней и... всё? Статья закончилась, ни сравнении с меинстримными реализациями, ни борьбы с деградацией скорости доступа к хеш-таблице при добавлении в ней огромного количества элементов, ни наглядных схем работы, т.к мне как читателю не сильно интересно склеивать в уме реализацию по сниппетам неизвестного мне ЯП.
Прочитав всё это я могу лишь сказать: "Доступ к хеш-таблице не за константное время происходит. Круто, и чё?"

[cpud47]

Здесь вместо внятно аргументации заголовка, просто самописная реализация хештаблицы. Это, как минимум, предаёт ожидания.

Дальше, позиция "поиск в хештаблице за O(1*)" более полезна, чем "поиск за O(n)". Вопрос только в том, в каком именно смысле там O(1) (этому можно придать строгую формулировку). В статье с таким заголовком я бы ожидал именно разбора различных формулировок и следствий из них.

Ну и в целом, хештаблицы — это инженерный трюк. А потому, разбирать абстрактную хештаблицу в вакууме смысла мало. Если уж и разбирать, то нужно брать конкретные реализации и особенности их работы.

Например, если взять хештаблицу в яве, то там не будет поиска O(n) даже в присутствии колизий (если ключи какие-нибудь строки, или числа — что почти всегда так). Просто потому, что бакеты там устроены как деревья, а не связанные списки.

Или, если взять хештаблицу в C#/Rust, то там другой подход. Там используется достаточно хорошая хешфункция, что спровоцировать колизии достаточно сложно даже в режиме "злоумышленика".

Поэтому разбор странный.

[yaSkazalGorbatiy]

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

[Spyman]

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

Отсюда два вопроса - вы уверены что ваша статья претендует на актуальность? (15 лет назад, когда я заканчивал учёбу, на Хабре уже были точно такие же статьи, и они никуда не делись).

И второй у меня к адекватности заголовка. Да, в худшем случае сложность операции будет o(n), но если вы не профессиональный профилировщик на сверхвысоконагруженном проекте - брать все равно имеет смысл о(1) для оценки, а иначе - у вас уже собака съедена на всех стандартных алгоритмах и структурах данных в используемом языке.

Имхо - заголовок слишком кликбейтен.

[MANAB]

Мне во всех описания попадалось, что сложность доступа O(1) только в идеальном случае, и на собеседованиях всегда приходилось объяснять что это значит и почему, а так же почему она не эквивалента сложности доступа по индексу массива.

Заголовок статьи же звучит как будто автору говорили, что сложность доступа строго O(1) и автор вдруг разобрался, что это не так.