miniaturadeimagen|La colisión entre John Smith y Sandra Dee (ambos con hashing en la celda 873) se resuelve colocando a Sandra Dee en la siguiente posición libre, la celda 874. 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".Thorup, Mikkel; Zhang, Yin (2012), "Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation", SIAM Journal on Computing, 41 (2): 293–331, doi:10.1137/100800774, MR 2914329 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.Richter, Stefan; Alvarez, Victor; Dittrich, Jens (2015), "A seven-dimensional analysis of hashing methods and its implications on query processing" (PDF), Proceedings of the VLDB Endowment, 9 (3): 293–331, doi:10.14778/2850583.2850585
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.Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 6.3.3: Linear Probing", Algorithm Design and Applications, Wiley, pp. 200–203Morin, Pat (February 22, 2014), "Section 5.2: LinearHashTable: Linear Probing", Open Data Structures (in pseudocode) (0.1Gβ ed.), pp. 108–116, retrieved 2016-01-15
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.Sedgewick, Robert; Wayne, Kevin (2011), Algorithms (4th ed.), Addison-Wesley Professional, p. 471, Sedgewick y Wayne también reducen a la mitad el tamaño de la tabla cuando una eliminación haría que el factor de carga fuera demasiado bajo, lo que les lleva a utilizar un rango más amplio [1/8,1/2] en los posibles valores del factor de carga.
Borrado miniaturadeimagen|Cuando se elimina un par clave-valor, puede ser necesario desplazar otro par hacia atrás en su celda, para evitar que las búsquedas de la clave desplazada encuentren una celda vacía. 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.Pătraşcu, Mihai; Thorup, Mikkel (2010), "On the k-independence required by linear probing and minwise independence" (PDF), Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, Julio6-10, 2010, Proceedings, Part I, Lecture Notes in Computer Science, vol. 6198, Springer, pp. 715-726, arXiv:1302.5127, doi:10.1007/978-3-642-14165-2_60 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.Heileman, Gregory L.; Luo, Wenbin (2005), "How caching affects hashing" (PDF), Seventh Workshop on Algorithm Engineering and Experiments (ALENEX 2005), pp. 141–154
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.Knuth, Donald (1963), Notes on "Open" Addressing, archivado del original el 03-03-2016
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
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