Быстрая структура данных для содержит () в Java?

Question

Какая структура данных в Java, которая выполняет самую быструю операцию для функции contains ()?

например, у меня есть набор чисел {1, 7, 12, 14, 20 ...}

Учитывая другое произвольное число x, каков самый быстрый (в среднем) способ для генерации логического значения того, содержится ли x в наборе или нет?Вероятность для! Contains () примерно в 5 раз выше.

Все ли структуры карт обеспечивают операцию o (1)?HashSet - самый быстрый путь?

Answer 1

посмотрите на реализации на основе множеств (Hashset, enumset) и hash (HashMap, connectedhash ..., idnetityhash ..) у них есть O (1) для содержит ()

Эта таблица очень полезна.

Answer 2

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

Answer 3

Единственной структурой данных, более быстрой, чем HashSet, скорее всего, будет TIntHashSet от Trove4J. Это использует примитивы, избегая необходимости использовать целочисленные объекты.

Если число целых чисел мало, вы можете создать логическое значение [], в котором каждое имеющееся значение превращается в «истину». Это будет O (1). Примечание: HashSet не гарантированно будет O (1) и, скорее всего, будет O (log (log (N))).

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

Answer 4

хэширование (хэш-набор) является лучшим с O (1)