Временная сложность таблицы Hash

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

Ответ 1

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

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

Ответ 2

Для некоторых видов использования хэш-таблиц невозможно заранее создать их из "правильного" размера, так как неизвестно, сколько элементов необходимо будет удерживать одновременно в течение всей жизни таблицы. Если вы хотите поддерживать быстрый доступ, вам нужно время от времени изменять размер таблицы по мере увеличения количества элементов. Это изменение размера занимает линейное время относительно количества элементов, уже находящихся в таблице, и обычно выполняется при вставке, когда числовые элементы проходят порог.

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

На практике это не проблема, если вы не создаете жесткие приложения реального времени.

Ответ 3

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

refer: http://www.cs.unc.edu/~plaisted/comp550/Neyer%20paper.pdf (раздел таблицы хэшей)