Ответ зависит от характеристик хеш-функции и конкретного значения альфа.Наихудший случай имеет место, если хеш достигает плохого распределения (для любой альфы), и, как вы указали в своем первоначальном посте, равен O (N).Наилучший случай возникает, когда у вас хорошо распределенный хеш, а альфа относительно велика (> 1,0), и, как вы сказали, это O (1).Таким образом, мы договариваемся о лучшем и худшем случаях.
Однако я думаю, что средний случай требует большего анализа, потому что альфа оказывает нелинейное влияние на производительность.Рассмотрим два крайних примера.Случай 1, альфа = 100, 1000, 10000. Поскольку альфа масштабируется до бесконечности, у вас не будет предотвращаемых коллизий (то есть тех, которые вызваны необходимостью усекать хэши для отображения в M сегментов, в отличие от неоднородного поведения хэша),и поэтому средний случай сходится к лучшему, или O (1).Случай 2, альфа = 0,01, 0,001, 0,0001.Поскольку альфа масштабируется до нуля, у вас будет все меньше и меньше хеш-блоков до тех пор, пока вся таблица не станет всего лишь одним хеш-пакетом со всеми значениями в одном списке в этом сегменте, и поэтому средний случай сходится к наихудшему случаю линейного поиска, или O (N).
Средний регистр между O (1) и O (N), в зависимости от альфа.Мы могли бы выразить это как O (N ^ x), где x - это функция, которая отображает альфа = 0 в x = 1, а альфа = бесконечность в x = 0. Так что для обсуждения (см. http://en.wikipedia.org/wiki/Heaviside_function), может быть что-то вроде O (N ^ (e ^ (- alpha))).