# Linear probing

Linear probing es un esquema de programación informática para resolver colisiones en tablas hash, estructuras de datos para mantener una colección de pares clave-valor y buscar el valor asociado a una clave determinada. Fue inventado en 1954 por Gene Amdahl, Elaine M. McGraw y Arthur Samuel y analizado por primera vez en 1963 por Donald Knuth.
Junto con el sondeo cuadrático y el hashing doble, linear probing es una forma de direccionamiento abierto. En estos esquemas, cada celda de una tabla hash almacena un único par clave-valor. Cuando la función hash provoca una colisión al asignar una nueva clave a una celda de la tabla hash que ya está ocupada por otra clave, el linear probing busca en la tabla la siguiente ubicación libre más cercana e inserta allí la nueva clave. Las búsquedas se realizan de la misma manera, buscando en la tabla secuencialmente a partir de la posición dada por la función hash, hasta encontrar una celda con una clave coincidente o una celda vacía.
Como escriben Thorup y Zhang (2012), "las tablas hash son las estructuras de datos no triviales más utilizadas, y la implementación más popular en hardware estándar utiliza el linear probing, que es rápido y sencillo".El linear probing puede proporcionar un alto rendimiento debido a su buena localidad de referencia, pero es más sensible a la calidad de su función hash que otros esquemas de resolución de colisiones. Requiere un tiempo esperado constante por búsqueda, inserción o borrado cuando se implementa utilizando una función hash aleatoria, una función hash independiente de 5 o un hashing de tabulación. En la práctica, también se pueden obtener buenos resultados con otras funciones hash, como MurmurHash.

## Operaciones

El linear probing es un componente de los esquemas de direccionamiento abierto para utilizar una tabla hash para resolver el problema del diccionario. En el problema del diccionario, una estructura de datos debe mantener una colección de pares clave-valor sujeta a operaciones que insertan o borran pares de la colección o que buscan el valor asociado a una clave dada. En las soluciones de direccionamiento abierto a este problema, la estructura de datos es una matriz T (la tabla hash) cuyas celdas T[i] (cuando no están vacías) almacenan cada una un único par clave-valor. Se utiliza una función hash para asignar cada clave a la celda de T en la que debe almacenarse, normalmente codificando las claves para que las claves con valores similares no se coloquen cerca unas de otras en la tabla. Una colisión hash se produce cuando la función hash asigna una clave a una celda que ya está ocupada por una clave diferente. El linear probing es una estrategia para resolver las colisiones, colocando la nueva clave en la celda vacía más próxima.

### Búsqueda

Para buscar una clave x dada, se examinan las celdas de T, empezando por la celda de índice h(x) (donde h es la función hash) y continuando por las celdas adyacentes h(x) + 1, h(x) + 2, ..., hasta encontrar una celda vacía o una celda cuya clave almacenada sea x. Si se encuentra una celda que contiene la clave, la búsqueda devuelve el valor de esa celda. En caso contrario, si se encuentra una celda vacía, la clave no puede estar en la tabla, porque se habría colocado en esa celda con preferencia a cualquier celda posterior en la que aún no se haya buscado. En este caso, la búsqueda devuelve como resultado que la clave no está presente en el diccionario.

### Inserción

Para insertar un par clave-valor (x,v) en la tabla (posiblemente sustituyendo cualquier par existente con la misma clave), el algoritmo de inserción sigue la misma secuencia de celdas que se seguiría para una búsqueda, hasta encontrar una celda vacía o una celda cuya clave almacenada sea x. El nuevo par clave-valor se coloca entonces en esa celda.
Si la inserción hiciera que el factor de carga de la tabla (su fracción de celdas ocupadas) creciera por encima de algún umbral preestablecido, toda la tabla puede ser sustituida por una nueva tabla, más grande por un factor constante, con una nueva función hash, como en un array dinámico. Establecer este umbral cerca de cero y utilizar una tasa de crecimiento alta para el tamaño de la tabla conduce a operaciones de tabla hash más rápidas pero con un mayor uso de memoria que los valores de umbral cercanos a uno y tasas de crecimiento bajas. Una opción común sería duplicar el tamaño de la tabla cuando el factor de carga superara 1/2, haciendo que el factor de carga se mantuviera entre 1/4 y 1/2.

### Borrado

También es posible eliminar un par clave-valor del diccionario. Sin embargo, no basta con vaciar su celda. Esto afectaría a las búsquedas de otras claves que tienen un valor hash anterior a la celda vaciada, pero que están almacenadas en una posición posterior a la celda vaciada. La celda vaciada provocaría que esas búsquedas informaran incorrectamente de que la clave no está presente.
En su lugar, cuando se vacía una celda i, es necesario buscar en las siguientes celdas de la tabla hasta encontrar otra celda vacía o una clave que se pueda mover a la celda i (es decir, una clave cuyo valor hash sea igual o anterior a i). Cuando se encuentra una celda vacía, el vaciado de la celda i es seguro y el proceso de borrado termina. Pero, cuando la búsqueda encuentra una clave que puede moverse a la celda i, realiza este movimiento. Esto tiene el efecto de acelerar las búsquedas posteriores de la clave movida, pero también vacía otra celda, más adelante en el mismo bloque de celdas ocupadas. La búsqueda de una llave movida continúa por la nueva celda vaciada, de la misma manera, hasta que termina al llegar a una celda que ya estaba vacía. En este proceso de traslado de llaves a celdas anteriores, cada llave se examina una sola vez. Por lo tanto, el tiempo para completar todo el proceso es proporcional a la longitud del bloque de celdas ocupadas que contiene la clave eliminada, igualando el tiempo de ejecución de las demás operaciones de la tabla hash.
Alternativamente, es posible utilizar una estrategia de borrado perezoso en la que un par clave-valor se elimina sustituyendo el valor por un valor de bandera especial que indica una clave borrada. Sin embargo, estos valores de bandera contribuirán al factor de carga de la tabla hash. Con esta estrategia, puede ser necesario limpiar los valores de las banderas de la matriz y volver a almacenar todos los pares clave-valor restantes una vez que una fracción demasiado grande de la matriz esté ocupada por claves eliminadas.

## Propiedades

El linear probing proporciona una buena localidad de referencia, lo que hace que requiera pocos accesos a memoria no almacenada por operación. Debido a esto, para factores de carga de bajos a moderados, puede proporcionar un rendimiento muy alto. Sin embargo, en comparación con otras estrategias de direccionamiento abierto, su rendimiento se degrada más rápidamente con factores de carga altos debido a la agrupación primaria, una tendencia de una colisión a causar más colisiones cercanas.Además, conseguir un buen rendimiento con este método requiere una función hash de mayor calidad que para otros esquemas de resolución de colisiones.Cuando se utiliza con funciones hash de baja calidad que no eliminan la falta de uniformidad en la distribución de entrada, el linear probing puede ser más lento que otras estrategias de direccionamiento abierto, como el doble hashing, que sondea una secuencia de celdas cuya separación viene determinada por una segunda función hash, o el sondeo cuadrático, en el que el tamaño de cada paso varía en función de su posición dentro de la secuencia de sondeo.

## Análisis

Utilizando el linear probing, las operaciones del diccionario pueden implementarse en un tiempo esperado constante. En otras palabras, las operaciones de inserción, eliminación y búsqueda pueden implementarse en O(1), siempre que el factor de carga de la tabla hash sea una constante estrictamente inferior a uno.
Más en detalle, el tiempo de cualquier operación concreta (una búsqueda, inserción o eliminación) es proporcional a la longitud del bloque contiguo de celdas ocupadas en el que se inicia la operación. Si todas las celdas de inicio tienen la misma probabilidad, en una tabla hash con N celdas, entonces un bloque máximo de k celdas ocupadas tendrá probabilidad k/N de contener la ubicación de inicio de una búsqueda, y tardará tiempo O(k) siempre que sea la ubicación de inicio. Por tanto, el tiempo previsto para una operación puede calcularse como el producto de estos dos términos, O(k2/N), sumado sobre todos los bloques máximos de celdas contiguas de la tabla. Una suma similar de longitudes de bloque al cuadrado da el límite de tiempo esperado para una función hash aleatoria (en lugar de para una ubicación inicial aleatoria en un estado específico de la tabla hash), sumando sobre todos los bloques que podrían existir (en lugar de los que realmente existen en un estado dado de la tabla), y multiplicando el término para cada bloque potencial por la probabilidad de que el bloque esté realmente ocupado. Es decir, definiendo Bloque(i,k) como el evento de que exista un bloque contiguo máximo de celdas ocupadas de longitud k que comience en el índice i, el tiempo esperado por operación es
$E[T]=O(1)+\sum _{i=1}^{N}\sum _{k=1}^{n}O(k^{2}/N)\operatorname {Pr} [\operatorname {Block} (i,k)].$
Esta fórmula puede simplificarse sustituyendo Block(i,k) por una condición necesaria más sencilla Full(k), el caso de que al menos k elementos tengan valores hash que se encuentren dentro de un bloque de celdas de longitud k. Tras esta sustitución, el valor dentro de la suma ya no depende de i, y el factor 1/N cancela los N términos de la suma exterior. Estas simplificaciones conducen al límite
$E[T]\leq O(1)+\sum _{k=1}^{n}O(k^{2})\operatorname {Pr} [\operatorname {Full} (k)].$
1+1/(1-𝛼))logrado por otras tablas hash de direcciones abiertas, como el sondeo uniforme y el hashing doble. El agrupamiento primario también afecta a las búsquedas fallidas, ya que, al igual que las inserciones, deben viajar hasta el final de una ejecución. Algunas variaciones del linear probing son capaces de lograr mejores límites para las búsquedas fallidas y las inserciones, mediante el uso de técnicas que reducen el agrupamiento primario.
En términos del factor de carga α, el tiempo esperado para realizar una búsqueda con éxito en una clave aleatoria es O(1 + 1/(1 - α)), y el tiempo esperado para realizar una búsqueda sin éxito (o la inserción de una nueva clave) es O(1 + 1/(1 - α)2).Para factores de carga constantes, con alta probabilidad, la secuencia de sonda más larga (entre las secuencias de sonda para todas las claves almacenadas en la tabla) tiene longitud logarítmica.

## Elección de la función hash

Dado que el linear probing es especialmente sensible a los valores hash distribuidos de forma desigual, es importante combinarlo con una función hash de alta calidad que no produzca tales irregularidades.
El análisis anterior asume que el hash de cada clave es un número aleatorio independiente de los hashes de todas las demás claves. Esta suposición es poco realista para la mayoría de las aplicaciones de hashing. Sin embargo, se pueden utilizar valores hash aleatorios o pseudoaleatorios cuando se realiza el hash de objetos por su identidad en lugar de por su valor. Por ejemplo, la clase IdentityHashMap del framework de colecciones de Java lo hace mediante linear probing. Se garantiza que el valor hash que esta clase asocia a cada objeto, su identityHashCode, permanece fijo durante la vida de un objeto, pero por lo demás es arbitrario. Dado que el identityHashCode se construye sólo una vez por objeto, y no es necesario que esté relacionado con la dirección o el valor del objeto, su construcción puede implicar cálculos más lentos, como la llamada a un generador de números aleatorios o pseudoaleatorios. Por ejemplo, Java 8 utiliza un generador de números pseudoaleatorios Xorshift para construir estos valores.

## Selección de la función hash

Para la mayoría de las aplicaciones de hash, es necesario calcular la función hash para cada valor cada vez que se hace hash, en lugar de una vez cuando se crea su objeto.En tales aplicaciones, los números aleatorios o pseudoaleatorios no pueden ser utilizados como valores hash, porque entonces diferentes objetos con el mismo valor tendrían diferentes hashes. Y las funciones hash criptográficas (que están diseñadas para ser computacionalmente indistinguibles de las funciones verdaderamente aleatorias) suelen ser demasiado lentas para ser utilizadas en tablas hash. En su lugar, se han ideado otros métodos para construir funciones hash. Estos métodos calculan la función hash rápidamente, y se puede demostrar que funcionan bien con el linear probing. En concreto, el linear probing se ha analizado desde el marco del hashing independiente de k, una clase de funciones hash que se inicializan a partir de una pequeña semilla aleatoria y que tienen la misma probabilidad de asignar cualquier k-tupla de claves distintas a cualquier k-tupla de índices. El parámetro k puede considerarse una medida de la calidad de la función hash: cuanto mayor sea k, más tiempo se tardará en calcular la función hash, pero se comportará de forma más similar a las funciones completamente aleatorias. Para el linear probing, 5-independencia es suficiente para garantizar un tiempo esperado constante por operación,mientras que algunas funciones hash 4-independientes funcionan mal, tardando hasta un tiempo logarítmico por operación.
En concreto, el linear probing se ha analizado desde el marco del hashing independiente de k, una clase de funciones hash que se inicializan a partir de una pequeña semilla aleatoria y que tienen la misma probabilidad de asignar cualquier k-tupla de claves distintas a cualquier k-tupla de índices. El parámetro k puede considerarse una medida de la calidad de la función hash: cuanto mayor sea k, más tiempo se tardará en calcular la función hash, pero se comportará de forma más similar a las funciones completamente aleatorias. Para el linear probing, la 5-independencia es suficiente para garantizar un tiempo esperado constante por operación, mientras que algunas funciones hash 4-independientes funcionan mal, tardando hasta un tiempo logarítmico por operación.
Otro método para construir funciones hash de alta calidad y velocidad práctica es el hashing de tabulación. En este método, el valor hash de una clave se calcula utilizando cada byte de la clave como un índice en una tabla de números aleatorios (con una tabla diferente para cada posición de byte). A continuación, los números de esas celdas de la tabla se combinan mediante una operación exclusiva o en sentido de los bits. Las funciones hash construidas de este modo sólo son 3-independientes. Tanto el hashing de tabulación como los métodos estándar para generar funciones hash 5-independientes están limitados a claves que tienen un número fijo de bits. Para manejar cadenas u otros tipos de claves de longitud variable, es posible componer una técnica hash universal más sencilla que mapee las claves a valores intermedios y una función hash de mayor calidad (independiente de 5 o de tabulación) que mapee los valores intermedios a índices de tablas hash.
En una comparación experimental, Richter et al. descubrieron que la familia de funciones hash Multiply-Shift (definida como
ℎ𝑧(𝑥)=(𝑥⋅𝑧mod2𝑤)÷2𝑤-𝑑) era "la función hash más rápida cuando se integraba con todos los esquemas de hashing, es decir, producía los rendimientos más altos y también de buena calidad", mientras que el hashing de tabulación producía "el rendimiento más bajo". Señalan que cada consulta de la tabla requiere varios ciclos, siendo más cara que las simples operaciones aritméticas. También encontraron que MurmurHash era superior al hashing de tabulación: "Estudiando los resultados proporcionados por Mult y Murmur, pensamos que la compensación por tabulación (...) es menos atractiva en la práctica".

## Historia

La idea de una matriz asociativa que permite acceder a los datos por su valor en lugar de por su dirección se remonta a mediados de los años 40 en los trabajos de Konrad Zuse y Vannevar Bush,pero las tablas hash no se describieron hasta 1953, en un memorándum de IBM de Hans Peter Luhn. Luhn utilizó un método de resolución de colisiones diferente, el encadenamiento, en lugar del linear probing.
Knuth (1963) resume la historia temprana del linear probing. Fue el primer método de direccionamiento abierto, y originalmente era sinónimo de direccionamiento abierto. Según Knuth, fue utilizado por primera vez por Gene Amdahl, Elaine M. McGraw (de soltera Boehme) y Arthur Samuel en 1954, en un programa ensamblador para el ordenador IBM 701.La primera descripción publicada del linear probing es de Peterson (1957), que también atribuye el mérito a Samuel, Amdahl y Boehme, pero añade que "el sistema es tan natural que es muy probable que haya sido concebido independientemente por otros antes o después"Otra publicación temprana de este método fue del investigador soviético Andrey Ershov, en 1958.
El primer análisis teórico del linear probing, mostrando que toma un tiempo esperado constante por operación con funciones hash aleatorias, fue dado por Knuth Sedgewick llama al trabajo de Knuth "un hito en el análisis de algoritmos"Desarrollos posteriores significativos incluyen un análisis más detallado de la distribución de probabilidad del tiempo de ejecución, y la prueba de que el linear probing se ejecuta en tiempo constante por operación con funciones hash prácticamente utilizables en lugar de con las funciones aleatorias idealizadas asumidas por análisis anteriores.