Sonido lineal

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de febrero de 2022; la verificación requiere 1 edición .

El sondeo lineal  es un esquema de programación para resolver colisiones en tablas hash , estructuras de datos para manipular conjuntos de pares clave-valor encontrar los valores asociados con una clave determinada. El esquema fue concebido en 1954 por Amdahl , Elaine McGraw y Arthur Samuel y analizado en 1963 por Donald Knuth .

Junto con el sondeo cuadrático y el sondeo doble , el sondeo lineal es una especie de direccionamiento abierto . En estos esquemas, cada celda de la tabla hash contiene un par clave-valor. Si la función hash choca al asignar el valor de la nueva clave a una celda de la tabla hash ocupada por otra clave, el sondeo lineal explora la tabla hasta la siguiente celda libre más cercana e inserta allí la nueva clave. La búsqueda de un valor se realiza de la misma forma, escaneando la tabla secuencialmente, comenzando desde la posición determinada por la función hash, hasta encontrar una clave coincidente, o una celda vacía.

Como escribieron Thorup y Zhang, "las tablas hash hacen un uso intensivo de estructuras de datos no triviales y la mayoría de las implementaciones de hardware usan sondeo lineal, que es rápido y fácil de implementar" [1] . El sondeo lineal puede brindar un alto rendimiento debido a la buena localidad de referencia del método pero es más sensible a la calidad de la función hash que otros esquemas de resolución de colisiones. El tiempo promedio esperado de búsqueda de un método es constante, lo mismo es cierto para las inserciones y eliminaciones si la implementación usa aleatorización de hash, hash independiente de 5 o hash de tabla . Sin embargo, en la práctica se obtienen buenos resultados con otras funciones hash como MurmurHash [2] .

Operaciones

El sondeo lineal es un componente de los esquemas de direccionamiento abierto para su uso en tablas hash para resolver problemas de vocabulario . En una tarea de diccionario, la estructura de datos debe operar sobre un conjunto de pares clave-valor y debe permitir la inserción y eliminación de pares, así como la búsqueda del valor asociado a la clave. En el direccionamiento abierto, la estructura de datos es una matriz T (tabla hash) cuyas celdas T [ i ] (si no están vacías) contienen un único par clave-valor. Se usa una función hash para asignar cada clave a una celda T de la tabla donde se debe colocar esa clave, generalmente codificando las claves para que las claves con valores cercanos no estén cerca en la tabla. Una colisión hash ocurre cuando la función hash asigna una clave a una celda que ya está ocupada por otra clave. El sondeo lineal es una estrategia para resolver colisiones colocando una nueva clave en la siguiente celda libre más cercana [3] [4] .

Buscar

Para buscar una clave dada x , se revisan las celdas de la tabla T , comenzando con la celda con índice h ( x ) (donde h  es una función hash), luego las celdas h ( x ) + 1 , h ( x ) + 2 , ..., hasta encontrar una celda libre o una celda que contenga la clave x . Si se encuentra la celda que contiene la clave, el procedimiento de 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 y el procedimiento devuelve como resultado que no se encontró la clave [3] [4]

Insertar

Para insertar un par clave-valor ( x , v ) en una tabla (posiblemente reemplazando cualquier par existente con la misma clave), el algoritmo de inserción recorre la misma secuencia de celdas que en la búsqueda hasta que encuentra una celda vacía o una celda que contiene la clave x . El nuevo par clave-valor se coloca en esta celda [3] [4] .

Si, después de una inserción , el factor de carga de la tabla (la fracción de celdas ocupadas) supera algún umbral, la tabla completa se puede reemplazar con una nueva tabla que crece en tamaño por un factor constante, como en el caso de una matriz dinámica , con una nueva tabla hash. Establecer este umbral cerca de cero y usar un factor de dispersión de tabla alto da como resultado operaciones rápidas pero consume mucha memoria. Normalmente, el tamaño de la mesa se duplica cuando se alcanza un factor de carga de 1/2, por lo que la carga está entre 1/4 y 1/2 [5]

Eliminación

Puede eliminar un par clave-valor de un diccionario. Sin embargo, no es suficiente simplemente borrar la celda. Tal vez haya otro par con el mismo valor hash que se colocó en algún lugar después de la celda ocupada. Después de borrar la celda, la búsqueda de un segundo valor con el mismo valor hash dará como resultado una celda vacía y no se encontrará el par.

Por lo tanto, al borrar la celda i , debemos mirar las celdas posteriores hasta que encontremos una celda vacía o una clave que se pueda transferir a la celda i (es decir, una clave cuyo valor hash sea igual o menor que i ). Si se encuentra una celda vacía, puede borrar la celda i y detener el proceso de eliminación. Si se encuentra una clave que se puede mover a la celda i , muévala. Esto aumentará la velocidad de búsqueda de la clave transferida y también borrará otra celda en el bloque de celdas ocupadas. Es necesario continuar la búsqueda de una clave que pueda transferirse a este espacio liberado. La búsqueda de una clave para transferir se realiza a una celda vacía, hasta llegar a la celda que originalmente estaba vacía. Así, el tiempo de ejecución de todo el proceso de borrado es proporcional a la longitud del bloque que contiene la clave borrada [3] .

Alternativamente, se puede usar una estrategia de eliminación diferida , en la que el par clave-valor se elimina reemplazando el valor con una bandera especial que indica que la clave ha sido eliminada. Sin embargo, dichas banderas dan como resultado un aumento en el factor de carga de la tabla hash. En esta estrategia, puede ser necesario eliminar las banderas de la matriz y volver a calcular los valores hash de todos los pares clave-valor restantes cuando se eliminan demasiados valores [3] [4] .

Propiedades

El sondeo lineal brinda una buena localidad de referencia , lo que significa que solo se necesitan unos pocos accesos a la memoria no almacenada en caché por operación. En vista de esto, manteniendo un factor de carga bajo, el algoritmo puede ofrecer un alto grado de rendimiento. Sin embargo, en comparación con otras estrategias de direccionamiento abierto, el rendimiento se degrada más rápidamente cuando se carga debido a la agrupación primaria , la tendencia de una sola colisión a causar muchas colisiones cercanas [3] . Además, este método requiere una función hash de mayor calidad que otros esquemas de resolución de colisiones [6] para obtener un buen rendimiento . Si el algoritmo se implementa con una función hash de baja calidad que no elimina la heterogeneidad en la distribución de entrada, el sondeo lineal puede ser más lento que otras estrategias de direccionamiento abiertas, como el sondeo doble , que prueba una secuencia de celdas cuya separación está determinada por una segunda función hash, o sondeo cuadrático , cuando el tamaño de cada paso cambia dependiendo de la posición en la secuencia de sondeos [7] .

Análisis

Cuando se utiliza el sondeo lineal, las operaciones del diccionario se pueden implementar con un tiempo de acceso 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 específicamente, el tiempo para cada operación individual (búsqueda, inserción o eliminación) es proporcional a la longitud del bloque contiguo de celdas ocupadas a partir del cual comienza la operación. Si todas las celdas iniciales tienen la misma probabilidad en una tabla hash con N celdas, entonces un bloque máximo de k celdas ocupadas tiene una probabilidad k / N de contener la posición de búsqueda inicial y toma O ( k ) tiempo , donde sea que se encuentre la celda inicial. Por lo tanto, el tiempo de ejecución esperado de la 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 los cuadrados de las longitudes de los bloques da el borde. tiempo de espera para una función hash aleatoria (en lugar de una posición inicial aleatoria en la tabla hash) sumando todos los bloques que podrían existir (en lugar de los que realmente existen en el estado actual de la tabla) y multiplicando los términos para cada bloque potencial por la probabilidad de que el bloque esté ocupado. Es decir, si definimos Block( i , k ) como el evento de que existe un bloque máximo contiguo de celdas ocupadas de longitud k comenzando en el índice i , mat. el tiempo de espera para la operación es

La 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 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 a la frontera

Pero, de acuerdo con la forma multiplicativa del límite de Chernoff , si el factor de carga es estrictamente menor que uno, la probabilidad de que la longitud del bloque k contenga al menos k valores hash es exponencialmente pequeña en función de k , lo que significa que la suma está acotado por una constante independiente de n [ 3] . También se puede hacer el mismo análisis utilizando la fórmula 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 fallida (o inserción de una nueva clave) es O (1 + 1/(1 - a ) 2 ) [10 ] . Para un factor de carga constante, con una alta probabilidad, la secuencia de sondeo más larga (entre las secuencias de sondeo para todas las claves de la tabla) tiene una longitud logarítmica [11] .

Seleccionar una función hash

Dado que el sondeo lineal es muy sensible a los valores de hash distribuidos de manera desigual [7] , es importante combinar el método con una función de hash de alta calidad que no genere tal desigualdad.

El análisis anterior asume que el hash de cada clave es un número aleatorio independiente de los hash de otras claves. Esta suposición no es realista para la mayoría de las aplicaciones hash. Sin embargo, los valores hash aleatorios o pseudoaleatorios se pueden usar cuando los objetos se codifican por su id en lugar de por valor. Por ejemplo, esto se hace usando un sondeo lineal con la clase IdentityHashMap en el marco de colecciones de Java [12] conjunto de clases e interfaces . Se garantiza que el valor hash que esta clase asocia con cada objeto, su IdentityHashCode, seguirá siendo el mismo para el objeto a lo largo de su vida útil, pero el valor hash para el mismo objeto en otras circunstancias será diferente [13] . Dado que el IdentityHashCode se construye solo una vez por objeto y no necesita estar asociado con el valor o la dirección del objeto, su construcción puede usar medios computacionales más lentos, como llamar a generadores de números aleatorios o pseudoaleatorios. Por ejemplo, Java 8 utiliza el generador numérico pseudoaleatorio Xorshift [14] para construir tales valores .

Para la mayoría de las aplicaciones hash, es necesario calcular la función hash para cada valor cada vez que se requiere un hash, no solo una vez que se crea el objeto. En dichas aplicaciones, los números aleatorios o pseudoaleatorios no pueden usarse como valores hash, porque entonces diferentes objetos con el mismo valor podrían tener diferentes valores hash. Y las funciones hash criptográficas (que están diseñadas para ser indistinguibles de las verdaderas funciones aleatorias) suelen ser demasiado lentas para usarse en tablas hash [15] . En su lugar, se utilizan 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 en términos de hashing k -independiente , una clase de funciones hash que se inicializan con un pequeño número aleatorio y asignan cualquier k -tupla de claves distintas a cualquier k -tupla de índices con igual probabilidad. El parámetro k se puede considerar 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á más cerca de 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 hash independientes de 4 funcionan mal y requieren un tiempo logarítmico por operación [6] .

Otro método para construir funciones hash con alta calidad y velocidad aceptable es el hashing de tablas . En este método, el valor hash de la clave se calcula eligiendo para cada byte de la clave un índice en una tabla de números aleatorios (con una tabla diferente para cada posición de byte). Los números de las celdas de estas tablas luego se combinan bit a bit usando la operación XOR . Las funciones hash construidas de esta manera son solo 3 independientes. Sin embargo, las sondas lineales que utilizan estas funciones hash requieren un tiempo esperado constante por operación [4] [17] . Tanto el hash de tablas como los métodos estándar para generar funciones hash independientes de 5 están limitados a claves que tienen un número fijo de bits. Para trabajar con cadenas u otros tipos de claves de longitud variable, se puede combinar la técnica de hashing universal más simple , que asigna claves a valores intermedios, con una función hash de alta calidad (5-independencia o tabulación ), que asigna valores intermedios ​​para hash índices -tablas [1] [18] .

En comparaciones experimentales, Richter et al. encontraron que la familia de funciones hash fold-shift (definida como ) era "la función hash más rápida cuando se usaba en todos los esquemas hash, es decir, brindaba el mayor rendimiento y buena calidad", en la tabla while hashing dio "el rendimiento más bajo" [2] . Señalaron que mirar cada tabla requiere varios ciclos, lo cual es más costoso que simples operaciones aritméticas. También descubrieron que MurmurHash es mejor que el hashing de tablas: "Después de examinar los resultados presentados por Mult y Murmur, creemos que la 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 por Konrad Zuse y Vanivar Busch [19] , pero las tablas hash no se describieron hasta que se describieron . Lun [ en un memorándum de IBM en 1953. Lun usó un método diferente para resolver colisiones, encadenando en lugar de sondeo lineal [20] .

Donald Knuth [8] resumió la historia temprana del sondeo lineal. Este fue el primer método de direccionamiento abierto y al principio fue sinónimo de direccionamiento abierto. Según Knuth, el método fue utilizado por primera vez por Jean Amdahl , McGraw, Elani M. y Arthur Samuel en 1954 en un programa ensamblador para el IBM 701 [8] . La primera descripción publicada del sonido lineal fue dada por Peterson [21] [8] , quien también mencionó a Samuel, Amdahl y McGraw, pero agregó que "el sistema es tan natural que es muy probable que haya sido creado de forma independiente por otros". antes o al mismo tiempo" [ 22] . Otra publicación temprana de este método pertenece al investigador soviético Andrey Petrovich Ershov , publicada en 1958 [23] .

El primer análisis teórico del sondeo lineal que muestra que el método funciona en un tiempo esperado constante por operación en una función hash aleatoria fue realizado por Knuth [8] . Sedgwick llamó al trabajo de Knuth "un hito en el análisis de algoritmos" [10] . Significativamente más tarde, los estudios llevaron a un análisis más detallado de la distribución de probabilidad del tiempo de trabajo [24] [25] y la prueba de que el sondeo lineal funciona en tiempo constante por operación con una función hash conveniente para cálculos prácticos, y no con el ideal función aleatoria asumida en análisis anteriores [16] [17] .

Notas

  1. ↑ 1 2 Thorup, Zhang, 2012 , pág. 293–331.
  2. ↑ 1 2 Richter, Álvarez, Dittrich, 2015 , p. 293–331.
  3. ↑ 1 2 3 4 5 6 7 Goodrich, Tamassia, 2015 , pág. 200–203.
  4. ↑ 1 2 3 4 5 6 Morin, 2014 , pág. 108–116.
  5. ↑ Sedgewick, Wayne, 2011 ; Sedgwick y Wayne reducen a la mitad el tamaño de la mesa si la carga de la mesa es demasiado baja en una división, lo que da como resultado un rango más amplio [1/8, 1/2] de posibles factores de carga.
  6. ↑ 1 2 Pătraşcu, Thorup, 2010 , pág. 715–726.
  7. ↑ 1 2 Heileman, Luo, 2005 , pág. 141–154.
  8. ↑ 1 2 3 4 5 Knuth, 1963 .
  9. ↑ Epstein, 2011 .
  10. ↑ 12 Sedgewick , 2003 .
  11. ↑ Pittel, 1987 , pág. 236–249.
  12. ↑ Documentación de Java SE 7 .
  13. ↑ Friesen, 2012 , pág. 376.
  14. ↑ Kabutz, 2014 .
  15. ↑ Weiss, 2014 , pág. 3-11.
  16. ↑ 1 2 Pagh, Pagh, Ružić, 2009 , pág. 1107-1120.
  17. ↑ 1 2 Pătrașcu, Thorup, 2011 , p. 1–10.
  18. ↑ Thorup, 2009 , pág. 655–664.
  19. ↑ Parhami, 2006 , pág. 67.
  20. ↑ Morin, 2004 , pág. 9-15.
  21. ↑ Peterson, 1957 .
  22. ↑ Peterson, 1957 , pág. 130–146.
  23. ↑ Ershov, 1958 , pág. 3–6.
  24. ↑ Flajolet, Poblete, Viola, 1998 , p. 490–515.
  25. ↑ Knuth, 1998 , pág. 561–568.

Literatura