El sondeo lineal es un esquema en programación de computadoras 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 doble hash , el sondeo lineal es una forma de direccionamiento abierto . En estos esquemas, cada celda de una tabla hash almacena un solo 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 la nueva clave allí. Las búsquedas se realizan de la misma manera, buscando secuencialmente en la tabla 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 comúnmente utilizadas, y la implementación más popular en hardware estándar utiliza el 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. Se necesita un tiempo esperado constante por búsqueda, inserción o eliminación cuando se implementa mediante 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 abiertos 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 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 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, generalmente codificando las claves para que las claves con valores similares no se coloquen cerca una de la otra 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 siguiente celda vacía más cercana. [3] [4]
Buscar
Para buscar una clave x dada , se examinan las celdas de T , comenzando con la celda en el índice h ( x ) (donde h es la función hash) y continuando hasta las celdas adyacentes h ( x ) + 1 , h ( x ) + 2 , ..., hasta encontrar una celda vacía o una celda cuya clave almacenada es 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 con 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 es x . El nuevo par clave-valor se coloca en esa celda. [3] [4]
Si la inserción hiciera que el factor de carga de la tabla (su fracción de celdas ocupadas) crezca por encima de algún 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 tasa de crecimiento alta para el tamaño de la tabla conduce a operaciones de tabla hash más rápidas pero a 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 mesa cuando el factor de carga excedería 1/2, haciendo que el factor de carga permanezca entre 1/4 y 1/2. [5]
Supresión
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 tienen un valor hash anterior a la celda vacía, pero que se almacenan en una posición posterior a la celda vacía. La celda vacía 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 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 a o antes de i ). Cuando se encuentra una celda vacía, 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 adelante en el mismo bloque de celdas ocupadas. La búsqueda de una llave móvil continúa para la nueva celda vacía, de la misma forma, hasta que termina llegando 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]
Alternativamente, 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 marca especial que indica una clave eliminada. 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 la bandera de la matriz y volver a hacer un refrito de todos los pares clave-valor restantes una vez que una fracción demasiado grande de la matriz queda ocupada por claves eliminadas. [3] [4]
Propiedades
El sondeo lineal proporciona una buena localidad de referencia , lo que hace que requiera pocos accesos a la memoria sin 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 con factores de carga altos debido al agrupamiento primario , 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 utiliza con funciones hash de baja calidad que no eliminan las faltas de uniformidad en la distribución de entrada, el sondeo lineal puede ser más lento que otras estrategias de direccionamiento abierto como el doble hash , que sondea una secuencia de celdas cuya separación está determinada por un segundo función hash, o sondeo cuadrático , donde el tamaño de cada paso varía dependiendo de su posición dentro de la secuencia de la sonda. [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]
Más detalladamente, el tiempo para cualquier operación en 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 son igualmente probables, 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 partida. Por lo tanto, el tiempo esperado para una operación se puede calcular como el producto de estos dos términos, O ( k 2 / 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 una ubicación inicial aleatoria en un estado específico de la tabla hash), sumando todos los bloques que podrían existir (en lugar de los que existen realmente en un estado dado de la tabla), y multiplicar 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 hay un bloque contiguo máximo de celdas ocupadas de longitud k comenzando en el índice i , el tiempo esperado por operación es
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 tienen valores hash que se encuentran 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
Pero por la forma multiplicativa del límite de Chernoff , cuando el factor de carga se aleja de uno, la probabilidad de que un bloque de longitud k contenga al menos k valores hash es exponencialmente pequeña en función de k , lo que hace que esta suma esté limitada por una constante independiente de n . [3] También es posible realizar el mismo análisis usando 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 una búsqueda exitosa es O (1 + 1 / (1 - α )) , y el tiempo esperado para 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 una longitud logarítmica. [11]
Elección de la función hash
Debido a que el sondeo lineal es especialmente sensible a los 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 asume que el hash de cada clave es un número aleatorio independiente de los hash de todas las demás claves. Esta suposición no es realista para la mayoría de las aplicaciones de hash. Sin embargo, los valores hash aleatorios o pseudoaleatorios se pueden usar cuando se procesan objetos por su identidad en lugar de por su valor. Por ejemplo, esto se hace mediante el sondeo lineal de la clase IdentityHashMap del marco de colecciones de Java . [12] 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 por lo demás es arbitrario. [13] Debido a que el 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 involucrar cálculos más lentos como la llamada a un generador de números aleatorios o pseudoaleatorios. Por ejemplo, Java 8 usa un generador de números pseudoaleatorios Xorshift para construir estos valores. [14]
Para la mayoría de las aplicaciones de hash, es necesario calcular la función hash para cada valor cada vez que se aplica hash, en lugar de una vez cuando se crea su objeto. En tales aplicaciones, los números aleatorios o pseudoaleatorios no se pueden usar como valores hash, porque entonces diferentes objetos con el mismo valor tendrían diferentes hash. 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 usarse en tablas hash. [15] 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 a partir del marco de hash k -independiente , una clase de funciones hash que se inicializan a partir de una pequeña semilla aleatoria y que es igualmente probable que mapeen 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 más grande es 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, [16] mientras que algunas funciones de hash independientes de 4 funcionan mal, tomando hasta 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. No obstante, el sondeo lineal que utiliza estas funciones hash requiere un tiempo esperado constante por operación. [4] [17] Tanto el hash de tabulación como los métodos estándar para generar funciones de hash independientes de 5 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 la tabla hash. índices. [1] [18]
En una comparación experimental, Richter et al. encontró que la familia de funciones hash Multiply-Shift (definida como) fue "la función hash más rápida cuando se integró con todos los esquemas de hash, es decir, produciendo los rendimientos más altos y también de buena calidad", mientras que el hash de tabulación produjo "el rendimiento más bajo". [2] Señalan que cada consulta de tabla requiere varios ciclos, siendo más cara que las operaciones aritméticas simples. También encontraron que MurmurHash es 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".
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 , [19] 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, encadenamiento, en lugar de sondeo lineal. [20]
Knuth ( 1963 ) resume la historia temprana del sondeo lineal. Fue el primer método de direccionamiento abierto y originalmente fue 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 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 de forma independiente por otros ya sea antes o desde ese momento ". [21] Otra publicación temprana de este método fue realizada por el investigador soviético Andrey Ershov , en 1958. [22]
El primer análisis teórico del sondeo lineal, que muestra que se necesita 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, [23] [24] y la prueba de que el sondeo lineal se ejecuta en tiempo constante por operación con funciones hash prácticamente utilizables en lugar de funciones aleatorias idealizadas asumido por un análisis anterior. [16] [17]
Referencias
- ^ a b 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
- ^ a b Richter, Stefan; Álvarez, Víctor; Dittrich, Jens (2015), "Un análisis en siete dimensiones de los métodos hash y sus implicaciones en el procesamiento de consultas" (PDF) , Proceedings of the VLDB Endowment , 9 (3): 293–331, doi : 10.14778 / 2850583.2850585
- ^ a b c d e f g Goodrich, Michael T .; Tamassia, Roberto (2015), "Sección 6.3.3: Sondeo lineal", Diseño y aplicaciones de algoritmos , Wiley, págs. 200-203
- ^ a b c d e f Morin, Pat (22 de febrero, 2014), "Sección 5.2: LinearHashTable: sondeo lineal", estructuras abiertas de datos (en pseudocódigo) (0,1 g β . Ed.), Pp 108-116 , recuperada 01/15/2016
- ^ Sedgewick, Robert ; Wayne, Kevin (2011), Algoritmos (4ª ed.), Addison-Wesley Professional, pág. 471, ISBN 9780321573513. Sedgewick y Wayne también reducen a la mitad el tamaño de la tabla cuando una eliminación provocaría que el factor de carga fuera demasiado bajo, lo que les haría utilizar un rango más amplio [1 / 8,1 / 2] en los posibles valores del factor de carga.
- ^ a b Pătraşcu, Mihai ; Thorup, Mikkel (2010), "Sobre la k -independencia requerida por el sondeo lineal y la independencia mínima" (PDF) , Automata, Languages and Programming , 37th International Colloquium, ICALP 2010, Burdeos, Francia, 6 al 10 de julio de 2010, Actas , Parte I , Lecture Notes in Computer Science , 6198 , Springer, págs. 715–726, arXiv : 1302.5127 , doi : 10.1007 / 978-3-642-14165-2_60
- ^ a b Heileman, Gregory L .; Luo, Wenbin (2005), "Cómo el almacenamiento en caché afecta el hash" (PDF) , Séptimo taller sobre ingeniería de algoritmos y experimentos (ALENEX 2005) , págs. 141-154
- ^ a b c d Knuth, Donald (1963), Notes on "Open" Addressing , archivado desde el original el 3 de marzo de 2016
- ^ Eppstein, David (13 de octubre de 2011), "Sondeo lineal simplificado " , 0xDE
- ^ a b Sedgewick, Robert (2003), "Sección 14.3: Sondeo lineal", Algoritmos en Java, Partes 1 a 4: Fundamentos, estructuras de datos, clasificación, búsqueda (3ª ed.), Addison Wesley, págs. 615–620, ISBN 9780321623973
- ^ Pittel, B. (1987), "Sondeo lineal: el mayor tiempo de búsqueda 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
- ^ "IdentityHashMap" , documentación de Java SE 7 , Oracle , consultado el 15 de enero de 2016
- ^ Friesen, Jeff (2012), Beginning Java 7 , Expert's voice in Java, Apress, p. 376, ISBN 9781430239109
- ^ Kabutz, Heinz M. (9 de septiembre de 2014), "Identity Crisis" , The Java Specialists 'Newsletter , 222
- ^ Weiss, Mark Allen (2014), "Capítulo 3: Estructuras de datos" , en González, Teófilo; Díaz-Herrera, Jorge; Tucker, Allen (eds.), Computing Handbook , 1 (3ª ed.), CRC Press, p. 3-11, ISBN 9781439898536.
- ^ a b Pagh, Anna; Pagh, Rasmus ; Ružić, Milán (2009), "Sondeo lineal con independencia constante", SIAM Journal on Computing , 39 (3): 1107–1120, arXiv : cs / 0612055 , doi : 10.1137 / 070702278 , MR 2538852
- ^ a b Pătraşcu, Mihai ; Thorup, Mikkel (2011), "El poder del hash de tabulación simple", Actas del 43 ° Simposio anual de ACM sobre Teoría de la Computación (STOC '11) , págs. 1-10, arXiv : 1011.5200 , doi : 10.1145 / 1993636.1993638
- ^ 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
- ^ Parhami, Behrooz (2006), Introducción al procesamiento paralelo: algoritmos y arquitecturas , Series in Computer Science, Springer, 4.1 Desarrollo de los primeros modelos, p. 67, ISBN 9780306469640
- ^ Morin, Pat (2004), "Tablas hash" , en Mehta, Dinesh P .; Sahni, Sartaj (eds.), Manual de estructuras y aplicaciones de datos , Chapman & Hall / CRC, p. 9-15, ISBN 9781420035179.
- ^ Peterson, WW (abril de 1957), "Addressing for random-access storage", IBM Journal of Research and Development , Riverton, Nueva Jersey, EE. UU .: IBM Corp., 1 (2): 130–146, doi : 10.1147 / rd.12.0130
- ^ Ershov, AP (1958), "On Programming of Arithmetic Operations", Communications of the ACM , 1 (8): 3–6, doi : 10.1145 / 368892.368907. Traducido de Doklady AN USSR 118 (3): 427–430, 1958, por Morris D. Friedman. El palpado lineal se describe como algoritmo A2.
- ^ 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
- ^ Knuth, DE (1998), "Linear probing and graphs", Algorithmica , 22 (4): 561–568, arXiv : cs / 9801103 , doi : 10.1007 / PL00009240 , MR 1701629