- допустим, длина строки равна L. Когда мы вставляем это в хеш-таблицу (скажем, мы используем раздельную цепочку), в первую очередь вычисляется хэш строки. Как происходит вставка в хеш-таблицу O(1), разве она не должна быть O(L), поскольку время вычисления хэша строки увеличивается с размером строки?
- после вычисления хеша строка сохраняется в хеш-таблице. Разве это копирование не займет O(L)?
- когда строка просматривается в хеш-таблице, как может ли это быть постоянная операция? Потому что снова вычисляется хеш для строки, а затем в вычисленном сегменте сравнивается строка, которая в худшем случае также должна быть O(L).
Я пробовал задавать вопросы в ChatGPT, а также искал решения на сайтах, но они были противоречивыми. В ChatGPT указано, что это будет O(L), но на некоторых веб-сайтах указано, что это будет O(1).
Подробнее здесь: https://stackoverflow.com/questions/790 ... able-is-o1
