Sondeo lineal

Método de programación informática para realizar hashes

La colisión entre John Smith y Sandra Dee (ambos en la celda 873) se resuelve colocando a Sandra Dee en la siguiente ubicación libre, la celda 874.

El sondeo lineal 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 con una clave dada. 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 hash doble , el sondeo lineal 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 sondeo lineal 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 comenzando en 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 sondeo lineal, que es rápido y simple". ^[1] El sondeo lineal 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 algunos otros esquemas de resolución de colisiones. Toma un tiempo esperado constante por búsqueda, inserción o eliminación cuando se implementa utilizando una función hash aleatoria, una función hash independiente de 5 o hash de tabulación . También se pueden lograr buenos resultados en la práctica con otras funciones hash como MurmurHash . ^[2]

Operaciones

El sondeo lineal es un componente de los esquemas de direccionamiento abierto para usar 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 sujetos a operaciones que insertan o eliminan pares de la colección o que buscan el valor asociado con una clave dada. En las soluciones de direccionamiento abierto para 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 solo par clave-valor. Se utiliza una función hash para mapear cada clave en la celda de T donde se debe almacenar esa clave, típicamente mezclando las claves para que las claves con valores similares no se coloquen cerca unas de otras en la tabla. Una colisión hash ocurre cuando la función hash mapea una clave en una celda que ya está ocupada por una clave diferente. El sondeo lineal es una estrategia para resolver colisiones, colocando la nueva clave en la celda vacía siguiente más cercana. ^{[3] [4]}

Buscar

Para buscar una clave dada x , se examinan las celdas de T , comenzando con la celda en el índice h ( x ) (donde h es la función hash) y continuando con 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. De lo contrario, si se encuentra una celda vacía, la clave no puede estar en la tabla, porque se habría colocado en esa celda en preferencia a cualquier celda posterior 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]}

Inserción

Para insertar un par clave-valor ( x , v ) en la tabla (posiblemente reemplazando 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 causara que el factor de carga de la tabla (su fracción de celdas ocupadas) crezca por encima de un umbral preestablecido, toda la tabla puede ser reemplazada por una nueva tabla, más grande por un factor constante, con una nueva función hash, como en una matriz dinámica . Establecer este umbral cerca de cero y usar una alta tasa de crecimiento para el tamaño de la tabla conduce a operaciones de tabla hash más rápidas pero 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 exceda 1/2, lo que hace que el factor de carga se mantenga entre 1/4 y 1/2. ^[5]

Supresión

Cuando se elimina un par clave-valor, puede ser necesario mover otro par hacia atrás, dentro de su celda, para evitar que las búsquedas de la clave movida encuentren una celda vacía.

También es posible eliminar un par clave-valor del diccionario. Sin embargo, no es suficiente hacerlo simplemente vaciando su celda. Esto afectaría las búsquedas de otras claves que tengan un valor hash anterior a la celda vaciada, pero que estén almacenadas en una posición posterior a la de la celda vaciada. La celda vaciada haría que esas búsquedas informaran incorrectamente que la clave no está presente.

En cambio, cuando se vacía una celda i , es necesario buscar hacia adelante a través de las celdas siguientes 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, entonces vaciar la celda i es seguro y el proceso de eliminación termina. Pero, cuando la búsqueda encuentra una clave que se puede mover 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 tarde en el mismo bloque de celdas ocupadas. La búsqueda de una clave movible continúa para 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 mover claves a celdas anteriores, cada clave se examina solo una 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, coincidiendo con el tiempo de ejecución de las otras operaciones de la tabla hash. ^[3]

Como alternativa, es posible utilizar una estrategia de eliminación diferida en la que se elimina un par clave-valor reemplazando el valor por un valor de indicador especial que indica una clave eliminada. Sin embargo, estos valores de indicador contribuirán al factor de carga de la tabla hash. Con esta estrategia, puede resultar necesario limpiar los valores de indicador de la matriz y volver a hacer un hash de todos los pares clave-valor restantes una vez que una fracción demasiado grande de la matriz esté ocupada por claves eliminadas. ^{[3] [4]}

Propiedades

El sondeo lineal proporciona una buena localidad de referencia , lo que hace que requiera pocos accesos a memoria no almacenada en caché por operación. Debido a esto, para factores de carga bajos a moderados, puede proporcionar un rendimiento muy alto. Sin embargo, en comparación con algunas otras estrategias de direccionamiento abierto, su rendimiento se degrada más rápidamente en factores de carga altos debido a la agrupación primaria , una tendencia a que una colisión cause más colisiones cercanas. ^[3] Además, lograr un buen rendimiento con este método requiere una función hash de mayor calidad que para algunos otros esquemas de resolución de colisiones. ^[6] Cuando se usa con funciones hash de baja calidad que no eliminan las no uniformidades en la distribución de entrada, el sondeo lineal puede ser más lento que otras estrategias de direccionamiento abierto como el hash doble , que sondea una secuencia de celdas cuya separación está determinada por una segunda función hash, o el sondeo cuadrático , donde el tamaño de cada paso varía según su posición dentro de la secuencia de sondeo. ^[7]

Análisis

Mediante el sondeo lineal, las operaciones de diccionario se pueden implementar en un tiempo esperado constante . En otras palabras, las operaciones de inserción, eliminación y búsqueda se pueden implementar en O(1) , siempre que el factor de carga de la tabla hash sea una constante estrictamente menor que uno. ^[8]

En más detalle, el tiempo para cualquier operación particular (una búsqueda, inserción o eliminación) es proporcional a la longitud del bloque contiguo de celdas ocupadas en el que comienza 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á una probabilidad k / N de contener la ubicación de inicio de una búsqueda, y tomará tiempo O ( k ) siempre que sea la ubicación de inicio. Por lo tanto, el tiempo esperado para una operación se puede calcular como el producto de estos dos términos, O ( k ² / N ) , sumados sobre todos los bloques máximos de celdas contiguas en 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 de inicio aleatoria en un estado específico de la tabla hash), sumando 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 en el que hay un bloque contiguo máximo de celdas ocupadas de longitud k que comienzan 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 se puede simplificar reemplazando Block( i , k ) por una condición necesaria más simple Full( k ) , el evento de que al menos k elementos tengan valores hash que se encuentren dentro de un bloque de celdas de longitud k . Después de este reemplazo, el valor dentro de la suma ya no depende de i , y el factor 1/ N cancela los N términos de la suma externa. Estas simplificaciones conducen al límite

${\displaystyle E[T]\leq O(1)+\sum _{k=1}^{n}O(k^{2})\operatorname {Pr} [\operatorname {Full} (k)].}$

Pero por la forma multiplicativa del límite de Chernoff , cuando el factor de carga está acotado lejos de uno, la probabilidad de que un bloque de longitud k contenga al menos k valores hash es exponencialmente pequeña como función de k , lo que hace que esta suma esté acotada por una constante independiente de  n . ^[3] También es posible realizar el mismo análisis utilizando la aproximación de Stirling en lugar del límite de Chernoff para estimar la probabilidad de que un bloque contenga exactamente k valores hash. ^{[4] [9]}

En términos del factor de carga α , el tiempo esperado para realizar una búsqueda exitosa en una clave aleatoria es O (1 + 1/(1 − α )) , y el tiempo esperado para realizar una búsqueda fallida (o la inserción de una nueva clave) es O (1 + 1/(1 − α ) ² ) . ^[10] Para factores de carga constantes, con alta probabilidad, la secuencia de sondeo más larga (entre las secuencias de sondeo para todas las claves almacenadas en la tabla) tiene una longitud logarítmica. ^[11]

Agrupamiento primario

Las tablas hash de sondeo lineal sufren un problema conocido como agrupamiento primario , en el que los elementos se agrupan en largas ejecuciones contiguas. ^{[12] [10]} En términos del factor de carga α , la longitud esperada de la ejecución que contiene un elemento dado es . ^[10] Es por esto que las inserciones toman tiempo , a diferencia del tiempo de ejecución de logrado por otras tablas hash de dirección abierta como el sondeo uniforme y el hash doble . ^[10] El agrupamiento primario también afecta las búsquedas fallidas, ya que al igual que las inserciones, deben viajar hasta el final de una ejecución. ^[10] Algunas variaciones del sondeo lineal pueden lograr mejores límites para las búsquedas e inserciones fallidas, mediante el uso de técnicas que reducen el agrupamiento primario. ^[13] ${\displaystyle \Theta (1+1/(1-\alpha )^{2})}$ ${\displaystyle \Theta (1+1/(1-\alpha )^{2})}$ ${\displaystyle \Theta (1+1/(1-\alpha ))}$

Elección de la función hash

Debido a que el sondeo lineal es especialmente sensible a valores hash distribuidos de manera desigual, ^[7] es importante combinarlo con una función hash de alta calidad que no produzca tales irregularidades.

El análisis anterior supone que el hash de cada clave es un número aleatorio independiente de los hashes de todas las demás claves. Esta suposición no es realista para la mayoría de las aplicaciones de hash. Sin embargo, se pueden utilizar valores hash aleatorios o pseudoaleatorios cuando se hace un hash de objetos por su identidad en lugar de por su valor. Por ejemplo, esto se hace utilizando un sondeo lineal por parte de la clase IdentityHashMap del marco de colecciones de Java . ^[14] Se garantiza que el valor hash que esta clase asocia con cada objeto, su identityHashCode, permanecerá fijo durante la vida útil de un objeto, pero de lo contrario es arbitrario. ^[15] Debido a que identityHashCode se construye solo una vez por objeto y no se requiere 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. ^[16]

Para la mayoría de las aplicaciones de hash, es necesario calcular la función hash para cada valor cada vez que se aplica el hash, en lugar de una vez cuando se crea su objeto. En tales aplicaciones, los números aleatorios o pseudoaleatorios no se pueden utilizar como valores hash, porque entonces los 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. ^[17] En cambio, 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 sondeo lineal. En particular, el sondeo lineal se ha analizado desde el marco del hash k -independiente , una clase de funciones hash que se inicializan a partir de una pequeña semilla aleatoria y que tienen la misma probabilidad de mapear cualquier k -tupla de claves distintas a cualquier k -tupla de índices. El parámetro k puede considerarse como una medida de la calidad de la función hash: cuanto mayor sea k , más tiempo llevará calcular la función hash, pero se comportará de manera más similar a las funciones completamente aleatorias. Para el sondeo lineal, la independencia de 5 es suficiente para garantizar un tiempo esperado constante por operación, ^[18] mientras que algunas funciones hash de 4 independencias tienen un mal desempeño, y requieren un tiempo logarítmico por operación. ^[6]

Otro método para construir funciones hash con alta calidad y velocidad práctica es el hash de tabulación . En este método, el valor hash de una clave se calcula utilizando cada byte de la clave como índice en una tabla de números aleatorios (con una tabla diferente para cada posición de byte). Los números de esas celdas de la tabla se combinan luego mediante una operación o exclusiva bit a bit . Las funciones hash construidas de esta manera son solo 3-independientes. Sin embargo, el sondeo lineal utilizando estas funciones hash toma un tiempo esperado constante por operación. ^{[4] [19]} Tanto el hash 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 de hash universal más simple que asigne las claves a valores intermedios y una función hash de mayor calidad (5-independiente o tabulación) que asigne los valores intermedios a índices de tabla hash. ^{[1] [20]}

En una comparación experimental, Richter et al. descubrieron que la familia de funciones hash Multiply-Shift (definida como ) era "la función hash más rápida cuando se integraba con todos los esquemas hash, es decir, producía los mayores rendimientos y también de buena calidad", mientras que el hash de tabulación producía "el rendimiento más bajo". ^[2] Señalan que cada búsqueda de tabla requiere varios ciclos, siendo más costoso que las operaciones aritméticas simples. También descubrieron que MurmurHash era superior al hash de tabulación: "Al estudiar los resultados proporcionados por Mult y Murmur, creemos que la compensación por tabulación (...) es menos atractiva en la práctica". ${\displaystyle h_{z}(x)=(x\cdot z{\bmod {2}}^{w})\div 2^{w-d}}$

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 la década de 1940 en el trabajo de Konrad Zuse y Vannevar Bush , ^[21] pero las tablas hash no se describieron hasta 1953, en un memorando de IBM de Hans Peter Luhn . Luhn utilizó un método de resolución de colisiones diferente, el encadenamiento, en lugar del sondeo lineal. ^[22]

Knuth  (1963) resume la historia temprana del sondeo lineal. 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 (née Boehme) y Arthur Samuel en 1954, en un programa ensamblador para la computadora IBM 701. ^[8] La primera descripción publicada del sondeo lineal es de Peterson (1957), ^[8] quien también acredita a Samuel, Amdahl y Boehme pero agrega que "el sistema es tan natural, que muy probablemente puede haber sido concebido independientemente por otros antes o después de ese momento". ^[23] Otra publicación temprana de este método fue realizada por el investigador soviético Andrey Ershov , en 1958. ^[24]

El primer análisis teórico del sondeo lineal, que muestra que requiere un tiempo esperado constante por operación con funciones hash aleatorias, fue realizado 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 sondeo lineal se ejecuta en un 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]}

Referencias

1. Thorup, Mikkel ; Zhang, Yin (2012), "Hash 5-independiente basado en tabulación con aplicaciones al sondeo lineal y estimación del segundo momento", SIAM Journal on Computing , 41 (2): 293–331, doi :10.1137/100800774, MR  2914329
2. Richter, Stefan; Alvarez, Victor; Dittrich, Jens (2015), "Un análisis de siete dimensiones de los métodos de hash y sus implicaciones en el procesamiento de consultas" (PDF) , Actas de la Fundación VLDB , 9 (3): 293–331, doi :10.14778/2850583.2850585
3. Goodrich, Michael T .; Tamassia, Roberto (2015), "Sección 6.3.3: Sondeo lineal", Diseño de algoritmos y aplicaciones , Wiley, págs. 200-203
4. Morin, Pat (22 de febrero de 2014), "Sección 5.2: LinearHashTable: Sondeo lineal", Open Data Structures (en pseudocódigo) (0.1G β  ed.), págs. 108-116 , consultado el 15 de enero de 2016
5. Sedgewick, Robert ; Wayne, Kevin (2011), Algoritmos (4.ª ed.), Addison-Wesley Professional, pág. 471, ISBN 9780321573513Sedgewick 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 hace que utilicen un rango más amplio [1/8,1/2] en los valores posibles del factor de carga.
6. Pătraşcu, Mihai ; Thorup, Mikkel (2010), "Sobre la independencia k requerida por el sondeo lineal y la independencia minwise" (PDF) , Automata, Languages ​​and Programming , 37th International Colloquium, ICALP 2010, Burdeos, Francia, 6–10 de julio de 2010, Actas, Parte 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. Heileman, Gregory L.; Luo, Wenbin (2005), "Cómo el almacenamiento en caché afecta al hash" (PDF) , Séptimo taller sobre ingeniería de algoritmos y experimentos (ALENEX 2005) , págs. 141–154
8. Knuth, Donald (1963), Notas sobre el direccionamiento "abierto", archivado desde el original el 3 de marzo de 2016
9. Eppstein, David (13 de octubre de 2011), "El sondeo lineal simplificado", 0xDE
10. Sedgewick, Robert (2003), "Sección 14.3: Sondeo lineal", Algoritmos en Java, partes 1 a 4: Fundamentos, estructuras de datos, ordenamiento, búsqueda (3.ª ed.), Addison Wesley, págs. 615 a 620, ISBN 9780321623973
11. Pittel, B. (1987), "Sondeo lineal: el tiempo de búsqueda más grande probable crece logarítmicamente con el número de registros", 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). Introducción a los algoritmos (3ª ed.). Cambridge, Massachusetts Londres, Inglaterra: MIT Press. ISBN 978-0-262-53305-8.
13. Bender, Michael A.; Kuszmaul, Bradley C.; Kuszmaul, William (2022). "Revisitando el sondeo lineal: las lápidas marcan la desaparición del agrupamiento primario". 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. págs. 1171–1182. doi :10.1109/focs52979.2021.00115. ISBN . 978-1-6654-2055-6. Número de identificación del sujeto  260502788.
14. "IdentityHashMap", Documentación de Java SE 7 , Oracle , consultado el 15 de enero de 2016
15. Friesen, Jeff (2012), Beginning Java 7, Voz de experto en Java, Apress, p. 376, ISBN 9781430239109
16. Kabutz, Heinz M. (9 de septiembre de 2014), "Crisis de identidad", The Java Specialists' Newsletter , 222
17. Weiss, Mark Allen (2014), "Capítulo 3: Estructuras de datos", en Gonzalez, Teofilo; Diaz-Herrera, Jorge; Tucker, Allen (eds.), Computing Handbook , vol. 1 (3.ª ed.), CRC Press, p. 3-11, ISBN 9781439898536.
18. Pagh, Anna; Pagh, Rasmus ; Ružić, Milan (2009), "Sondaje lineal con independencia constante", SIAM Journal on Computing , 39 (3): 1107–1120, arXiv : cs/0612055 , doi :10.1137/070702278, MR  2538852
19. Pătraşcu, Mihai ; Thorup, Mikkel (2011), "El poder del hash de tabulación simple", Actas del 43.° Simposio anual de la ACM sobre teoría de la computación (STOC '11) , págs. 1–10, arXiv : 1011.5200 , doi :10.1145/1993636.1993638, S2CID  195776653
20. Thorup, Mikkel (2009), "String hashing for linear probing", Actas del vigésimo simposio anual ACM-SIAM sobre algoritmos discretos , Filadelfia, PA: SIAM, págs. 655–664, CiteSeerX 10.1.1.215.4253 , doi :10.1137/1.9781611973068.72, MR  2809270 
21. Parhami, Behrooz (2006), Introducción al procesamiento paralelo: algoritmos y arquitecturas, Serie en Ciencias de la Computación, Springer, 4.1 Desarrollo de modelos tempranos, pág. 67, ISBN 9780306469640
22. Morin, Pat (2004), "Tablas hash", en Mehta, Dinesh P.; Sahni, Sartaj (eds.), Manual de estructuras de datos y aplicaciones , Chapman & Hall / CRC, pág. 9-15, ISBN 9781420035179.
23. Peterson, WW (abril de 1957), "Direccionamiento para almacenamiento de acceso aleatorio", IBM Journal of Research and Development , 1 (2), Riverton, NJ, EE. UU.: IBM Corp.: 130–146, doi :10.1147/rd.12.0130
24. Ershov, AP (1958), "Sobre la programación de operaciones aritméticas", Communications of the ACM , 1 (8): 3–6, doi : 10.1145/368892.368907 , S2CID  15986378Traducido de Doklady AN URSS 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), "Sobre el análisis del hash de sondeo lineal" (PDF) , Algorithmica , 22 (4): 490–515, doi :10.1007/PL00009236, MR  1701625, S2CID  5436036
26. Knuth, DE (1998), "Sondaje lineal y gráficos", Algorithmica , 22 (4): 561–568, arXiv : cs/9801103 , doi :10.1007/PL00009240, MR  1701629, S2CID  12254909