Descripción general de la tabla hash simple
Como actualización, una tabla hash es una forma de almacenar un valor bajo una clave específica en una estructura de datos. Por ejemplo, podría almacenar el valor "a"debajo de la clave 1y luego recuperarlo buscando la clave 1en la tabla hash.
El ejemplo más simple de una tabla hash que se me ocurre fuera de mi cabeza es una tabla hash que solo puede almacenar enteros, donde la clave para la entrada de la tabla hash también es el valor que se está almacenando. Digamos que su tabla es de tamaño 8, y es básicamente una matriz en la memoria:
---------------------------------
| | | | | | | | |
---------------------------------
0 1 2 3 4 5 6 7
Función hash
Las funciones hash le dan un índice sobre dónde almacenar su valor. Una función hash bastante simple para esta tabla sería agregar 1 al valor que desea almacenar y luego modificarlo en 8 (el tamaño de la tabla). En otras palabras, su función hash es (n+1)%8dónde nestá el número entero que desea almacenar.
Inserta
Si desea insertar un valor en esta tabla hash, llame a su función hash (en este caso (n+1)%8) sobre el valor que desea insertar para obtener un índice. Por ejemplo, si queremos insertar 14, llamaríamos (14 + 1) % 8y obtendríamos índice 7, por lo que insertaríamos el valor en index 7.
---------------------------------
| | | | | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Del mismo modo, podemos insertar 33, 82 y 191 así:
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Colisiones
Pero, ¿qué sucede si intentamos insertar algo que colisionaría con una entrada? 2 debe ir en el índice 3, pero está en 82. Hay varias formas de resolver este problema, la más simple es llamar a nuestra función hash una y otra vez hasta que encontremos un espacio vacío.
Entonces la lógica es la siguiente:
- (2 + 1)% 8 = 3
- El índice 3 está lleno
- Vuelva a enchufar 3 en nuestra función hash. ( 3 + 1)% 8 = 4 , que está vacío.
- Coloque nuestro valor en el índice 4 .
Ahora la tabla hash se ve así, con el valor 2 almacenado en el índice 4.
---------------------------------
|191| |33 |82 |2 | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
La desventaja de esta solución es que muy pronto, ¡nuestra mesa se llenará! Si sabe que el tamaño de sus datos es limitado, esto no debería ser un problema siempre que su tabla sea lo suficientemente grande como para contener todos los valores posibles. Si desea poder sostener más, puede manejar las colisiones de manera diferente. Volvamos a donde estábamos antes de insertar 2.
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Si recuerda, (2+1)%8nos da un índice 3, que se toma. Si no desea que se llene su tabla hash, puede usar cada índice de la tabla como una lista vinculada y agregarla a la lista en ese índice. Entonces, en lugar de llamar a la función hash nuevamente, simplemente agregaremos a la lista en el índice 3:
-----
| 2 |
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Esta lista puede crecer tanto como lo permita la memoria. Puedo insertar 18, y solo se agregará a 2:
-----
|18 |
-----
| 2 |
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Búsquedas
La búsqueda de valores en su tabla hash es rápida, dado que su tabla hash es de un tamaño bastante grande. Simplemente llame a su función hash y obtenga el índice. Digamos que quieres ver si 82 está en tu mesa. La función de búsqueda llamaría (82+1)%8= 3, y miraría el elemento en el índice 3, y lo devolvería por usted. Si buscó 16, la función de búsqueda se vería en el índice 1y vería que no existe.
¡Las búsquedas también necesitan manejar colisiones!
Si intenta buscar el valor 2, su tabla hash tendría que usar la misma lógica de colisión que usó para almacenar los datos que para recuperarlos. Dependiendo de la forma en que funcione su tabla hash, puede cambiar la clave una y otra vez hasta encontrar la entrada que está buscando (o encontrar un espacio en blanco), o puede recorrer su lista vinculada hasta encontrar el elemento (o llegó al final de la lista)
Resumen
Por lo tanto, las tablas hash son una buena forma de almacenar y acceder rápidamente a pares clave-valor. En este ejemplo, utilizamos la misma clave que el valor, pero en las tablas hash del mundo real las claves no son tan limitadas. Las funciones de hash funcionarán en las teclas para generar un índice, y luego la clave / valor se puede almacenar en ese índice. Las tablas hash en realidad no están destinadas a ser iteradas, aunque es posible hacerlo. Como puede ver, las tablas hash pueden tener muchos espacios en blanco, y recorrerlas sería una pérdida de tiempo. Incluso si la tabla hash tiene lógica para omitir las búsquedas de espacios en blanco en su iterador, sería mejor utilizar una estructura de datos diseñada para iteradores, como listas vinculadas.
Imagina una biblioteca con miles de libros. Debe organizar los libros para poder encontrarlos por título lo más rápido posible.
Una forma (común) de hacer esto es ordenar los libros alfabéticamente. Si su título comienza con "G", encontrará el área "G", luego busque la segunda letra, diga "ö", luego "d", "e", "l", reduzca la búsqueda, etc. , hasta que encuentres el libro. Sin embargo, esto puede llevar mucho tiempo y, además, cuando llegan nuevos libros, a veces necesita reorganizar su diseño para dejar espacio a los recién llegados.
Esa es la búsqueda binaria. Es bueno.
Sin embargo, hay una forma más rápida de hacerlo. Digamos que enumera todas las estanterías y estanterías, y luego para cada libro calcula un número especial, con suerte único, que se asigna a una estantería / estantería donde se debe encontrar el libro. La forma de calcular la "clave" no importa mucho, siempre y cuando proporcione un número de aspecto aleatorio. Por ejemplo, podría agregar códigos de caracteres de todas las letras en el título y luego dividirlo por algún número primo (posiblemente no sea el mejor método, pero funciona de todos modos).
Eso es hashing. Es mucho más rápido, porque no necesita revisar estanterías y estanterías enteras para buscar la siguiente letra del título. El hash generalmente es una operación de una sola vez, a menos que tenga una "colisión" cuando dos o más libros resuelven la misma clave. Pero está bien, sabes que se encuentran uno al lado del otro y, dependiendo de la calidad de la función hash, no debería haber demasiados bajo la misma tecla.
Las tablas hash tienen algunas limitaciones y caprichos (rehashing / redimensionamiento), lo que mantiene la búsqueda binaria como un competidor viable. No todo es blanco y negro con respecto a qué método es mejor. Pero esa es una historia diferente.
PD Perdón por no responder su pregunta directamente (escriba una tabla hash en PHP), pero eso es detalles y se llama "programación";)
fuente
La tabla hash en PHP, hasta donde yo sé, simplemente se implementa a través de:
Luego accede a los datos a través de llamadas como:
Utiliza la función foreach () para iterar sobre el contenido de la matriz.
La mejor manera de entender las tablas hash es leer algo como http://en.wikipedia.org/wiki/Hash_table , pero más o menos se reduce a esto: el lado izquierdo de cada línea dentro de esa llamada a la matriz () son las claves . Estas claves se someterán a un cálculo hash y el resultado es un hash. Probablemente hayas visto hashes MD5 o SHA antes, se parece bastante a esto. Una parte específica de este hash, generalmente los primeros caracteres X, pero a veces el hash completo, se utilizará para identificar los llamados 'cubos', que son las áreas de almacenamiento de los valores (el lado derecho).
Luego, cada vez que acceda a su tabla hash, use la tecla para obtener el valor. La clave se calcula de nuevo en un hash y el hash se usa para buscar rápidamente el valor asociado. Por lo tanto, las tablas hash permiten una búsqueda más rápida que solo buscar lineal si todo se acaba de almacenar. El único inconveniente es que algunas implementaciones de hash sufren colisiones, que es el mismo hash calculado para dos claves diferentes. En general, no es algo de lo que deba preocuparse demasiado.
Espero que esto proporcione algunos antecedentes, pero intente leer más sobre el tema si está interesado en él. Mi explicación es muy rudimentaria y estoy seguro de que hay suficientes agujeros allí, pero debería ser suficiente para una explicación rápida.
fuente