Коллекция ключей Java со сложностью O (1) для миллионов случайных неупорядоченных ключей

Я думаю, вы путаете, что представляет собой нотация Big O. Он определяет ограничивающее поведение функции, не обязательно фактическое поведение.

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

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

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

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

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

Нет, такой (известной) структуры данных для универсальных типов данных не существует.

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

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

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