El filtro de Bloom es una estructura de datos compacta que permite verificar pertenencia a un conjunto con una tasa de falsos positivos configurable. Su variante de conteo extiende esta funcionalidad al reemplazar bits por contadorres, habilitando la eliminación segura y la estimación del tamaño del conjunto. Esta implementación incorpora mecanismos de seguridad concorrencial mediante bloqueos de lectura-escritura, cálculo automático de parámetros óptimos y persistencia mediante serialización.

Objetivos de Diseño

La versión mejorada se propone superar las limitaciones estándar:

• Eliminación segura de elementos sin afectar otros registros.
• Control de acceso concorrencial con hilos múltiples.
• Estimación del número de elementos insertados.
• Evaluación dinámica de la tasa de falsos positivos basada en la carga actual.
• Configuración flexible de funciones hash y cálculo óptimo de dimensiones.
• Soporte para persistencia mediante serialización/deserialización.

Estructura de Datos Principal

El núcleo del filtro utiliza un arreglo de contadores de precisión limitada y un conjunto de funciones hash independientes:

private final short[] contadores; // Reemplaza el arreglo de bits para permitir incrementos/decrementos
private volatile int insercionesTotales = 0; // Registro aproximado de inserciones
private final ReadWriteLock bloqueo = new ReentrantReadWriteLock(); // Control de concurrencia
private final List<HashFunction> funcionesHash; // Funciones hash múltiples

La elección de short balancea uso de memoria y rango de valores (máximo 65535 por posición). El campo insercionesTotales se actualiza cuando un contador cambia entre 0 y 1.

Operaciones Fundamentales

Insertar Elementos

Al insertar, se incrementan los contadores en las posiciones hash. Si un contador pasa de 0 a 1, se considera una nueva posición ocupada:

public void insertar(String elemento) {
    bloqueo.writeLock().lock();
    try {
        for (HashFunction hf : funcionesHash) {
            int posicion = Math.abs(hf.hashString(elemento, StandardCharsets.UTF_8).asInt()) % m;
            contadores[posicion]++;
            if (contadores[posicion] == 1) {
                insercionesTotales++;
            }
        }
    } finally {
        bloqueo.writeLock().unlock();
    }
}

Eliminar Elementos

La eliminación decrementa contadores solo si son positivos, previniendo valores negativos:

public void eliminar(String elemento) {
    bloqueo.writeLock().lock();
    try {
        for (HashFunction hf : funcionesHash) {
            int posicion = Math.abs(hf.hashString(elemento, StandardCharsets.UTF_8).asInt()) % m;
            if (contadores[posicion] > 0) {
                contadores[posicion]--;
                if (contadores[posicion] == 0) {
                    insercionesTotales--;
                }
            }
        }
    } finally {
        bloqueo.writeLock().unlock();
    }
}

Consulta y Estadísticas

La verificación de pertenencia requiere que todos los contadores hash sean positivos. Las estadísticas se calculan derivando del número de inserciones totales:

public boolean contiene(String elemento) {
    bloqueo.readLock().lock();
    try {
        for (HashFunction hf : funcionesHash) {
            int posicion = Math.abs(hf.hashString(elemento, StandardCharsets.UTF_8).asInt()) % m;
            if (contadores[posicion] == 0) return false;
        }
        return true;
    } finally {
        bloqueo.readLock().unlock();
    }
}

public int estimarElementos() {
    bloqueo.readLock().lock();
    try {
        return (int) (insercionesTotales / (double) k);
    } finally {
        bloqueo.readLock().unlock();
    }
}

public double tasaFalsosPositivos() {
    bloqueo.readLock().lock();
    try {
        double n = estimarElementos();
        return Math.pow(1 - Math.exp(-k * n / m), k);
    } finally {
        bloqueo.readLock().unlock();
    }
}

Cálculo de Parámetros Óptimos

Las dimensiones del filtro (tamaño del arreglo m y número de funciones hash k) se determinan matemáticamente para minimizar espacio y falsos positivos:

private int tamanoOptimo(int n, double p) {
    return (int) (-n * Math.log(p) / (Math.pow(Math.log(2), 2)));
}

private int funcionesHashOptimas(int m, int n) {
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}

En el constructor se aplica un margen de seguridad del 20% al tamaño calculado para mejorar tolerancia a variaciones en la carga.

Estrategia de Funciones Hash

Se generan múltiples funciones hash mediante semillas diferentes para reducir colisiones:

for (int i = 0; i < k; i++) {
    HashFunction hf = Hashing.murmur3_128(0xABCDEF + i);
    funcionesHash.add(hf);
}

Seguridad Concorrencial

El uso de ReentrantReadWriteLock permite múltiples lecturas concurrentes mientras bloquea escrituras en exclusión mutua. Esto garantiza consistencia en entornos multihilo con un impacto mínimo en el rendimiento.

Persistencia y Serialización

La implementación soporta serialización mediante la interfaz Serializable, permitiendo guardar y restaurar el estado del filtro en almacenamiento persistente. Esto es esencial para servicios de larga duración o actualizaciones sin reinicio.

Validación mediante Pruebas

Se incluyen pruebas que verifican el comportamiento bajo operaciones de alta frecuencia y concurrencia:

public static void main(String[] args) throws InterruptedException {
    FiltroBloomConteoAvanzado filtro = new FiltroBloomConteoAvanzado(1000, 0.01);
    // Inserción y eliminación repetida para un elemento
    String item = "elementoPrueba";
    for (int i = 0; i < 1000; i++) filtro.insertar(item);
    System.out.println("Presente tras inserciones: " + filtro.contiene(item));
    for (int i = 0; i < 1000; i++) filtro.eliminar(item);
    System.out.println("Presente tras eliminaciones: " + filtro.contiene(item));

    // Prueba de concurrencia con múltiples hilos
    ExecutorService ejecutor = Executors.newFixedThreadPool(10);
    for (int i = 0; i < 5000; i++) {
        String elem = "item" + (i % 100);
        if (i % 3 != 0) ejecutor.execute(() -> filtro.insertar(elem));
        else ejecutor.execute(() -> filtro.eliminar(elem));
    }
    ejecutor.shutdown();
    while (!ejecutor.isTerminated()) Thread.sleep(100);

    // Resultados
    System.out.println("Elementos estimados: " + filtro.estimarElementos());
    System.out.println("Factor de carga: " + String.format("%.2f%%", filtro.cargaActual() * 100));
    System.out.println("Tasa de falsos positivos: " + filtro.tasaFalsosPositivos());
}

Escenarios de Aplicación

Este filtro es adecuado para entornos que requieren operaciones rápidas de pertenencia con soporte para modificaciones:

• Prevención de caché negativo en sistemas distribuidos.
• Filtros de listas negras con soporte para eliminación.
• Deduplicación en procesamiento de datos a gran escala.
• Verificcaión de tareas en sistemas de concurrencia.

Consideraciones de Rendimiento

Aunque el filtro mejora funcionalidades, se debe monitorear el factor de carga y reconstruir periódicamente en escenarios de alta rotación para mantener la precisión. La concurrencia se gestiona mediante bloqueos, por lo que se recomienda limitar el número de hilos activos en entornos con restricciones de recursos.