Время выполнения для вставки n элементов в пустую хеш-таблицу

Question

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

Итак: каково среднее время вставки n элементов в хеш-таблицу? Я понимаю, что это, вероятно, зависит от реализации, поэтому упомяните, о каком типе реализации вы говорите.

Например, если есть (log n) коллизии с равным интервалом, и каждая коллизия требует O (k) для разрешения, где k - текущий размер хеш-таблицы, то у вас будет это рекуррентное соотношение:

T(n) = T(n/2) + n/2 + n/2

(то есть, вы тратите время на вставку n / 2 элементов, затем вы сталкиваетесь с коллизиями, принимаете n / 2 для разрешения, затем вы делаете оставшиеся n / 2 вставки без коллизий). Это все равно заканчивается O (n), так что да. Но разумно ли это?

Answer 1

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

С теоретической точки зрения это ожидаемый амортизированный O (1).

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

Вы можете получить ожидаемую амортизированную O (1), используя динамическое идеальное хеширование :

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

Решение состоит в том, чтобы иметь две хеш-таблицы со второй таблицей для коллизий; разрешить коллизии на этой второй таблице, перестроив ее. В этой таблице будет O (\ sqrt {n}) элементов, поэтому размер будет увеличен до O (n).

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

Answer 2

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

Answer 3

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

Проще говоря, это означает, что вам придется платить одинаковую стоимость независимо от размера вашей структуры данных.

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

Answer 4

Почему бы просто не запустить несколько тестов в вашей системе? Возможно, если вы опубликуете источник, мы можем вернуться и протестировать их в наших системах, и мы действительно могли бы превратить это в очень полезное обсуждение.

Это не только реализация, но и среда, которая решает, сколько времени на самом деле займет алгоритм. Однако вы можете посмотреть, доступны ли какие-либо образцы для тестирования. Проблема, связанная с тем, что я буду публиковать свои результаты, будет бесполезной, поскольку люди понятия не имеют, что еще работает в моей системе, сколько оперативной памяти сейчас свободно и так далее. Вы можете иметь только широкую идею. И это примерно так же хорошо, как то, что дает тебе big-O.