Почему в хэш таблицах вставка и удаление занимает O(1), если по факту вся работа ведется в массиве, где эти две операции выполняются за O(n)?
Всем привет, будучи без пяти минут студентом, решил не тратить лето в пустую, поэтому решил прочитать книгу "Грокаем алгоритмы". При прочтении, задался вопросом, описанным сверху. Конечно, есть догадка, что в хеш таблице массив уже зарезервирован, из-за чего ячейки памяти массива не приходится, как либо изменять при вставке и удалении => и время выполнения будет постоянное. Но вопрос верна ли догадка или я чего-то не понимаю?
Ответы (1 шт):
вставка и удаление занимает О(1) потому что не смещаются элементы в массиве, все потому что информация о ячейках(ключах) хешируется, если я вставлю элемент с ключом 1 и другой с ключом 2, они в памяти таблицы не обязательно будут находится рядом. ключ ведь хэшируется и записывается в таблицу под индексом который представлен хэшем от ключа.
В общем все дело в хешировании!