Usando BitSet para guardar ids

Todos los programadores conocemos de sobra la mayoría de estructuras de datos que existen. Bien porque las usamos a diario o porque las hemos estudiado en la facultad, a nadie le resulta raro un array, un mapa (o hash) o una lista enlazada entre otras muchas. Para los programadores Java (u otro lenguaje de la JVM), las interfaces Collection y Map, junto con todas las clases que las implementan son el pan nuestro de cada día.

Sin embargo, hay algunas estructuras de datos que quizá (solo quizá) no conocemos tanto y que son sumamente interesantes. Una de ellas es java.util.BitSet. Quizá sea poco conocida por varias razones: primero porque no implementa ni Collection ni Map ni ninguna otra interfaz del api colecciones. Tampoco hereda de ninguna clase especial: el BitSet es una clase suelta, sin más. Segundo porque su uso típico parece un tanto alejado de lo que usamos cada día. Es interesante tener cientos o miles de bits juntos, y poder hacer operaciones and, or y xor con ellos, pero en realidad pocas veces necesitamos hacer operaciones a nivel de bit. Sin embargo, es posible darle otros usos a BitSet. Veamos uno de ellos.

Otros usos de BitSet

Supongamos que queremos guardar una gran cantidad de números enteros. Por ejemplo, los ids de un tabla en una aplicación con una base da datos. Si, de acuerdo, podríamos decir que para eso basta con crear otra tabla relacionada donde puedo guardar estos ids, filtrarlos, ordenarlos, etc. Pero no, supongamos que por cualquier razón, no queremos/podemos hacer esto. Si no conociéramos la clase BitSet, una primera solución sería guardar los ids en un List (ArrayList/LinkedList, no importa), el cual crecerá linealmente a medida que guardamos los ids.

Es decir, el tamaño que ocupa en memoria el List es directamente proporcional al número de elementos que almacena. Y aquí el problema viene cuando tenemos muchos, muchos elementos que guardar, por ejemplo 10.000.000. Tener 10 millones de integers es un array muy muy grande. Quizá podemos ahorrar algo de espacio con un BitSet, usando algunos trucos.

Veamos un BitSet como un array de booleanos, donde podemos preguntar una posición y que nos diga si es true o false (si el bit está a 1, es true; y si está a 0, es false). Usando el BitSet desde este punto de vista, podemos aprovechar para guardar los elementos posicionalmente. Es decir, en vez de guardar los valores, como se hacía en un List, el BitSet almacena las posiciones donde están los valores a guardar. Así, si queremos guardar el id 14, llamamos a nuestro BitSet y activamos el bit de la posición 14.

Un BitSet guardando el valor 14 simplemente tiene el bit 14 activo (a 1) y el resto desactivos (a 0)

              bit 14
                  v
000000000000000000100000000000000

Repetimos sucesivamente la misma operación con el resto de valores. Si ahora guardamos el 3 y 7, tendríamos un BitSet así:

              bit 14     7   3
                  v      v   v
000000000000000000100000010001000


Crecimiento de un BitSet

El tamaño y crecimiento de un BitSet viene dado por la posición más alta que en él guardamos. Así que no importa cuantos elementos introduzcamos en el BitSet, éste ocupará siempre lo mismo y solo crecerá cuando introduzcamos un elemento con un valor mayor. Es decir, ocupará lo mismo con los bits 3, 7 y 14, que si añadimos todos los bits 0, 1, 2, 3…12, 13 y 14. En ambos casos tiene que reservar sitio para 14 bits.

En resumen, un BitSet crece en función del bit más grande que almacena y un List en función del número de elementos que tiene. Para saber hasta cuanto puede crecer un BitSet tenemos que saber cual es el bit más grande. Después dividimos entre 32 (un Integer son 32 bits, de esta manera podemos hacer una comparación directa con el List de Integers) y ya sabemos cuanto ocupa en memoria. Por otro lado, un ArrayList crece en función del número de elementos que tiene, por lo que para saber cuanto ocupa, tan solo tenemos que ver cuantos elementos hemos insertado.

Todo esto provoca algunas situaciones que debemos valorar. Si vamos a guardar pocos elementos, y estos además tienen un valor muy alto, entonces vamos a desaprovechar mucho espacio. Por ejemplo: tenemos que guardar los valores 14 y 2510. En un List esto supone solo 2 Integers, uno para cada elemento. En un BitSet supone gastar bits hasta la posición 2510 (lo que hacen 79 elementos de 32 bits, o 79 Integers)

Pero si vamos a guardar más elementos, entonces es posible que nos compense un BitSet frente al List. Por ejemplo, queremos guardar solo los números pares del 0 al 2000, lo que suponen 1000 valores. Ahora el BitSet necesita bits hasta la posición 2000, lo que suponen 64 Integers, mientras que el ArrayList necesitaría 1000 Integers, uno por cada valor.

Hacer unos cuantos números antes de decidir qué colección usar nos puede hacer ahorrar bastante espacio. Por lo que la fórmula mágica es, usando la implementación de Java 6 usa en la que se usa un Long por cada 58 bits, si la densidad de tu colección es mayor que 1/58, entonces es preferible usar BitSet. Es decir, si (nº de elementos/valor más alto) > 0,01724 (1,72%). Todo esto suponiendo que nuestro List sea de Integers, si es de Longs, que ocupan el doble, entonces es la mitad.

– Resumen a ojo: si en nuestra tabla el id más alto es un millón, entonces nos compensa usar un BitSet a partir de 1720 ids por colección. –

Trabajando con la clase BitSet

Manipular un BitSet es extremadamente sencillo, si bien difiere un poco a como estamos acostumbrado de las clases List

BitSet bs = new BitSet();

// Número de elementos que tiene "activos" (bits a 1)
assert 0 == bs.cardinality();

// Añadimos 3 elementos: 0, 14, 2400 y el 80000
bs.set(0, true);
bs.set(14, true);
bs.set(2400, true);
bs.set(80000);  // Si no pasamos parametro, por defecto es true

// Número de elementos que tiene "activos" (bits a 1)
assert 4 == bs.cardinality();

// Borrar un elemento es simplemente asignarlo a false
bs.set(14, false);

// Para saber si hay un elemento activo
assert bs.get(0) == true;
assert bs.get(14) == false;
assert bs.get(2400) == true;

Hasta aquí muy fácil. Pero, ¿cómo itero los valores? No tenemos iterator(), así que tendremos que hacerlo así:

int value = -1;
while ((value = bs.nextSetBit(value+1)) != -1) {
    System.out.println(value);
}

Finalmente y de regalo, si queremos persistir a disco nuestro BitSet, podemos usar este código (que en realidad sirve para persistir cualquier objeto):

// Como guardarlo (comprimido, para que ocupe menos)
ByteArrayOutputStream baos = new ByteArrayOutputStream();
ObjectOutputStream oos = new ObjectOutputStream(new java.util.zip.GZIPOutputStream(baos));
oos.writeObject(bs);
oos.close();

// Como volverlo a leer
ObjectInputStream ois = new ObjectInputStream(
    new java.util.zip.GZIPInputStream(new ByteArrayInputStream(bytes)));
BitSet bs = (BitSet) ois.readObject();
ois.close();

¡Espero que os haya sido de utilidad!

Bola extra: como siempre, esto es solo la punta del iceberg. Hay otras implementaciones de BitSet optimizadas para que el tamaño que necesitan en memoria no sea lineal con respecto al tamaño del bit más grande que almacenan, como FastBitSet de Javolution, o Javaewah.