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.​