Entrevista técnica de programación: ¿Cómo implementar Robin Hood Hashing?

Prompt y alcance

Implementa una tabla hash de direccionamiento abierto de capacidad fija con un arreglo de m ranuras (slots), donde cada ranura almacena como máximo un par clave-valor. Admite insert(key,value), contains(key) y remove(key). Resuelve las colisiones con hashing Robin Hood; no uses encadenamiento ni tombstones. Para centrarse en el algoritmo principal, una tabla llena puede devolver un error en lugar de redimensionarse.

Este es un problema general de entrevista técnica de programación sobre estructuras de datos, invariantes, casos límite y complejidad. La tarea pública de Stanford CS106B pide a los estudiantes implementar una tabla Robin Hood e incluye explícitamente el intercambio por distancia de sondeo, la terminación temprana de búsqueda y la eliminación por desplazamiento hacia atrás. Una guía actual de entrevistas de ingeniería de software enumera el criterio de selección de estructuras de datos, la corrección, la complejidad y el manejo de casos límite como señales clave en la evaluación de código.

Qué evalúa el entrevistador

• ¿Puedes almacenar el bucket de origen (home bucket) y el PSL (longitud de la secuencia de sondeo) de cada elemento?
• ¿Puedes explicar por qué “la clave más pobre tiene prioridad”: cuando el PSL entrante es mayor, intercambiar con la clave residente que está más cerca de su origen?
• ¿Puedes usar la monotonicidad del PSL para detener tempranamente una búsqueda fallida en lugar de escanear todo el arreglo?
• ¿Puedes eliminar elementos sin tombstones manteniendo accesible cada clave dentro de un clúster de sondeo?
• ¿Puedes enunciar los costos promedio y en el peor caso y elegir una política para escenarios de alta carga?

Una respuesta común escribe un sondeo lineal pero pasa por alto que los huecos de eliminación truncan las búsquedas posteriores. Una respuesta sólida convierte tanto la “ranura vacía” como el “PSL residente menor que el PSL objetivo” en condiciones de parada demostradas.

Aclaraciones previas a responder

1. ¿La capacidad es fija? Con capacidad fija, el fallo de inserción es un resultado explícito; con redimensionamiento, un umbral de factor de carga dispara una reconstrucción.
2. ¿Se permiten claves duplicadas? Asume que un duplicado actualiza su valor en lugar de agregar una segunda ranura; un multimap requeriría una API y un contrato de eliminación diferentes.
3. ¿El hash es estable y las claves son copiables? Un hash debe ser estable durante una operación. Guardar en caché el bucket de origen puede evitar trabajo repetido pero consume memoria por ranura.
4. ¿Deben permanecer estables los iteradores o las referencias? Los intercambios y los desplazamientos hacia atrás mueven elementos, por lo que no se prometen direcciones estables. Usa indirección si los llamadores necesitan identificadores estables.
5. ¿Está la concurrencia dentro del alcance? Esto es de un solo hilo. Una versión concurrente necesita bloqueos, segmentación (striping) o un protocolo sin bloqueos; la implementación ordinaria no es segura para subprocesos (thread-safe).

Estructura de respuesta en 30 segundos

“Almaceno clave, valor, bucket de origen y PSL en cada ranura ocupada. La inserción realiza un sondeo lineal desde el origen; cuando el PSL entrante supera al PSL residente, los intercambio para que el elemento que ha viajado más lejos tenga prioridad, y luego continúo ubicando el elemento desplazado. Una búsqueda puede fallar ante una ranura vacía o cuando el PSL residente es inferior al PSL objetivo, ya que las entradas posteriores no pueden retroceder a una distancia menor. La eliminación desplaza las entradas posteriores hacia atrás hasta encontrar una ranura vacía o una entrada con PSL cero, decrementando el PSL en cada movimiento para no cortar ninguna ruta de búsqueda. Las operaciones esperadas son cercanas a O(1), el peor caso es O(m) y el espacio es O(m).”

Respuesta detallada paso a paso

1. Modelo de ranuras e invariantes

Cada ranura ocupada almacena (key, value, home, psl). En un anillo de m ranuras, psl = (index - home + m) % m. Mantén tres invariantes:

• home es el origen hash fijo para la clave.
• Avanzar psl pasos hacia adelante desde home alcanza el índice actual.
• Dentro de un clúster de sondeo contiguo, los valores de PSL ocupados nunca disminuyen; una ranura vacía finaliza el clúster.

El tercer invariante surge de dar prioridad al PSL mayor en la inserción. Permite que la búsqueda compare el PSL objetivo con el PSL residente en lugar de examinar cada ranura posterior.

2. El cuello de botella del sondeo lineal

El sondeo lineal simple avanza desde el origen hasta encontrar una ranura vacía. Con alta carga, una clave temprana puede ocupar una ranura cercana a su origen mientras que una clave posterior que ya ha sondeado lejos continúa avanzando; la varianza de la longitud de sondeo infla entonces la latencia de cola. Robin Hood hashing mantiene el diseño compacto en arreglo, pero da prioridad en las colisiones a la clave que ha viajado más lejos.

3. Inserción con Robin Hood

Pseudocódigo:

insert(key, value):
    item = (key, value, home=hash(key), psl=0)
    for step in 0 .. m-1:
        i = (item.home + item.psl) mod m
        if table[i] is empty:
            table[i] = item
            return success
        if table[i].key == key:
            table[i].value = value
            return updated
        if table[i].psl < item.psl:
            swap(table[i], item)
        item.psl += 1
    return full

Después de un intercambio, item es la entrada desplazada. Su PSL ya describe la posición de sondeo actual, por lo que la siguiente iteración lo incrementa en uno. Mantén las ranuras vacías diferenciadas de una entrada real cuyo PSL sea cero; de lo contrario, los límites de inserción y eliminación se vuelven ambiguos.

4. Búsqueda y terminación temprana

La búsqueda comienza en el origen objetivo y rastrea el PSL objetivo:

contains(key):
    home = hash(key)
    for psl in 0 .. m-1:
        i = (home + psl) mod m
        if table[i] is empty:
            return false
        if table[i].psl < psl:
            return false
        if table[i].key == key:
            return true
    return false

Una ranura vacía finaliza el clúster. Un PSL residente menor que el objetivo significa que las ranuras posteriores no pueden contener el objetivo, porque el PSL del clúster no disminuye. La tarea de Stanford trata esta parada temprana como una diferencia fundamental respecto al sondeo lineal ordinario.

5. Eliminación por desplazamiento hacia atrás (backward shift)

No limpies una ranura de inmediato: una clave posterior puede haberla cruzado durante la resolución de colisiones y la búsqueda se detendría incorrectamente en el hueco. Los tombstones tampoco están permitidos y alargarían los sondeos con el tiempo.

remove(key):
    i = find_index_or_not_found(key)
    if i is not found:
        return false
    j = (i + 1) mod m
    while table[j] is not empty and table[j].psl > 0:
        table[i] = table[j]
        table[i].psl -= 1
        i = j
        j = (j + 1) mod m
    table[i] = empty
    return true

Detén el desplazamiento ante una ranura vacía o una entrada con PSL cero. La primera finaliza el clúster; la segunda está en su origen, por lo que limpiar la ranura anterior no puede cortar su ruta de búsqueda. Cada movimiento decrementa el PSL y restaura el invariante de distancia.

6. Complejidad y política ante alta carga

Con un hash uniforme y un factor de carga α cómodamente por debajo de uno, los sondeos esperados para inserción, búsqueda y eliminación son de escala constante. Una sola operación aún puede escanear las m ranuras, por lo que el tiempo en el peor caso es O(m) y el espacio es O(m). Robin Hood hashing mejora principalmente la distribución y la varianza de la longitud de sondeo; no elimina el peor caso del direccionamiento abierto. El análisis citado estudia la varianza acotada en modelos de alta carga, pero el código de producción aún necesita un umbral de carga.

Cuando α se aproxima a ese umbral, reconstruye con una capacidad mayor en lugar de confiar en el O(1) esperado. Si la capacidad debe permanecer fija, trata full como un resultado de negocio normal y monitorea la tasa de fallos, el PSL medio, los sondeos en P99 y la longitud de desplazamiento en eliminaciones.

7. Contraejemplos y pruebas

• Inserción y búsqueda en tabla vacía: la ranura de origen se llena directamente y una clave inexistente se detiene en la primera ranura vacía.
• Clave duplicada: actualizar un valor no incrementa el conteo de elementos.
• Desbordamiento circular (wraparound): elige un origen cerca del final y verifica (index - home + m) % m.
• Cadena de intercambios: construye claves en colisión y verifica que una sola inserción pueda desplazar y colocar cada elemento.
• Eliminar la cabeza, el centro y la cola de un clúster: todas las claves restantes siguen siendo localizables.
• Eliminar una entrada en su origen: detenerse cuando el sucesor tenga PSL cero, evitando movimientos entre clústeres diferentes.
• Tabla llena: la (m+1)-ésima clave distinta devuelve un error en lugar de ciclarse indefinidamente.
• Hash adverso: mapea muchas claves al mismo origen, verifica la corrección y expón sondeos O(m) en las métricas.

Ejemplo de respuesta de alta calidad

“Utilizaría una tabla de direccionamiento abierto Robin Hood de capacidad fija, almacenando la clave, el valor y el PSL en cada ranura ocupada. La inserción sondea linealmente desde el origen. Si la entrada entrante ha viajado más lejos que la entrada residente, las intercambio y continúo colocando la entrada desplazada. Esto mantiene el PSL no decreciente dentro de un clúster de sondeo.

La búsqueda aprovecha ese invariante: una ranura vacía indica fallo, y un PSL residente menor que el PSL objetivo también indica fallo porque las entradas posteriores no pueden volver a una distancia menor. La eliminación no puede dejar un hueco, así que desplazo las entradas hacia atrás mientras su PSL sea positivo y decremento cada PSL; una ranura vacía o una entrada con PSL cero finaliza el desplazamiento. El tiempo esperado es cercano a O(1) y el peor caso es O(m), por lo que el factor de carga, los sondeos en P99 y la longitud de desplazamiento deciden si redimensionar o rechazar la inserción. Dado que los desplazamientos mueven elementos, no prometo iteradores ni direcciones estables.”

Errores comunes

• Error → mantener siempre al residente anterior ante una colisión → las entradas posteriores acumulan sondeos largos → intercambiar cuando el PSL entrante sea mayor.
• Error → detener la búsqueda únicamente ante ranuras vacías → perder la optimización de PSL → detenerse también cuando el PSL residente sea menor que el objetivo.
• Error → limpiar una ranura eliminada inmediatamente → el hueco trunca las rutas de sondeo posteriores → usar desplazamiento hacia atrás y decrementar el PSL.
• Error → detener el desplazamiento ante cualquier entrada ocupada → dejar claves inalcanzables o mover elementos entre clústeres distintos → desplazar únicamente mientras el PSL del clúster contiguo sea positivo.
• Error → escribir el O(1) esperado como O(1) en el peor caso → los malos hashes y la alta carga lo invalidan → enunciar el peor caso O(m) y aplicar un umbral de carga.
• Error → prometer referencias estables → los intercambios y las eliminaciones mueven entradas → devolver identificadores (handles), usar indirección o descartar la garantía de dirección fija.

Preguntas de seguimiento y respuestas

¿Cuándo debería reconstruirse una tabla de crecimiento dinámico?

Disparar la reconstrucción tanto por factor de carga como por latencia de sondeo de cola, como un α configurado o un presupuesto de sondeo P99. Recalcula cada origen y PSL durante la reconstrucción; copiar las ranuras directamente es incorrecto porque el módulo del arreglo cambia. Un bloqueo de escritura, una migración de doble tabla o una reconstrucción en segundo plano pueden servir a diferentes objetivos de disponibilidad, pero define primero la política de consistencia y pausas.

¿Por qué evitar los tombstones y puede el desplazamiento hacia atrás costar demasiado?

Un tombstone hace que la eliminación sea O(1), pero alarga permanentemente las búsquedas hasta una reconstrucción. El desplazamiento hacia atrás concentra el trabajo en las eliminaciones y mantiene los clústeres compactos. Si dominan las eliminaciones y las lecturas son raras, los tombstones más una reconstrucción periódica pueden resultar mejores; si la latencia de lectura importa, es preferible el desplazamiento y monitorear la longitud de los movimientos.

¿Cómo manejarías lectores y escritores concurrentes?

Esta implementación es de un solo hilo. La versión concurrente más simple utiliza un bloqueo de lectura-escritura; los intercambios y desplazamientos deben formar una única sección crítica de escritura para que los lectores nunca vean un clúster a medio mover. Para un mayor rendimiento se pueden usar bloqueos segmentados (striped locks) o instantáneas inmutables. Un diseño lock-free necesita palabras de versión, ordenamiento de memoria y recolección de memoria; los punteros de ranura atómicos por sí solos son insuficientes.

¿Robin Hood hace que la búsqueda promedio sea en tiempo constante?

Bajo los modelos habituales de hash uniforme, el costo esperado del direccionamiento abierto depende del factor de carga. Robin Hood reduce principalmente la varianza de la longitud de sondeo y la dispersión en la cola. El costo promedio sigue aumentando con alta carga y el peor caso puede escanear toda la tabla, por lo que las mejoras de varianza no reemplazan el control de carga y las pruebas de rendimiento (benchmarks).