Estoy buscando una explicación de cómo funciona una tabla hash, ¡en inglés simple para un tonto 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 determinar dónde se encuentra en la matriz donde se almacena el valor, pero ahí es donde se detiene mi conocimiento .

¿Alguien podría aclarar el proceso?

Editar: no estoy preguntando específicamente 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 simples.

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

Entonces, usted decide que si la persona que quiere leer un libro sabe el título del libro y el título exacto para arrancar, entonces eso es todo lo que debe tomar. Con el título, la persona, con la ayuda del bibliotecario, debería poder encontrar el libro fácil y rápidamente.

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. De acuerdo, 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.

Desea algo que, con el título del libro, pueda darle el lugar correcto de una vez, por lo que todo lo que tiene que hacer es caminar hasta el estante correcto y recoger el libro.

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

En lugar de comenzar a llenar la biblioteca de un extremo al 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 alimenta el título a través del programa una vez más, y obtiene el mismo número de estante y número de ranura que le dieron originalmente, y esto es donde se encuentra el libro.

El programa, como otros ya han mencionado, se llama 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 solo convierte cada letra y símbolo en un número y los resume todos. En realidad, es mucho más complicado que eso, pero dejémoslo así por ahora.

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

Ok, así es básicamente cómo funciona una tabla hash.

Lo técnico sigue.

Primero, está el tamaño del número. Por lo general, la salida de dicho algoritmo hash está dentro de un rango de algún número grande, 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 contabas el número que querías (es decir, el número de mil millones) pero querías mantenerte dentro de un rango mucho más pequeño, cada vez que alcanzas el límite de ese rango más pequeño, comienzas de nuevo en 0, pero debes hacer un seguimiento de cuán lejos has llegado en la gran secuencia.

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, usted cuenta 1, 2, 3, 4, 5, 6 y cuando llega a 7, comienza de nuevo en 0. Dado 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 así, se hace con la división y el resto. El resto de dividir 17 entre 7 es 3 (7 va 2 veces en 17 a 14 y la diferencia entre 17 y 14 es 3).

Por lo tanto, pones el libro en la ranura número 3.

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

Existen varios métodos de manejo de colisiones, incluida la ejecución de los datos en otro cálculo para obtener otro lugar en la tabla ( doble hashing ), o simplemente para encontrar un espacio cercano al que le dieron (es decir, justo al lado del libro anterior asumiendo el espacio estaba disponible también conocido como sondeo lineal ). Esto significaría que tienes que cavar 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 los que la biblioteca permite. En otras palabras, necesita 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 deduce que si cambia el tamaño de la biblioteca, es posible que tenga que encontrar nuevos lugares para todos los libros, ya que el cálculo se realizó para encontrar sus lugares ha cambiado.

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

Uso y jerga:

1. Las tablas hash se utilizan para almacenar y recuperar datos (o registros) rápidamente.
2. Los registros se almacenan en cubos utilizando claves hash
3. Las claves hash se calculan aplicando un algoritmo hash a un valor elegido (el valor clave ) contenido en el registro. Este valor elegido debe ser un valor común para todos los registros.
4. Cada depósito puede tener múltiples registros que se organizan 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 archivos estaba claramente identificada con su número de cliente, un número único de 0 a 29,999.

Los empleados de archivo de esa época tuvieron que buscar y almacenar rápidamente registros de clientes para el personal de trabajo. El personal había decidido que sería más eficiente utilizar una metodología de hash 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. Utilizando este número de cliente, modularían la clave hash en 300 para identificar el archivador en el que se encuentra. Cuando abran el archivador, descubrirán que contiene muchas carpetas ordenadas por número de cliente. Después de identificar la ubicación correcta, simplemente la introducirían.

Para recuperar un registro de cliente, los empleados de archivo recibirían un número de cliente en una hoja de papel. Usando este número de cliente único (la clave hash ), lo modularían en 300 para determinar qué archivador tenía la carpeta de clientes. Cuando abrieran el archivador descubrirían que contenía muchas carpetas ordenadas por número de cliente. Al buscar 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 .

Una cosa importante para recordar es que las computadoras (y sus algoritmos) manejan los números mejor que las cadenas. Por lo tanto, acceder a una gran matriz usando un índice es significativamente mucho más rápido que acceder secuencialmente.

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

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

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

Es posible que haya notado que algunos ya lo hacen. Pero en lugar de idear una metodología de hash para generar una clave 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!

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

Esencialmente, una función hash es solo una función que toma cosas de un espacio (digamos cadenas de longitud arbitraria) y las asigna a un espacio útil para indexar (enteros sin signo, por ejemplo).

Si solo tiene un pequeño espacio de cosas para hacer hash, puede salirse con la suya interpretando esas cosas como enteros, y ya está (por ejemplo, cadenas de 4 bytes)

Por lo general, 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 (sus uint32 o lo que sea), entonces no puede tener un valor único para cada uno. Cuando dos o más cosas tienen el mismo resultado, tendrá que manejar la redundancia de una manera adecuada (esto generalmente se conoce como una colisión, y cómo lo maneje o no dependerá un poco de lo que sea usando el hash para).

Esto implica que desea que sea poco 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 ocupada a muchas personas!

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

Ahora para que esto funcione como una tabla hash: imagina que no te importa el uso de la memoria. Luego puede crear una matriz siempre que su conjunto de indexación (todos los uint32, por ejemplo). A medida que agrega algo a la tabla, cambia la clave y mira la matriz en ese índice. Si no hay nada allí, pones tu valor allí. Si ya hay algo allí, agrega 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.

Entonces, a medida que avanza mucho, cada entrada en su tabla hash (la matriz) está vacía o contiene una entrada o una lista de entradas. La recuperación es tan simple como indexar en la matriz y devolver el valor o recorrer la lista de valores y devolver el correcto.

Por supuesto, en la práctica, normalmente no puede hacer esto, desperdicia demasiada memoria. Por lo tanto, todo se basa en una matriz dispersa (donde las únicas entradas son las que realmente usa, todo lo demás es implícitamente nulo).

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

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 vinculadas. Si imaginamos una tabla que almacena los nombres de las personas, después de algunas inserciones, se puede 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 depósito y comienza una lista de valores ( posiblemente vacía) vinculada (también conocidos como elementos , en este ejemplo, nombres de personas )
• cada valor (por ejemplo, "fred"con hash 42) está vinculado desde el depósito, [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 depósito, 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 hash son los mismos (por ejemplo, "fred"y "jane"ambos se muestran con el hash 42arriba)
  • la mayoría de las tablas hash manejan las colisiones, con un rendimiento ligeramente reducido pero sin confusión funcional, al comparar el valor completo (aquí texto) de un valor que se busca o se inserta con cada valor que ya está en la lista vinculada en el depósito hash-to

Las longitudes de la lista vinculada se relacionan con el factor de carga, no con el número de valores

Si el tamaño de la tabla aumenta, las tablas hash implementadas como las anteriores tienden a redimensionarse (es decir, crear una matriz más grande de cubos, crear listas vinculadas nuevas / actualizadas, eliminar la matriz anterior) para mantener la relación de valores a cubetas (también conocida como carga factor ) en algún lugar en el rango de 0.5 a 1.0.

Hans proporciona la fórmula real para otros factores de carga en un comentario a continuación, pero para valores indicativos: con el factor de carga 1 y una función hash de fuerza criptográfica, 1 / e (~ 36.8%) de los cubos tenderán a estar vacíos, otro 1 / e (~ 36.8%) tienen un elemento, 1 / (2e) o ~ 18.4% dos elementos, 1 / (3! E) aproximadamente 6.1% tres elementos, 1 / (4! E) o ~ 1.5% cuatro elementos, 1 / (5! E) ~ .3% tiene cinco, etc. - la longitud promedio de la cadena de los cubos no vacíos es ~ 1.58 sin importar cuántos elementos hay en la tabla (es decir, si hay 100 elementos y 100 cubos, o 100 millones elementos y 100 millones de cubos), por eso decimos que buscar / insertar / borrar son O (1) operaciones de tiempo constante.

Cómo una tabla hash puede asociar claves con valores

Dada una implementación de tabla hash como se describió anteriormente, podemos imaginar la creación de un tipo de valor como struct Value { string name; int age; };, y la comparación de igualdad y funciones hash que solo miran el namecampo (ignorando la edad), y luego sucede algo maravilloso: podemos almacenar Valueregistros como {"sue", 63}en la tabla , luego busque "demandar" sin saber su edad, encuentre el valor almacenado y recupere o incluso actualice su edad
, feliz cumpleaños Sue, que curiosamente no cambia el valor hash, por lo que no requiere que traslademos el registro de Sue a otro Cubeta.

Cuando hacemos esto, estamos usando la tabla hash como un contenedor asociativo, también conocido como mapa , y los valores que almacena pueden considerarse como una clave (el nombre) y uno o más campos aún denominados, de manera confusa, el valor ( en mi ejemplo, solo la edad). Una implementación de tabla hash utilizada como mapa se conoce como mapa hash .

Esto contrasta con el ejemplo anterior en esta respuesta donde almacenamos valores discretos como "demandar", que podría considerarse como su propia clave: ese tipo de uso se conoce como un conjunto de hash .

Hay otras formas de implementar una tabla hash

No todas las tablas hash usan listas vinculadas (conocidas como encadenamiento separado ), pero la mayoría de las de uso general lo hacen, ya que el hashing cerrado alternativo principal (también conocido como direccionamiento abierto ) , particularmente con operaciones de borrado compatibles, tiene propiedades de rendimiento menos estables con teclas propensas a colisiones / funciones hash.

Algunas palabras sobre funciones hash

Hash fuerte ...

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 manera efectiva al azar, mientras que siempre genera el mismo valor hash para la misma clave. Incluso un bit que cambia en cualquier parte de la clave idealmente, al azar, voltea aproximadamente la mitad de los bits en el valor hash resultante.

Esto normalmente está orquestado con matemáticas demasiado complicadas para que pueda asimilarlas. Mencionaré una forma fácil de entender, no la más escalable o amigable con la caché, sino intrínsecamente elegante (¡como el cifrado con una almohadilla única!), Ya que creo que ayuda a llevar a casa las cualidades deseables mencionadas anteriormente. Supongamos que estaba utilizando hash de 64 bits double: puede crear 8 tablas de 256 números aleatorios (código a continuación), luego usar cada segmento de 8 bits / 1 byte de la doublerepresentación de memoria del s para indexar en una tabla diferente, XOR números aleatorios que buscas. Con este enfoque, es fácil ver que un bit (en el sentido de los dígitos binarios) cambia en cualquier parte de los doubleresultados en un número aleatorio diferente que se busca en una de las tablas y un valor final totalmente no correlacionado.

// note caveats above: cache unfriendly (SLOW) but strong hashing...
size_t random[8][256] = { ...random data... };
const char* p = (const char*)&my_double;
size_t hash = random[0][p[0]] ^ random[1][p[1]] ^ ... ^ random[7][p[7]];

Hash débil pero a menudo rápido ...

Las funciones de hash de muchas bibliotecas pasan enteros sin cambios (conocido como una función hash trivial o de identidad ); Es el otro extremo del fuerte hashing descrito anteriormente. Un hash de identidad es extremadamentepropensos a colisiones en los peores casos, pero la esperanza es que, en el caso bastante común de las teclas enteras que tienden a incrementarse (tal vez con algunos huecos), se mapearán en cubos sucesivos dejando menos hojas vacías que hashing aleatorias (nuestro ~ 36.8 % en el factor de carga 1 mencionado anteriormente), por lo que tiene menos colisiones y menos listas enlazadas más largas de elementos en colisión que lo que se consigue mediante asignaciones aleatorias. También es excelente para ahorrar el tiempo que lleva generar un hash fuerte, y si las claves se buscan en orden, se encontrarán en cubos cercanos en la memoria, mejorando los aciertos de caché. Cuando las teclas no se incrementan bien, la esperanza es que sean lo suficientemente aleatorias como para que no necesiten una función hash fuerte para aleatorizar totalmente su ubicación en cubos.

Ustedes están muy cerca de explicar esto completamente, pero se pierden 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 este espacio. Además de esto, también puede almacenar una lista vinculada / encadenada de valores que han colisionado en este espacio, o puede usar el método de direccionamiento abierto. También puede almacenar un puntero o punteros a otros datos que desea recuperar de esta ranura.

Es importante tener en cuenta que el valor hash en sí mismo generalmente no indica la ranura en la que colocar el valor. Por ejemplo, un valor hash podría ser un valor entero negativo. Obviamente, un número negativo no puede apuntar a una ubicación de matriz. Además, los valores hash tenderán muchas veces a ser números mayores que los espacios disponibles. Por lo tanto, la tabla hash debe realizar otro cálculo para determinar en 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 el espacio en el que irá el valor. En direccionamiento abierto, si el espacio ya está lleno con otro valor hash y / u otros datos, la operación de módulo se ejecutará nuevamente para encontrar el siguiente espacio:

slotIndex = (remainder + 1) % hashTableSize;

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

Con el método de módulo, si tiene una tabla de digamos tamaño 1000, cualquier valor de hash que esté entre 1 y 1000 irá a la ranura correspondiente. Cualquier valor negativo y cualquier valor mayor que 1000 serán potencialmente colisionadores de ranuras. Las posibilidades de que eso ocurra dependen tanto de su método de hash como de la cantidad total de elementos que agregue a la tabla de hash. En general, es una buena práctica hacer que el tamaño de la tabla hash sea tal que el número total de valores agregados solo sea igual al 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 de cubetas / ranuras y funcionará muy rápidamente para las operaciones de búsqueda y escritura. Si el número total de valores para agregar no se conoce de antemano, haga una buena estimación utilizando cualquier medio,

Espero que esto haya ayudado.

PD: en C #, el GetHashCode()método es bastante lento y produce colisiones de valor real en muchas condiciones que he probado. Para divertirse de verdad, cree su propia función hash e intente que NUNCA choque 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 de código hash largos en lugar de int de tamaño y ha funcionado bastante bien en hasta 32 millones de valores hash 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. :)

Así es como funciona en mi entendimiento:

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

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

En cuanto al cálculo del código hash, no tiene nada de mágico. El objetivo es 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 que un código hash para todas las instancias, pero esencialmente destruiría la utilidad de una tabla hash, ya que se convertiría en un cubo gigante.

Corto y dulce:

Una tabla hash envuelve una matriz, vamos a llamarla 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 combinan con 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 haciendo internalArrayuna 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, las búsquedas y la eliminación de nuestro conjunto de listas vinculadas es casi O (1).

Cuando nuestra matriz interna se llena demasiado, tal vez a una capacidad de alrededor del 85%, podemos cambiar el tamaño de la matriz interna y mover todos los elementos de la matriz anterior a la nueva matriz.

Es incluso más simple que eso.

Una tabla hash no es más que una matriz (generalmente escasa ) 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 entran los vectores de almacenamiento de pares clave / valor en la matriz. Debido a que el conjunto de valores que pueden ser índices en la matriz suele ser menor 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 hash evitará esto tanto como sea posible (por lo que se relega al tipo generalmente porque tiene información específica que un algoritmo hash general no puede saber), pero es imposible de prevenir.

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

Tomas un montón de cosas y una gran variedad.

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

Pones tus cosas en la matriz en la posición indicada por el hash. Más de una cosa puede terminar en un hash determinado, por lo que almacena las cosas en matrices u otra cosa apropiada, que generalmente llamamos un cubo.

Cuando busca cosas en el hash, sigue los mismos pasos, calcula el valor del hash, luego ve lo que hay en el cubo en esa ubicación y verifica si es lo que está buscando.

Cuando su hashing funciona bien y su matriz es lo suficientemente grande, solo habrá algunas cosas como máximo en cualquier índice particular en 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, mueva lo encontrado (si lo hay) al comienzo del cubo, por lo que la próxima vez es lo primero que se verifica.

Todas las respuestas hasta ahora 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 claves.

Como explicó Simon, la función hash se utiliza para asignar 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 número entero, por lo que "cocodrilo" 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 depósitos (podrían ser ArrayLists en Java), y colocamos el elemento en el depósito 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 al cubo para ese código hash, por lo que habría que hacer una búsqueda lineal en el cubo para Encuentra un artículo en particular.

En nuestro ejemplo, si solo tuviéramos unas pocas docenas de elementos con claves que abarcaran el alfabeto, funcionaría muy bien. Sin embargo, si tuviéramos un millón de elementos 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.

Aquí hay otra forma de verlo.

Supongo que comprende el concepto de una matriz A. Eso es algo que respalda la operación de indexación, donde puede llegar al elemento Ith, A [I], en un solo paso, sin importar cuán grande sea A.

Entonces, por ejemplo, si desea almacenar información sobre un grupo de personas que tienen diferentes edades, una forma simple sería tener una matriz lo suficientemente grande y usar la edad de cada persona como un índice en la matriz. De cualquier manera, 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, por lo que lo que 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 "cubeta"). Solo se ralentiza si hay tanta gente que los cubos se hacen 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 la edad.

Esa es la idea básica. En lugar de usar la edad, se puede usar cualquier función de la persona que produzca una buena distribución de valores. Esa es la función hash. Como si pudieras tomar cada tercer bit de la representación ASCII del nombre de la persona, codificada en algún orden. Lo único que importa es que no quieres que demasiadas personas hagan el hash al mismo cubo, porque la velocidad depende de que los cubos permanezcan pequeños.

La forma en que se calcula el hash generalmente no depende de la tabla hash, sino de los elementos que se le agregan. En frameworks / bibliotecas de clases 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 ideal de código hash y la implementación exacta dependen de los datos representados en el objeto.

Una tabla hash funciona totalmente sobre el hecho de que el cálculo práctico sigue el modelo de máquina de acceso aleatorio, es decir, se puede acceder al valor en cualquier dirección en la memoria en O (1) tiempo 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, no. Para estudiante, si son 4 dígitos, entonces este universo es un conjunto de números del 1 al 9999), y un Para 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.

En general, 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, digamos, 10000 o 100000 valores enteros porque son 32 poco tiempo en la representación binaria). Entonces, usamos este hash. Es una especie de mezcla de operación "matemática", que asigna 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, el mapeo debe ser muchos a uno. Por lo tanto, se asignarán diferentes claves al mismo espacio (?? no es justo). Hay algunas maneras de manejar esto, solo conozco las dos populares:

• Use el espacio que debía asignarse al valor como referencia a una lista vinculada. Esta lista vinculada almacenará uno o más valores, que vienen a residir en la misma ranura en muchas asignaciones. La lista vinculada también contiene claves para ayudar a alguien que viene buscando. Es como muchas personas en el mismo departamento, cuando llega un repartidor, él va a la habitación y pregunta específicamente por el tipo.
• Use una función de doble hash en una matriz que proporcione 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 almacene mi valor allí. Cuando busco o recupero el valor, vuelvo a la misma ruta dada por la secuencia y en cada ubicación pregunto por el valor si está allí hasta que lo encuentre o busco todas las ubicaciones posibles en la matriz.

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

Para todos aquellos que buscan lenguaje de programación, así es como funciona. La implementación interna de tablas de hash avanzadas tiene muchas complejidades y optimizaciones para la asignación / desasignación de almacenamiento y la búsqueda, 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;
}

¿Dónde calculate_bucket_from_val()está la función hash donde debe ocurrir toda la magia de la unicidad?

La regla general es: para que se inserte un valor dado, el depósito debe ser ÚNICO Y DERIVABLE DEL VALOR que se supone que TIENE ALMACENAMIENTO.

Bucket es cualquier espacio donde se almacenan los valores, porque aquí lo he mantenido int como un índice de matriz, pero tal vez también sea una ubicación de memoria.