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

Question

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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