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

1. ↑ 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