data-structures - tablas - transformacion hash

¿Cómo funciona una tabla hash? (14)

Aquí hay otra forma de verlo.

Supongo que entiende el concepto de una matriz A. Eso es algo que admite la operación de indexación, donde puede obtener el elemento Ith, A [I], en un solo paso, sin importar qué tan grande sea A.

Entonces, por ejemplo, si desea almacenar información sobre un grupo de personas a las que todas tienen edades diferentes, una manera simple sería tener una matriz que sea lo suficientemente grande, y usar la edad de cada persona como un índice en la matriz. De esta forma, podría tener acceso en un solo paso a la información de cualquier persona.

Pero, por supuesto, podría haber más de una persona con la misma edad, de modo que lo que se coloca en la matriz en cada entrada es una lista de todas las personas que tienen esa edad. Por lo tanto, puede acceder a la información de una persona individual en un solo paso más un poco de búsqueda en esa lista (llamada "cubo"). Sólo se ralentiza si hay tanta gente que los cubos se vuelven grandes. Luego, necesita una matriz más grande y alguna otra forma de obtener más información de identificación sobre la persona, como las primeras letras de su apellido, en lugar de usar age.

Esa es la idea básica. En lugar de usar la edad, se puede usar cualquier función de la persona que produce una buena distribución de valores. Esa es la función hash. Al igual que usted podría tomar cada tercer bit de la representación ASCII del nombre de la persona, mezclado en algún orden. Lo único que importa es que no quieras que demasiadas personas se peguen al mismo cubo, porque la velocidad depende de que los cubos sean pequeños.

Estoy buscando una explicación de cómo funciona una tabla hash, ¡en un lenguaje sencillo para un simplón como yo!

Por ejemplo, sé que toma la clave, calcula el hash (estoy buscando una explicación de cómo) y luego realiza algún tipo de módulo para averiguar dónde se encuentra en la matriz donde se almacena el valor, pero ahí es donde mi conocimiento se detiene. .

¿Alguien podría aclarar el proceso?

Edición: no pregunto específicamente sobre cómo se calculan los códigos hash, sino una descripción general de cómo funciona una tabla hash.

Aquí hay una explicación en términos sencillos.

Supongamos que desea llenar una biblioteca con libros y no solo meterlos allí, sino que desea poder encontrarlos fácilmente de nuevo cuando los necesite.

Entonces, usted decide que si la persona que quiere leer un libro conoce el título del libro y el título exacto para iniciar, entonces eso es todo lo que debe tomar. Con el título, la persona, con la ayuda del bibliotecario, debe poder encontrar el libro con facilidad y rapidez.

Entonces, ¿cómo puedes hacer eso? Bueno, obviamente, puede mantener algún tipo de lista de dónde coloca cada libro, pero luego tiene el mismo problema que buscar en la biblioteca, necesita buscar en la lista. Concedido, la lista sería más pequeña y más fácil de buscar, pero aún así no desea buscar secuencialmente de un extremo de la biblioteca (o lista) al otro.

Quieres algo que, con el título del libro, pueda darte el lugar correcto a la vez, por lo que todo lo que tienes que hacer es ir al estante correcto y recoger el libro.

Pero, ¿cómo se puede hacer eso? Bueno, con un poco de previsión cuando llena la biblioteca y mucho trabajo cuando llena la biblioteca.

En lugar de comenzar a llenar la biblioteca de un extremo a otro, diseña un pequeño método inteligente. Usted toma el título del libro, lo ejecuta a través de un pequeño programa de computadora, que escupe un número de estante y un número de ranura en ese estante. Aquí es donde colocas el libro.

La belleza de este programa es que más adelante, cuando una persona vuelve a leer el libro, usted introduce el título en el programa una vez más, y recupera el mismo número de estante y número de espacio que le dieron originalmente, y esto es donde se encuentra el libro

El programa, como otros ya han mencionado, se denomina algoritmo hash o cómputo hash y generalmente funciona tomando los datos ingresados (el título del libro en este caso) y calcula un número a partir de él.

Para simplificar, digamos que simplemente convierte cada letra y símbolo en un número y los resume a todos. En realidad, es mucho más complicado que eso, pero dejémoslo así por ahora.

La belleza de tal algoritmo es que si ingresa la misma entrada una y otra vez, seguirá escupiendo el mismo número cada vez.

Ok, así es básicamente como funciona una tabla hash.

Lo técnico sigue.

Primero, está el tamaño del número. Generalmente, la salida de tal algoritmo hash está dentro de un rango de un gran número, generalmente mucho más grande que el espacio que tiene en su tabla. Por ejemplo, digamos que tenemos espacio para exactamente un millón de libros en la biblioteca. La salida del cálculo de hash podría estar en el rango de 0 a mil millones, que es mucho mayor.

¿Asi que que hacemos? Usamos algo llamado cálculo de módulo, que básicamente dice que si contaste el número que querías (es decir, el número de mil millones) pero quisiste permanecer dentro de un rango mucho más pequeño, cada vez que alcanzas el límite de ese rango más pequeño en el que volviste a 0, pero tienes que hacer un seguimiento de cuán lejos en la secuencia grande has llegado.

Digamos que la salida del algoritmo hash está en el rango de 0 a 20 y obtienes el valor 17 de un título en particular. Si el tamaño de la biblioteca es de solo 7 libros, cuentas 1, 2, 3, 4, 5, 6, y cuando llegas a 7, comienzas de nuevo a 0. Ya que necesitamos contar 17 veces, tenemos 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, y el número final es 3.

Por supuesto, el cálculo del módulo no se hace de esa manera, se hace con división y un resto. El resto de dividir 17 por 7 es 3 (7 va 2 veces a 17 en 14 y la diferencia entre 17 y 14 es 3).

Así, pones el libro en la ranura número 3.

Esto lleva al siguiente problema. Colisiones Ya que el algoritmo no tiene forma de espaciar los libros para que llenen la biblioteca exactamente (o la tabla hash si así lo desea), invariablemente terminará calculando un número que se ha usado antes. En el sentido de la biblioteca, cuando llegas al estante y al número de espacio en el que deseas poner un libro, ya hay un libro allí.

Existen varios métodos de manejo de colisiones, incluyendo la ejecución de los datos en otro cálculo para obtener otro punto en la tabla ( doble hash ), o simplemente para encontrar un espacio cercano al que recibió (es decir, justo al lado del libro anterior, asumiendo la ranura) Estaba disponible también conocido como sondeo lineal ). Esto significaría que tienes que cavar un poco cuando intentas encontrar el libro más tarde, pero aún así es mejor que simplemente comenzar en un extremo de la biblioteca.

Finalmente, en algún momento, es posible que desee poner más libros en la biblioteca de lo que la biblioteca permite. En otras palabras, necesitas construir una biblioteca más grande. Dado que el lugar exacto en la biblioteca se calculó utilizando el tamaño exacto y actual de la biblioteca, se sigue que si cambia el tamaño de la biblioteca, es posible que tenga que encontrar nuevos sitios para todos los libros desde el cálculo realizado para encontrarlos. ha cambiado.

Espero que esta explicación haya sido un poco más realista que los cubos y funciones :)

Así es como funciona en mi entendimiento:

Aquí hay un ejemplo: imagina la tabla completa como una serie de cubos. Supongamos que tiene una implementación con códigos hash alfanuméricos y tiene un cubo para cada letra del alfabeto. Esta implementación coloca cada elemento cuyo código hash comienza con una letra en particular en el grupo correspondiente.

Digamos que tienes 200 objetos, pero solo 15 de ellos tienen códigos hash que comienzan con la letra ''B''. La tabla hash solo tendría que buscar y buscar entre los 15 objetos en el cubo ''B'', en lugar de los 200 objetos.

En cuanto al cálculo del código hash, no hay nada mágico en ello. El objetivo es simplemente que diferentes objetos devuelvan códigos diferentes y que objetos iguales devuelvan códigos iguales. Podría escribir una clase que siempre devuelva el mismo número entero como un código hash para todas las instancias, pero esencialmente destruiría la utilidad de una tabla hash, ya que solo se convertiría en un cubo gigante.

Corto y dulce:

Una tabla hash envuelve una matriz, llamémosla internalArray . Los elementos se insertan en la matriz de esta manera:

let insert key value = internalArray[hash(key) % internalArray.Length] <- (key, value) //oversimplified for educational purposes

A veces, dos claves se agrupan en el mismo índice en la matriz y desea mantener ambos valores. Me gusta almacenar ambos valores en el mismo índice, que es fácil de codificar creando internalArray una matriz de listas vinculadas:

let insert key value = internalArray[hash(key) % internalArray.Length].AddLast(key, value)

Entonces, si quisiera recuperar un elemento de mi tabla hash, podría escribir:

let get key = let linkedList = internalArray[hash(key) % internalArray.Length] for (testKey, value) in linkedList if (testKey = key) then return value return null

Las operaciones de eliminación son igual de simples de escribir. Como puede ver, las inserciones, búsquedas y eliminación de nuestro conjunto de listas vinculadas es casi O (1).

Cuando nuestro internalArray se llene demasiado, tal vez en alrededor del 85% de la capacidad, podemos cambiar el tamaño de la matriz interna y mover todos los elementos de la matriz antigua a la nueva matriz.

Es incluso más simple que eso.

Una tabla hash no es más que una matriz (generalmente sparse ) de vectores que contienen pares clave / valor. El tamaño máximo de esta matriz suele ser menor que el número de elementos en el conjunto de valores posibles para el tipo de datos que se almacenan en la tabla hash.

El algoritmo hash se utiliza para generar un índice en esa matriz en función de los valores del elemento que se almacenará en la matriz.

Aquí es donde se almacenan los vectores de pares clave / valor en la matriz. Debido a que el conjunto de valores que pueden ser índices en la matriz es generalmente más pequeño que el número de todos los valores posibles que puede tener el tipo, es posible que su hash El algoritmo va a generar el mismo valor para dos claves separadas. Un buen algoritmo de hash evitará esto tanto como sea posible (por lo que es relegado al tipo generalmente porque tiene información específica que un algoritmo de hash general no puede conocer), pero es imposible evitarlo.

Debido a esto, puede tener varias claves que generarán el mismo código hash. Cuando eso sucede, los elementos del vector se repiten, y se realiza una comparación directa entre la clave del vector y la clave que se está buscando. Si se encuentra, excelente y el valor asociado con la clave se devuelve, de lo contrario, no se devuelve nada.

Esto resulta ser un área bastante profunda de la teoría, pero el esquema básico es simple.

Esencialmente, una función de hash es solo una función que toma elementos de un espacio (por ejemplo, cadenas de longitud arbitraria) y los asigna a un espacio útil para la indexación (números enteros sin signo, por ejemplo).

Si solo tiene un pequeño espacio de hash, puede salirse con la simple interpretación de esas cosas como enteros, y ya está listo (por ejemplo, cadenas de 4 bytes)

Generalmente, sin embargo, tienes un espacio mucho más grande. Si el espacio de las cosas que permite como claves es mayor que el espacio de las cosas que está usando para indexar (su uint32 o lo que sea), no puede tener un valor único para cada una. Cuando dos o más cosas tienen que ver con el mismo resultado, tendrás que manejar la redundancia de una manera adecuada (esto generalmente se conoce como una colisión, y cómo manejarlo o no dependerá un poco de lo que seas). usando el hash para).

Esto implica que no es probable que tenga el mismo resultado, y probablemente también le gustaría que la función hash sea rápida.

¡Equilibrar estas dos propiedades (y algunas otras) ha mantenido a muchas personas ocupadas!

En la práctica, normalmente debería poder encontrar una función que se sepa que funciona bien para su aplicación y usarla.

Ahora para hacer que esto funcione como una tabla hash: imagina que no te importó el uso de la memoria. Luego puede crear una matriz siempre y cuando su conjunto de indexación (todos los uint32, por ejemplo). A medida que agregas algo a la tabla, hash es clave y mira la matriz en ese índice. Si no hay nada allí, pones tu valor allí. Si ya hay algo allí, agregue esta nueva entrada a una lista de cosas en esa dirección, junto con suficiente información (su clave original, o algo inteligente) para encontrar qué entrada pertenece realmente a qué clave.

Así que a medida que avanza un largo, cada entrada en su tabla hash (la matriz) está vacía, o contiene una entrada, o una lista de entradas. Recuperar es tan simple como indexar en la matriz, y devolver el valor o recorrer la lista de valores y devolver el valor correcto.

Por supuesto, en la práctica, normalmente no puedes hacer esto, desperdicia mucha memoria. Así que haces todo basado en una matriz dispersa (donde las únicas entradas son las que realmente usas, todo lo demás es implícitamente nulo).

Hay muchos esquemas y trucos para hacer que esto funcione mejor, pero eso es lo básico.

La forma en que se calcula el hash no depende de la tabla hash, sino de los elementos que se le agregan. En los marcos / bibliotecas de clase base como .net y Java, cada objeto tiene un método GetHashCode () (o similar) que devuelve un código hash para este objeto. El algoritmo de código hash ideal y la implementación exacta dependen de los datos representados en el objeto.

Muchas respuestas, pero ninguna de ellas es muy visual , y las tablas hash pueden "hacer clic" fácilmente cuando se visualizan.

Las tablas hash a menudo se implementan como matrices de listas enlazadas. Si imaginamos una tabla que almacena los nombres de las personas, después de algunas inserciones, se podría colocar en la memoria como se muestra a continuación, donde los números encerrados () son valores hash del texto / nombre.

bucket# bucket content / linked list [0] --> "sue"(780) --> null [1] null [2] --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null [3] --> "mary"(73) --> null [4] null [5] --> "masayuki"(75) --> "sarwar"(105) --> null [6] --> "margaret"(2626) --> null [7] null [8] --> "bob"(308) --> null [9] null

Algunos puntos:

cada una de las entradas de la matriz (índices [0] , [1] ...) se conoce como un grupo, y comienza una lista de valores posiblemente enlazada (esto es, los nombres de las personas)
cada valor (por ejemplo, "fred" con hash 42 ) se vincula desde el grupo [hash % number_of_buckets] por ejemplo, 42 % 10 == [2] ; % es el operador de módulo, el resto cuando se divide por el número de cubos
múltiples valores de datos pueden colisionar y estar vinculados desde el mismo grupo, la mayoría de las veces porque sus valores hash chocan después de la operación del módulo (por ejemplo, 42 % 10 == [2] , y 9282 % 10 == [2] ), pero ocasionalmente porque los valores de hash son los mismos (por ejemplo, "fred" y "jane" ambos mostrados con el hash 42 anterior)
- la mayoría de las tablas hash manejan colisiones (con un rendimiento ligeramente reducido pero sin confusión funcional) al comparar el valor completo (aquí texto) de una clave que se busca o inserta en cada clave que ya se encuentra en la lista vinculada en el cubo de hash-to

Si el tamaño de la tabla aumenta, las tablas hash implementadas como anteriormente tienden a redimensionarse a sí mismas (es decir, crean una matriz más grande de cubetas, crean listas vinculadas nuevas / actualizadas desde allí, eliminan la matriz antigua) para mantener la proporción de elementos a cubetas (también conocida como carga factor ) en algún lugar en el rango de 0.5 a 1.0. Con el factor de carga 1 y una función de hash de fuerza criptográfica, el 36.8% de los cubos tenderá a estar vacío, el 36.8% tiene un elemento, el 18.4% dos elementos, el 6.1% tres elementos, el 1.5% cuatro elementos, el .3% cinco, etc. - las longitudes de la lista promedian 2.0 elementos sin importar cuántos elementos haya en la tabla (es decir, si hay 100 elementos y 100 cubetas, o 100 millones de elementos y 100 millones de cubetas), por lo que decimos que buscar / insertar / borrar es O ( 1) operaciones de tiempo constante.

(Notas: no todas las tablas hash usan listas vinculadas, pero la mayoría de las de propósito general lo hacen, ya que el hashing cerrado (también conocido como direccionamiento abierto), especialmente con las operaciones de borrado admitidas, tiene propiedades de rendimiento menos estables con las teclas / funciones hash propensas a colisiones).

Unas pocas palabras sobre funciones hash

Un propósito general, el trabajo de la función hash que minimiza la colisión en el peor de los casos es rociar las teclas alrededor de los cubos de la tabla hash de forma aleatoria, mientras se genera el mismo valor hash para la misma tecla. Incluso un bit de cambio en cualquier parte de la clave sería idealmente, al azar, voltear la mitad de los bits en el valor de hash resultante.

Esto normalmente está orquestado con matemáticas demasiado complicadas para que yo pueda asimilar. Mencionaré una forma fácil de entender: no es la más escalable o fácil de almacenar en caché, pero es intrínsecamente elegante (como el cifrado con un teclado de una sola vez), ya que creo que ayuda a impulsar las cualidades deseables mencionadas anteriormente. Digamos que estaba haciendo un hashing de 64 bits double s: podría crear 8 tablas cada una de 256 números aleatorios (es decir, size_t random[8][256] ), luego usar cada porción de 8 bits / 1 byte de la representación de la memoria del double para indexar en una tabla diferente, XORRE los números aleatorios que busca. Con este enfoque, es fácil ver que un poco de cambio en cualquier lugar en el double resulta en un número aleatorio diferente que se busca en una de las tablas, y un valor final totalmente no correlacionado.

Aún así, muchas funciones de hashing de bibliotecas pasan de enteros sin cambios, lo que es extremadamente propenso a colisiones en los peores casos, pero la esperanza es que en el caso bastante común de las claves de enteros que tienden a incrementarse, se asignarán en grupos sucesivos dejando menos está vacío que el 36.8% de las hojas aleatorias de hashing, por lo que tiene menos colisiones y menos listas enlazadas más largas de elementos de colisión que lo que se logra mediante asignaciones aleatorias. También es genial ahorrar el tiempo que lleva generar un hash fuerte. Cuando las claves no aumentan bien, la esperanza es que sean lo suficientemente aleatorias que no necesiten una función hash fuerte para aleatorizar totalmente su ubicación en los cubos.

Bueno, eso fue menos divertido y más pesado que la explicación de la tabla hash, pero espero que ayude a alguien ...

Para todos aquellos que buscan lenguaje de programación, aquí está cómo funciona. La implementación interna de tablas hash avanzadas tiene muchas complejidades y optimizaciones para la asignación / desasignación y búsqueda de almacenamiento, pero la idea de nivel superior será muy parecida.

(void) addValue : (object) value { int bucket = calculate_bucket_from_val(value); if (bucket) { //do nothing, just overwrite } else //create bucket { create_extra_space_for_bucket(); } put_value_into_bucket(bucket,value); } (bool) exists : (object) value { int bucket = calculate_bucket_from_val(value); return bucket; }

donde calculate_bucket_from_val() es la función de hashing donde toda la magia de unicidad debe suceder.

La regla de oro es: para que se inserte un valor dado, el cubo debe ser ÚNICO Y DERIVABLE DEL VALOR que se supone que debe almacenar.

Bucket es cualquier espacio donde se almacenan los valores, ya que aquí lo he mantenido como un índice de matriz, pero quizás también como una ubicación de memoria.

Todas las respuestas hasta el momento son buenas y abordan diferentes aspectos de cómo funciona una tabla hash. Aquí hay un ejemplo simple que podría ser útil. Digamos que queremos almacenar algunos elementos con cadenas alfabéticas en minúsculas como teclas.

Como explicó Simon, la función hash se usa para mapear desde un espacio grande a un espacio pequeño. Una implementación simple e ingenua de una función hash para nuestro ejemplo podría tomar la primera letra de la cadena y asignarla a un entero, por lo que "caimán" tiene un código hash de 0, "bee" tiene un código hash de 1 " cebra "sería 25, etc.

A continuación, tenemos una matriz de 26 cubos (podrían ser ArrayLists en Java), y colocamos el elemento en el cubo que coincide con el código hash de nuestra clave. Si tenemos más de un elemento que tiene una clave que comienza con la misma letra, tendrán el mismo código hash, por lo que todos irían en el cubo para ese código hash, por lo que habría que realizar una búsqueda lineal en el cubo para encontrar un elemento en particular

En nuestro ejemplo, si tuviéramos unas pocas docenas de elementos con teclas que abarcan el alfabeto, funcionaría muy bien. Sin embargo, si tuviéramos un millón de artículos o todas las claves comenzaran con ''a'' o ''b'', entonces nuestra tabla hash no sería ideal. Para obtener un mejor rendimiento, necesitaríamos una función hash diferente y / o más depósitos.

Tomas un montón de cosas, y una matriz.

Para cada cosa, creas un índice para ello, llamado hash. Lo importante del hash es que se ''dispersa'' mucho; no quieres que dos cosas similares tengan hashes similares.

Usted pone sus cosas en la matriz en la posición indicada por el hash. Más de una cosa puede terminar en un hash dado, por lo que almacena las cosas en arreglos u otra cosa apropiada, que generalmente llamamos un cubo.

Cuando buscas cosas en el hash, sigues los mismos pasos, averiguas el valor del hash, luego ves lo que hay en el cubo en esa ubicación y verificas si es lo que estás buscando.

Cuando su hash esté funcionando bien y su matriz sea lo suficientemente grande, solo habrá algunas cosas como máximo en cualquier índice particular de la matriz, por lo que no tendrá que mirar mucho.

Para obtener puntos de bonificación, asegúrese de que cuando se accede a su tabla hash, se mueva lo encontrado (si lo hubiera) al principio del grupo, de modo que la próxima vez sea lo primero que se verifique.

Una tabla hash funciona totalmente en el hecho de que los cálculos prácticos siguen el modelo de máquina de acceso aleatorio, es decir, se puede acceder al valor en cualquier dirección en la memoria en tiempo O (1) o tiempo constante.

Entonces, si tengo un universo de claves (conjunto de todas las claves posibles que puedo usar en una aplicación, por ejemplo, número de registro para el estudiante, si son 4 dígitos, este universo es un conjunto de números del 1 al 9999), y La forma de asignarlos a un conjunto finito de números de tamaño Puedo asignar memoria en mi sistema, en teoría, mi tabla hash está lista.

Generalmente, en las aplicaciones, el tamaño del universo de claves es muy grande que el número de elementos que quiero agregar a la tabla hash (no quiero desperdiciar una memoria de 1 GB en hash, por ejemplo, 10000 o 100000 valores enteros porque son 32 Un poco largo en la repetición binaria). Por lo tanto, utilizamos este hash. Es una especie de mezcla de operación "matemática", que mapea mi gran universo a un pequeño conjunto de valores que puedo acomodar en la memoria. En casos prácticos, a menudo el espacio de una tabla hash es del mismo "orden" (big-O) que el (número de elementos * tamaño de cada elemento), por lo tanto, no desperdiciamos mucha memoria.

Ahora, un conjunto grande asignado a un conjunto pequeño, la asignación debe ser de varios a uno. Así, diferentes claves se asignarán al mismo espacio (?? no es justo). Hay algunas maneras de manejar esto, solo conozco a los dos populares:

Utilice el espacio que se asignaría al valor como una referencia a una lista vinculada. Esta lista vinculada almacenará uno o más valores, que residen en la misma ranura en muchos mapeos. La lista enlazada también contiene claves para ayudar a alguien que viene a buscar. Es como muchas personas en el mismo apartamento, cuando llega un repartidor, él va a la habitación y pregunta específicamente por el tipo.
Utilice una función de doble hash en una matriz que proporciona la misma secuencia de valores cada vez en lugar de un solo valor. Cuando voy a almacenar un valor, veo si la ubicación de memoria requerida está libre u ocupada. Si es gratis, puedo almacenar mi valor allí, si está ocupado tomo el siguiente valor de la secuencia y así sucesivamente hasta que encuentre una ubicación libre y guarde mi valor allí. Cuando busco o recupero el valor, vuelvo por el mismo camino dado por la secuencia y en cada ubicación pregunte por el valor si está allí hasta que lo encuentre o busque todas las ubicaciones posibles en la matriz.

Introducción a los algoritmos por CLRS proporciona una muy buena visión sobre el tema.

Uso y Lingo:

Las tablas hash se utilizan para almacenar y recuperar rápidamente datos (o registros).
Los registros se almacenan en cubos utilizando claves hash
Las claves de hash se calculan aplicando un algoritmo de hash a un valor elegido contenido dentro del registro. Este valor elegido debe ser un valor común a todos los registros.
Cada cubo puede tener múltiples registros que están organizados en un orden particular.

Ejemplo del mundo real:

Hash & Co. , fundada en 1803 y sin tecnología informática, tenía un total de 300 archivadores para mantener la información detallada (los registros) de sus aproximadamente 30,000 clientes. Cada carpeta de archivo se identificó claramente con su número único de 0 a 299.

Los empleados de archivo de esa época tuvieron que buscar y almacenar rápidamente los registros de los clientes para el personal de trabajo. El personal había decidido que sería más eficiente utilizar una metodología de hashing para almacenar y recuperar sus registros.

Para archivar un registro de cliente, los empleados de archivo usarían el número de cliente único escrito en la carpeta. Usando este número de cliente, modularían la clave hash en 300 para identificar el archivador en el que se encuentra. Cuando abrieron el archivador, descubrirían que contenía muchas carpetas ordenadas por número de cliente. Después de identificar la ubicación correcta, simplemente la introducirían.

Para recuperar un registro del cliente, a los encargados de archivar se les daría un número de cliente en una hoja de papel. Usando este número de cliente único, lo modularían en 300 (la clave hash ) para determinar qué archivador tenía la carpeta de clientes. Cuando abrían el archivador, descubrían que contenía muchas carpetas ordenadas por número de cliente. Buscando en los registros, encontrarían rápidamente la carpeta del cliente y la recuperarían.

En nuestro ejemplo del mundo real, nuestros cubos son archivadores y nuestros registros son carpetas de archivos .

Es importante recordar que las computadoras (y sus algoritmos) manejan los números mejor que las cadenas. Por lo tanto, acceder a una matriz grande utilizando un índice es mucho más rápido que acceder de forma secuencial.

Como Simon ha mencionado, lo que creo que es muy importante es que la parte de hash es transformar un espacio grande (de longitud arbitraria, generalmente cadenas, etc.) y mapearlo en un espacio pequeño (de tamaño conocido, generalmente números) para la indexación. Esto es muy importante para recordar!

Entonces, en el ejemplo anterior, los 30,000 clientes posibles se asignan a un espacio más pequeño.

La idea principal de esto es dividir todo su conjunto de datos en segmentos para acelerar la búsqueda real, que suele llevar mucho tiempo. En nuestro ejemplo anterior, cada uno de los 300 archivadores contendría (estadísticamente) alrededor de 100 registros. La búsqueda (independientemente del orden) a través de 100 registros es mucho más rápida que tener que lidiar con 30,000.

Es posible que hayas notado que algunos ya lo hacen. Pero en lugar de idear una metodología de hash para generar una clave de hash, en la mayoría de los casos simplemente usarán la primera letra del apellido. Entonces, si tiene 26 archivadores, cada uno con una letra de la A a la Z, en teoría, acaba de segmentar sus datos y mejorado el proceso de archivo y recuperación.

Espero que esto ayude,

Jeach

Ustedes están muy cerca de explicar esto completamente, pero faltan un par de cosas. La tabla hash es solo una matriz. La matriz en sí contendrá algo en cada ranura. Como mínimo, almacenará el valor hash o el valor en sí mismo en esta ranura. Además de esto, también puede almacenar una lista enlazada / encadenada de valores que han colisionado en esta ranura, o puede usar el método de direccionamiento abierto. También puede almacenar un puntero o punteros a otros datos que desee recuperar fuera de esta ranura.

Es importante tener en cuenta que el valor hash en sí mismo generalmente no indica la ranura en la que se coloca el valor. Por ejemplo, un valor de hash puede ser un valor entero negativo. Obviamente, un número negativo no puede apuntar a una ubicación de matriz. Además, los valores de hash tenderán a ser muchas veces números más grandes que las ranuras disponibles. Por lo tanto, la propia tabla hash debe realizar otro cálculo para determinar a qué ranura debe ir el valor. Esto se hace con una operación matemática de módulo como:

uint slotIndex = hashValue % hashTableSize;

Este valor es la ranura en la que entrará el valor. En el direccionamiento abierto, si la ranura ya está llena con otro valor hash y / u otros datos, la operación de módulo se ejecutará una vez más para encontrar la siguiente ranura:

slotIndex = (remainder + 1) % hashTableSize;

Supongo que puede haber otros métodos más avanzados para determinar el índice de ranura, pero este es el más común que he visto ... estaría interesado en otros que funcionen mejor.

Con el método de módulo, si tiene una tabla de dicho tamaño 1000, cualquier valor hash que esté entre 1 y 1000 entrará en la ranura correspondiente. Cualquier valor negativo y cualquier valor superior a 1000 posiblemente colisionarán con valores de ranura. Las posibilidades de que eso suceda dependen de su método de hash, así como de la cantidad de elementos que agregue a la tabla de hash. En general, es una buena práctica hacer el tamaño de la tabla hash tal que el número total de valores agregados a ella sea igual a aproximadamente el 70% de su tamaño. Si su función hash hace un buen trabajo de distribución uniforme, generalmente encontrará muy pocas o ninguna colisión entre casillas / ranuras y funcionará muy rápidamente para las operaciones de búsqueda y escritura. Si el número total de valores a agregar no se conoce de antemano, haga una buena estimación utilizando cualquier medio y luego cambie el tamaño de su tabla hash una vez que la cantidad de elementos agregados alcance el 70% de la capacidad.

Espero que esto haya ayudado.

PS: en C #, el método GetHashCode() es bastante lento y produce colisiones de valores reales en muchas condiciones que he probado. Para un poco de diversión real, cree su propia función hash e intente que NUNCA colisione con los datos específicos que está procesando, ejecute más rápido que GetHashCode y tenga una distribución bastante uniforme. He hecho esto usando valores hashcode largos en lugar de tamaño int y funcionó bastante bien en hasta 32 millones de hash valores en la tabla hash con 0 colisiones. Desafortunadamente no puedo compartir el código ya que pertenece a mi empleador ... pero puedo revelar que es posible para ciertos dominios de datos. Cuando puedes lograr esto, la tabla hash es MUY rápida. :)