Почему BitSet Java внутренне хранит длинный массив, но использует int для метода set?

Question

Согласно реализации BitSet, он внутренне использует массив longs:

/**
 * The internal field corresponding to the serialField "bits".
 */
private long[] words;

Но для метода set он использует int:

public void set(int bitIndex) {...}

Итак, в основном мы можем хранить (2^31 - 1) * 64 * 8 = 2,147,483,642 * 64 * 8 = 137,438,953,088 bits, но при индексировании int мы имеем доступ только к первым 2,147,483,648 битам.

Это означает, что 137,438,953,088 - 2,147,483,648 = 135,291,469,440 битов недоступны.

Но если бы разработчики этого класса использовали long вместо int для индексации битов, это решило бы все проблемы, поскольку с long мы можем перемещаться по корыту 2^63 - 1 = 9,223,372,036,854,775,807 bits

Это не имеет никакого смысла даже с точки зрения производительности.

Что за логические причины c использования int вместо из long для индексации и пропущенных миллиардов бит?

PS Можно сказать, что проблема в размере 2 GiB кучи, но сегодня это больше не проблема.

Answer 1

Каждый фрагмент из 64 бит упакован в длинный, а не один длинный индекс на бит, поэтому длина массива long [] words будет использовать до 268 435 456 байт с индексом int при вызове set (2147483647) или только один длинный при вызове только bitset.set (1). Пример в jshell:

BitSet b = new BitSet();
b.size();
==> 64 (ie words is length 1 can store 64 bits)
b.set(1);
b.size();
==> 64 (ie words is still length 1)
b.set(64)
==> 128 (ie words array is length 2, can store up to 128 bits)

Answer 2

В документации к java.util.BitSet говорится:

Биты BitSet индексируются неотрицательными целыми числами.

Это что он должен делать, поэтому индексы long не требуются.

То, что его внутренняя структура данных может поддерживать более 2 ^ 31 отдельных битов, является деталью реализации, не имеющей отношения к интерфейсу publi c класса (они могли бы использовать массив boolean[], и класс по-прежнему работал бы, хотя и с большим объемом памяти и большим временем выполнения для некоторых методов.)

---

Остается вопрос: будет ли publi c интерфейс этого класса изменился для поддержки long индексов?

Это маловероятно, потому что поддержка long индексов будет означать, что такие методы, как

• int cardinality()
• int nextClearBit() (и аналогичные методы: следующая / предыдущая очистка / установка бита)
• int size()
• IntStream stream()

также необходимо изменить, что приведет к поломке существующего кода.

Единственный w ау, я могу думать о BitSet -подобном классе с long индексами, это был бы дополнительный класс BigBitSet (или LongBitSet или что угодно), чтобы люди нуждались в битовых наборах с более чем 2 ^ 31 бит может переключиться на этот новый класс.

Будет ли такой класс когда-либо добавлен в пакет java.util - это другой вопрос - для этого вам придется убедить исполнительный совет JCP, что это важное дополнение / зияющая дыра в текущей Java экосистеме.

Answer 3

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

BitSet b = new BitSet();
b.set(2147483647);
ArrayList<X> items = new ArrayList<X>();
// ...add a looot of elements to the ArrayList...
// then:
X item = items.get(b.nextSetBit(0));

Чтобы эта работа работала, список массивов должен содержать 2 147 483 648 элементов, и он будет использовать как минимум 2 ГБ ОЗУ (при условии, что для каждого элемента требуется как минимум 1 байт памяти), в результате чего sh Java.