Самая быстрая структура данных для содержит () в Java?
То, какова структура данных в Java, который начинает самую быструю операцию для, содержит ()?
например, у меня есть ряд чисел {1, 7, 12, 14, 20...}
Учитывая другое произвольное число x, что самый быстрый путь состоит в том, чтобы (в среднем) сгенерировать булево значение того, содержится ли x в наборе или нет? Вероятность для! содержит (), о 5x выше.
Все структуры карты обеспечивают o (1) операция? Действительно ли HashSet является самым быстрым способом пойти?
4 ответа
посмотрите на реализации на основе набора (Hashset, enumset) и хеша (HashMap, connectedhash ..., idnetityhash ..). у них O (1) для contains ()
Эта шпаргалка очень помогает.
Для вашего конкретного случая чисел с относительно высокой плотностью я бы использовал BitSet, это будет быстрее и намного меньше, чем хэш-множество.
Единственная структура данных, которая быстрее, чем HashSet, вероятно, будет TIntHashSet от Trove4J. При этом используются примитивы, исключающие необходимость использования целочисленных объектов.
Если количество целых чисел невелико, вы можете создать логическое значение [], в котором каждое имеющееся значение превращается в «истину». Это будет O (1). Примечание. Не гарантируется, что HashSet будет иметь значение O (1) и, скорее всего, будет иметь значение O (log (log (N))).
Вы получите только O (1) для идеального распределения хешей. Однако более вероятно, что вы столкнетесь с конфликтами хешированных сегментов, и при некоторых поисках потребуется проверить более одного значения.