Я читал Javadocs на HashSet, когда наткнулся на интересное утверждение:

Этот класс предлагает постоянное время выполнения для основных операций (добавление, удаление, содержание и размер)

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

Если это так, то независимо от того, сколько данных я сбрасываю в свой HashSet, я буду иметь доступ к любому элементу в постоянное время. То есть, если я добавлю 1 элемент в мой HashSet, потребуется столько же времени, чтобы найти его, как если бы у меня был элемент googolplex.

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

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

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

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

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

Замечания:Эта почта а такжеэта почта оба не решают проблемы, которые я перечислил ..