Smiulación de Tablas Hash con Resolución de Colisiones

Las tablas hash son estructuras de datos eficientes para operaciones de inserción y búsqueda rápidas. Utilizan una función hash para mapear datos a un arreglo de tamaño fijo, pero pueden surgir colisiones cuando diferentes elementos se asignan al mismo índice. Este artículo describe dos métodos para resolver colisiones: encadenamiento y direccionamiento abierto, con implementaciones en C++.

Función Hash y Colisiones

La función hash transforma datos de rango amplio a un índice en el arreglo. Un enfoque común es usar la operación módulo: k = (x % T + T) % T, donde T es el tamaño del arreglo. Elegir T como un número primo alejado de potencias de 2 (por ejemplo, 100003 o 200003) reduce la probabilidad de colisiones.

Método 1: Encadenamiento

En el encadenamiento, cada posición del arreglo almacena una lista enlazada. Los elementos con el mismo valor hash se insertan en la lista correspondiente.

Principios clave:

• Inicializar el arreglo tabla con -1 para indicar listas vacías.
• Durante la inserción, calcular el índice hash y añadir el elemento al inicio de la lista.
• Para búsqueda, recorrer la lista hasta encontrar el elemento o llegar al final.

Implementación en C++:

#include <iostream>
#include <cstring>
using namespace std;

const int TAM = 100003; // Tamaño primo
int n;
int valores[TAM], sig[TAM], actual; // Almacena valores y siguientes índices
int tabla[TAM]; // Arreglo de tabla hash

void agregar(int x) {
    int idx = (x % TAM + TAM) % TAM;
    valores[actual] = x;
    sig[actual] = tabla[idx];
    tabla[idx] = actual;
    actual++;
}

bool buscar(int x) {
    int idx = (x % TAM + TAM) % TAM;
    for (int i = tabla[idx]; i != -1; i = sig[i]) {
        if (valores[i] == x) return true;
    }
    return false;
}

int main() {
    scanf("%d", &n);
    memset(tabla, -1, sizeof(tabla));
    char op[2];
    int x;
    while (n--) {
        scanf("%s%d", op, &x);
        if (op[0] == 'I') agregar(x);
        else {
            if (buscar(x)) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

Explicación: La inicialización con memset establece todos los elementos de tabla a -1. La inserción tiene complejidad O(1), y la búsqueda promedio es O(1), pero puede ser O(n) en el peor caso.

Método 2: Direccionamiento Abierto

El direccionamiento abierto maneja colisiones mediante sondeo lineal. El arreglo debe ser 2-3 veces el número de elementos, y se busca la siguiente posición vacía en caso de colisión.

Principios clave:

• Inicializar el arreglo con un valor nulo, como 0x3f3f3f3f.
• Al insertar, si la posición está ocupada, avanzar hasta encontrar un espacio libre.
• La búsqueda sigue un proceso similar: recorrer hasta encontrar el elemento o un espacio nulo.

Implemetnación en C++:

#include <iostream>
#include <cstring>
using namespace std;

const int TAM = 200003; // Tamaño ajustado
const int VACIO = 0x3f3f3f3f; // Marcador nulo
int n;
int tabla[TAM]; // Arreglo de tabla hash

void insertar(int x) {
    int pos = (x % TAM + TAM) % TAM;
    while (tabla[pos] != VACIO) {
        pos++;
        if (pos == TAM) pos = 0; // Envolver al inicio
    }
    tabla[pos] = x;
}

int encontrar(int x) {
    int pos = (x % TAM + TAM) % TAM;
    while (tabla[pos] != VACIO && tabla[pos] != x) {
        pos++;
        if (pos == TAM) pos = 0;
    }
    return pos;
}

int main() {
    scanf("%d", &n);
    memset(tabla, 0x3f, sizeof(tabla));
    char op[2];
    int x;
    while (n--) {
        scanf("%s%d", op, &x);
        if (op[0] == 'I') insertar(x);
        else {
            int indice = encontrar(x);
            if (tabla[indice] == x) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

Explicación: La inicialización con memset establece todos los valores a VACIO. La inserción y búsqueda tienen complejidad promedio O(1), pero pueden requerir sondeo extenso en colisiones frecuentes.

Comparación de Métodos

Encadenamiento: Usa menos espacio cuando hay pocas colisiones, pero requiere punteros adicionales. Implementación sencilla.

Direccionamiento Abierto: Requiere un arreglo más grande, pero ofrece mejor rendimiento en acceso directo. Ideal para datos estáticos.

Ambos métodos logran complejidad promedio O(1) para inserción y búsqueda. La elección depende de las restricciones de memoria y características de los datos.

Hashing de Cadenas para Comparación Rápida de Subcadenas

En procesamiento de cadenas, comparar subcadenas directamente tiene complejidad O(n) por operación. El hashing de cadenas permite comparaciones en O(1) mediante preprocesamiento, usando un enfoque polinomial.

Principio del Algoritmo

Tratar la cadena como un número en base P (un primo, como 131). Calcular hashes de prefijo y usarlos para derivar hashes de subcadenas.

Pasos clave:

• Precomputar un arreglo de hashes de prefijo pref[].
• Precomputar un arreglo de potencias pot[] para la base P.
• Obtener el hash de una subcadena [l, r] con la fórmula: hash(l, r) = pref[r] - pref[l-1] * pot[r-l+1].

Detalles técnicos:

• Elegir P mayor que el tamaño del alfabeto (por ejemplo, 131 para ASCII).
• Usar unsigned long long para manejar desbordamiento natural módulo 2^64.
• Mapear caracteres directamente a sus valores ASCII, evitando ceros para prevenir ambigüedades.

Implementación en C++

#include <iostream>
using namespace std;

typedef unsigned long long ULL;
const int MAX_LEN = 1e5 + 10, BASE = 131; // Base polinomial

int n, m;
char cadena[MAX_LEN];
ULL pref[MAX_LEN], pot[MAX_LEN]; // Arrays de prefijos y potencias

ULL obtener_hash(int l, int r) {
    return pref[r] - pref[l - 1] * pot[r - l + 1];
}

int main() {
    scanf("%d%d%s", &n, &m, cadena + 1);
    pot[0] = 1;
    for (int i = 1; i <= n; i++) {
        pot[i] = pot[i - 1] * BASE;
        pref[i] = pref[i - 1] * BASE + cadena[i];
    }
    while (m--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        ULL h1 = obtener_hash(l1, r1);
        ULL h2 = obtener_hash(l2, r2);
        puts(h1 == h2 ? "Yes" : "No");
    }
    return 0;
}

Análisis de Complejidad

Tiempo: Preprocesamiento O(n), consulta O(1) por subcadena.

Espacio: O(n) para almacenar los arreglos.

Ejemplo de Uso

Entrada:

8 3
ABCDABC
1 3 6 8
1 2 3 4
1 3 2 4

Salida:

Yes  // "ABC" vs "ABC"
No   // "AB" vs "CD"
No   // "ABC" vs "BCD"

Aplicaciones Comunes

• Algoritmos de coincidencia de cadenas como Rabin-Karp.
• Encontrar subcadenas palindrómicas o comunes.
• Optimización de consultas repetidas en procesamiento de texto.

Nota: Aunque la probabilidad de colisión es extremadamente baja (aproximadamente 1/2^64), en escenarios críticos se puede usar hashing doble para mayor seguridad.