Время выполнения для вставки 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 (n). По сути, вы должны указать, насколько неэффективен ваш расчет размера перефразировки, прежде чем вы сможете определить ожидаемый порядок.

Answer 2

  

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

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

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

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

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

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

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

Answer 3

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

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

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

Answer 4

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

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