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.^[3]​^[4]​

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.^[3]​^[4]​

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.^[3]​^[4]​

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.^[5]​

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.^[3]​

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.^[3]​^[4]​

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.^[3]​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.^[6]​ 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.^[7]​

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.^[8]​

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

${\displaystyle 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

${\displaystyle 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.^[3]​ 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.^[4]​ 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.^[4]​^[9]​

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).^[10]​ 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.^[11]​

Dado que el linear probing es especialmente sensible a los valores hash distribuidos de forma desigual,^[12]​^[10]​ 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.^[10]​ 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.^[10]​ 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.^[13]​

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.^[7]​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.^[14]​ 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.^[15]​ 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.^[16]​

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,^[17]​ mientras que algunas funciones hash 4-independientes funcionan mal, tardando hasta un tiempo logarítmico por operación.^[6]​

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.^[4]​^[18]​ 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.^[1]​^[19]​

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".^[20]​ 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".

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,^[21]​ 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.^[22]​

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.^[8]​La primera descripción publicada del linear probing es de Peterson (1957),^[8]​ 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"^[23]​ Otra publicación temprana de este método fue del investigador soviético Andrey Ershov, en 1958.^[24]​

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^[8]​ Sedgewick llama al trabajo de Knuth "un hito en el análisis de algoritmos"^[10]​Desarrollos posteriores significativos incluyen un análisis más detallado de la distribución de probabilidad del tiempo de ejecución,^[25]​^[26]​ 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.^[18]​^[19]​

1. ↑ ^{a b} 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
2. ↑ 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
3. ↑ ^{a b c d e f g} Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 6.3.3: Linear Probing", Algorithm Design and Applications, Wiley, pp. 200–203
4. ↑ ^{a b c d e f g} Morin, 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
5. ↑ Sedgewick, Robert; Wayne, Kevin (2011), Algorithms (4th ed.), Addison-Wesley Professional, p. 471, ISBN 9780321573513 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.
6. ↑ ^{a b} 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
7. ↑ ^{a b} Heileman, Gregory L.; Luo, Wenbin (2005), "How caching affects hashing" (PDF), Seventh Workshop on Algorithm Engineering and Experiments (ALENEX 2005), pp. 141–154
8. ↑ ^{a b c d} Knuth, Donald (1963), Notes on "Open" Addressing, archivado del original el 03-03-2016
9. ↑ Eppstein, David (October 13, 2011), "Linear probing made easy", 0xDE
10. ↑ ^{a b c d e} Sedgewick, Robert (2003), "Section 14.3: Linear Probing", Algorithms in Java, Parts 1–4: Fundamentals, Data Structures, Sorting, Searching (3rd ed.), Addison Wesley, pp. 615–620, ISBN 9780321623973
11. ↑ Pittel, B. (1987), "Linear probing: the probable largest search time grows logarithmically with the number of records", Journal of Algorithms, 8 (2): 236–249, doi:10.1016/0196-6774(87)90040-X, MR 0890874
12. ↑ Cormen, Thomas H.; Leiserson, Charles Eric; Rivest, Ronald Linn; Stein, Clifford (2009). Introduction to algorithms (3rd ed.). Cambridge, Massachusetts London, England: MIT Press. ISBN 978-0-262-53305-8.
13. ↑ Bender, Michael A.; Kuszmaul, Bradley C.; Kuszmaul, William (2022). "Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering". 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 1171–1182. doi:10.1109/focs52979.2021.00115. ISBN ISBN 978-1-6654-2055-6. S2CID  260502788.
14. ↑ "IdentityHashMap", Java SE 7 Documentation, Oracle, retrieved 2016-01-15
15. ↑ Friesen, Jeff (2012), Beginning Java 7, Expert's voice in Java, Apress, p. 376, ISBN 9781430239109
16. ↑ Kabutz, Heinz M. (September 9, 2014), "Identity Crisis", The Java Specialists' Newsletter, 222
17. ↑ Pagh, Anna; Pagh, Rasmus; Ružić, Milan (2009), "Linear probing with constant independence", SIAM Journal on Computing, 39 (3): 1107–1120, arXiv:cs/0612055, doi:10.1137/070702278, MR 2538852
18. ↑ ^{a b} Pătraşcu, Mihai; Thorup, Mikkel (2011), "The power of simple tabulation hashing", Proceedings of the 43rd annual ACM Symposium on Theory of Computing (STOC '11), pp. 1–10, arXiv:1011.5200, doi:10.1145/1993636.1993638, S2CID 195776653
19. ↑ ^{a b} Thorup, Mikkel (2009), "String hashing for linear probing", Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA: SIAM, pp. 655–664, CiteSeerX 10.1.1.215.4253, doi:10.1137/1.9781611973068.72, MR 2809270
20. ↑ Weiss, Mark Allen (2014), "Chapter 3: Data Structures", en Gonzalez, Teofilo; Diaz-Herrera, Jorge; Tucker, Allen (eds.), Computing Handbook, vol. 1 (3rd ed.), CRC Press, p. 3-11, ISBN 9781439898536.
21. ↑ Parhami, Behrooz (2006), Introduction to Parallel Processing: Algorithms and Architectures, Series in Computer Science, Springer, 4.1 Development of early models, p. 67, ISBN 9780306469640
22. ↑ Morin, Pat (2004), "Hash tables", en Mehta, Dinesh P.; Sahni, Sartaj (eds.), Handbook of Data Structures and Applications, Chapman & Hall / CRC, p. 9-15, ISBN 9781420035179.
23. ↑ Peterson, W. W. (April 1957), "Addressing for random-access storage", IBM Journal of Research and Development, 1 (2), Riverton, NJ, USA: IBM Corp.: 130–146, doi:10.1147/rd.12.0130
24. ↑ Ershov, A. P. (1958), "On Programming of Arithmetic Operations", Communications of the ACM, 1 (8): 3-6, doi:10.1145/368892.368907, S2CID 15986378. Traducido de Doklady AN USSR 118 (3): 427-430, 1958, por Morris D. Friedman. El sondeo lineal se describe como algoritmo A2.
25. ↑ Flajolet, P.; Poblete, P.; Viola, A. (1998), "On the analysis of linear probing hashing" (PDF), Algorithmica, 22 (4): 490–515, doi:10.1007/PL00009236, MR 1701625, S2CID 5436036
26. ↑ Knuth, D. E. (1998), "Linear probing and graphs", Algorithmica, 22 (4): 561–568, arXiv:cs/9801103, doi:10.1007/PL00009240, MR 1701629, S2CID 12254909