Los fundamentos de las tablas Hash?
https://stackoverflow.com/questions/282712
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy bastante confundido acerca de los conceptos básicos de una tabla Hash. Si tuviera que codificar un hash, ¿cómo comenzaría? ¿Cuál es la diferencia entre una tabla Hash y solo una matriz normal?
Básicamente, si alguien respondiera esta pregunta, creo que todas mis preguntas serían respondidas: Si tuviera 100 números generados aleatoriamente (como claves), ¿cómo implementaría una tabla hash y por qué sería ventajoso sobre una matriz?
Psuedo-code o Java serían apreciados como una herramienta de aprendizaje ...
Solución
Las respuestas hasta ahora han ayudado a definir tablas hash y explicar algo de teoría, pero creo que un ejemplo puede ayudarlo a tener una mejor idea de ellas.
¿Cuál es la diferencia entre una tabla hash y solo una matriz normal?
Una tabla hash y una matriz son estructuras que le permiten almacenar y recuperar datos. Ambos le permiten especificar un índice y recuperar un valor asociado a él. La diferencia, como observó Daniel Spiewak, es que los índices de una matriz son secuenciales , mientras que los de una tabla hash se basan en el valor de los datos asociados a ellos.
¿Por qué usaría una tabla hash?
Una tabla hash puede proporcionar una manera muy eficiente de buscar elementos en grandes cantidades de datos, particularmente datos que de otra manera no se pueden buscar fácilmente. (" Grande " aquí significa ginormous , en el sentido de que tomaría mucho tiempo realizar una búsqueda secuencial).
Si tuviera que codificar un hash, ¿cómo comenzaría?
No hay problema. La forma más sencilla es inventar una operación matemática arbitraria que pueda realizar en los datos, que devuelva un número N (generalmente un número entero). Luego use ese número como índice en una matriz de "cubos". y almacene sus datos en el depósito # N . El truco está en seleccionar una operación que tiende a colocar valores en diferentes cubos de una manera que le facilite encontrarlos más tarde.
Ejemplo: Un gran centro comercial mantiene una base de datos de los autos y lugares de estacionamiento de sus clientes, para ayudar a los compradores a recordar dónde estacionaron. La base de datos almacena make , color , matrícula y ubicación de estacionamiento . Al salir de la tienda, un comprador encuentra su automóvil ingresando su marca y color. La base de datos devuelve una lista (relativamente corta) de placas y espacios de estacionamiento. Un escaneo rápido localiza el auto del comprador.
Puede implementar esto con una consulta SQL:
SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"
Si los datos se almacenaron en una matriz, que es esencialmente una lista, puede imaginarse implementando la consulta escaneando una matriz en busca de todas las entradas coincidentes.
Por otro lado, imagine una regla hash:
Agregue los códigos de caracteres ASCII de todas las letras en la marca y el color, divida por 100 y use el resto como valor hash.
Esta regla convertirá cada elemento en un número entre 0 y 99, esencialmente ordenando los datos en 100 cubos. Cada vez que un cliente necesita localizar un automóvil, puede cambiar la marca y el color para encontrar el one cubo de cada 100 que contiene la información. ¡Inmediatamente redujo la búsqueda por un factor de 100!
Ahora escale el ejemplo a grandes cantidades de datos, digamos una base de datos con millones de entradas que se busca en base a decenas de criterios. A '' bueno '' la función hash distribuirá los datos en cubos de una manera que minimice cualquier búsqueda adicional, ahorrando una cantidad significativa de tiempo.
Otros consejos
Primero, debe comprender qué es una función hash. Una función hash es una función que toma una clave (por ejemplo, una cadena de longitud arbitraria) y devuelve un número lo más exclusivo posible . La misma clave siempre debe devolver el mismo hash. Una función de hash de cadena realmente simple en Java podría verse
public int stringHash(String s) {
int h = s.length();
for(char c : s.toCharArray()) {
h ^= c;
}
return h;
}
Puede estudiar una buena función hash en http://www.azillionmonkeys.com/qed/ hash.html
Ahora, el mapa hash usa este valor hash para colocar el valor en una matriz. Método simplista de Java:
public void put(String key, Object val) {
int hash = stringHash(s) % array.length;
if(array[hash] == null) {
array[hash] = new LinkedList<Entry<String, Object> >();
}
for(Entry e : array[hash]) {
if(e.key.equals(key)){
e.value = val;
return;
}
}
array[hash].add(new Entry<String, Object>(key, val));
}
(Este mapa aplica claves únicas. No todos los mapas lo hacen).
Es posible que dos claves diferentes se combinen con el mismo valor, o que dos hashes diferentes se asignen al mismo índice de matriz. Existen muchas técnicas para lidiar con esto. Lo más simple es usar una lista vinculada (o árbol binario) para cada índice de matriz. Si la función hash es lo suficientemente buena, nunca necesitará una búsqueda lineal.
Ahora para buscar una clave:
public Object get(String key) {
int hash = stringHash(key) % array.length;
if(array[hash] != null) {
for(Entry e : array[hash]) {
if(e.key.equals(key))
return e.value;
}
}
return null;
}
tablas hash son asociativas . Esta es una gran diferencia con respecto a las matrices, que son solo estructuras de datos lineales. Con una matriz, puede hacer algo como esto:
int[] arr = ...
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i] + 1);
}
Observe cómo obtiene un elemento de la matriz especificando un desplazamiento de memoria exacto ( i ). Esto contrasta con las tablas hash, que le permiten almacenar pares clave / valor, y luego recuperar el valor basado en la clave:
Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);
Con la tabla anterior, podemos hacer la siguiente llamada:
int n = table.get("Chris");
... y tenga la seguridad de que n se valorará en 18 .
Creo que esto probablemente responderá la mayoría de sus preguntas. La implementación de una tabla hash es un tema bastante interesante, uno que Wikipedia aborda muy bien .
" Estoy más interesado en la forma en que Hash Tables busca la clave y cómo se genera la clave. "
-
El hash transforma un objeto clave en un número. Esto se llama '' hashing '' - hace un hash del objeto. Consulte Hash Function . Sumar los bytes de una cadena, por ejemplo, es una técnica de hash estándar. Calcula la suma del módulo 2 32 para mantener el hash en un tamaño manejable. Hash siempre da la misma respuesta. Esto es O(1).
-
El número le da una "ranura" en la tabla hash. Dado un objeto clave arbitrario, el valor hash calcula un valor hash. El valor hash te da el espacio en la tabla. Por lo general,
mod (hash, tamaño de tabla). También es O (1).
Esa es la solución general. Dos cálculos numéricos y has pasado de un objeto arbitrario como clave a un objeto arbitrario como valor. Pocas cosas pueden ser tan rápidas.
La transformación de objeto a valor hash ocurre en una de estas formas comunes.
-
Si se trata de una "primitiva" objeto de 4 bytes, entonces el valor nativo del objeto es un número.
-
La dirección del objeto es de 4 bytes, luego la dirección del objeto se puede usar como un valor hash.
-
Una simple función hash (MD5, SHA1, lo que sea) acumula los bytes de el objeto para crear un número de 4 bytes. Los hashes avanzados no son sumas simples de bytes, una suma simple no refleja todos los bits de entrada originales de manera suficiente.
El espacio en la tabla hash es mod (número, tamaño de la tabla).
Si esa ranura tiene el valor deseado, ya está. Si ese no es el valor deseado, debe buscar en otro lugar. Existen varios algoritmos de sondeo populares para buscar un lugar libre en la tabla. Lineal es una búsqueda simple para el próximo lugar libre. Quadratic es un salto no lineal en busca de una ranura libre. Se puede utilizar un generador de números aleatorios (con una semilla fija) para generar una serie de sondas que distribuirán los datos de manera uniforme pero arbitraria.
Los algoritmos de sondeo no son O (1). Si la mesa es lo suficientemente grande, las probabilidades de colisión son bajas y las sondas no importan. Si la mesa es demasiado pequeña, se producen colisiones y se realiza un sondeo. En ese punto, se convierte en una cuestión de "ajuste y ajuste". para equilibrar el sondeo y el tamaño de la mesa para optimizar el rendimiento. Por lo general, solo hacemos que la mesa sea más grande.
Ver Hash Table .
Algo que no vi específicamente notado todavía:
El punto de usar una tabla hash sobre una matriz es el rendimiento.
Iterar a través de una matriz normalmente llevaría de O (1) a O (x) donde x es el número de elementos en la matriz. Sin embargo, el tiempo para encontrar su artículo será extremadamente variable , especialmente si estamos hablando de cientos de miles de artículos en la matriz.
Una tabla hash correctamente ponderada generalmente tiene un tiempo de acceso constante de poco más de O (1), sin importar cuántos elementos haya en la tabla hash.
No querrás usar una tabla hash para 100 números generados aleatoriamente.
Una buena manera de pensar en tablas hash es pensar en pares de valores. Usemos estudiantes y digamos que todos tienen un número de identificación de estudiante. En su programa, almacena información sobre los estudiantes (nombres, números de teléfono, facturas, etc.). Desea encontrar toda la información sobre un estudiante utilizando solo información básica (nombre o ID del estudiante, por ejemplo).
Digamos que tienes 10,000 estudiantes. Si los almacena todos en una matriz, debe recorrer toda la matriz comparando la ID de estudiante de cada entrada con la que está buscando.
Si, en cambio, usted '' hash '' (vea a continuación) su número de identificación de estudiante en una posición en la matriz, luego solo tiene que buscar los números de quién tienen el mismo hash. Mucho menos trabajo para encontrar lo que buscabas.
En este ejemplo, supongamos que las ID de los estudiantes son solo números de 6 dígitos. Nuestra función hash podría usarse solo los 3 dígitos inferiores del número como la tecla hash " ;. Por lo tanto, 232145 se ajusta a la ubicación de la matriz 145. Entonces, solo necesita una matriz de 999 elementos (cada elemento es una lista de estudiantes).
Eso debería ser un buen comienzo para ti. Por supuesto, debe leer un libro de texto o wikipedia para este tipo de información. Pero supongo que ya lo has hecho y estás cansado de leer.
Aquí está, en resumen, cómo funciona una tabla hash.
Imagina que tienes una biblioteca llena de libros. Si tuviera que almacenar los libros en una matriz, colocaría cada libro en un lugar en un estante, y luego, cuando alguien le pidiera que encontrara un libro, miraría a través de todos los estantes, bastante lento. Sin embargo, si alguien dijera "libro # 12345", podría encontrarlo con bastante facilidad.
Digamos, en cambio, usted dice, si el título del libro comienza con 'A', va en la fila 1. Si la segunda letra es 'B', va en la fila 1, estante 2. Si la tercera letra es 'C ', va en la fila 1, estante 2, estante 3 ... y así sucesivamente hasta que identifique la posición del libro. Luego, según el título del libro, podría saber exactamente dónde debería estar.
Ahora, hay algunos problemas en el hash simplista algoritmo que describí: algunos estantes estarán sobrecargados mientras que otros estarán vacíos, algunos libros se asignarán a la misma ranura ... por lo que las funciones hash reales se construyen cuidadosamente para tratar de evitar tales problemas.
Pero esta es la idea básica.
Contestaré esa parte sobre la diferencia entre una tabla hash y una matriz ... pero como nunca antes he implementado un algoritmo hash de ninguna importación, se lo dejaré a alguien con más conocimientos:)
Una matriz es solo una lista ordenada de objetos. El objeto en sí realmente no importa ... lo importante es que si desea enumerar los objetos en orden de inserción, siempre es el mismo (lo que significa que el primer elemento siempre tiene un índice de 0).
En cuanto a una tabla hash, que está indexada por teclas, no por orden ... Creo que una búsqueda básica en algoritmos de hash te dará mucha más información de la que puedo ... Wikipedia tiene una muy decente ... que determina " cubo " que las claves entran para una recuperación rápida en objetos arbitrarios utilizados como claves.
En cuanto a las ventajas: si el orden de inserción es importante, se necesita una matriz o algún tipo de lista ordenada. Si la búsqueda rápida por clave arbitraria (clave por varias funciones hash) es importante, entonces una tabla hash tiene sentido.
[Esta es la respuesta a un comentario hecho por me.yahoo.com/a arriba]
Eso depende de su función hash. Supongamos que su función hash codifica una palabra según la longitud de su palabra, la clave para chris será 5. De manera similar, la clave para yahoo también será 5. Ahora, ambos valores (chris y yahoo) irán por debajo de 5 (es decir, en un 'cubo' marcado por 5). De esta manera, no tiene que hacer una matriz igual al tamaño de sus datos.
La pregunta, creo, está respondida con bastante claridad y de muchas maneras diferentes por ahora.
Me gustaría agregar otra perspectiva (que también puede confundir a un nuevo lector)
En un nivel de mínima abstracción, las matrices son solo bloques contiguos de memoria. Dada la dirección inicial ( startAddress ), el tamaño ( sizeOfElement ) y el index de un solo elemento, la dirección del elemento se calcula como:
elementAddress = startAddress + sizeOfElement * index
Lo interesante a tener en cuenta aquí es que las matrices se pueden abstraer / ver como tablas hash con index como clave y la función anterior como una función hash que calcula la ubicación de un valor en O (1)
La tabla hash es una estructura de datos creada para una búsqueda rápida.
Las tablas hash no son efectivas cuando el número de entradas es muy pequeño.
Algunos ejemplos:
import java.util.Collection;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Set;
public class HashtableDemo {
public static void main(String args[]) {
// Creating Hashtable for example
Hashtable companies = new Hashtable();
// Java Hashtable example to put object into Hashtable
// put(key, value) is used to insert object into map
companies.put("Google", "United States");
companies.put("Nokia", "Finland");
companies.put("Sony", "Japan");
// Java Hashtable example to get Object from Hashtable
// get(key) method is used to retrieve Objects from Hashtable
companies.get("Google");
// Hashtable containsKey Example
// Use containsKey(Object) method to check if an Object exits as key in
// hashtable
System.out.println("Does hashtable contains Google as key: "+companies.containsKey("Google"));
// Hashtable containsValue Example
// just like containsKey(), containsValue returns true if hashtable
// contains specified object as value
System.out.println("Does hashtable contains Japan as value: "+companies.containsValue("Japan"));
// Hashtable enumeration Example
// hashtabl.elements() return enumeration of all hashtable values
Enumeration enumeration = companies.elements();
while (enumeration.hasMoreElements()) {
System.out.println("hashtable values: "+enumeration.nextElement());
}
// How to check if Hashtable is empty in Java
// use isEmpty method of hashtable to check emptiness of hashtable in
// Java
System.out.println("Is companies hashtable empty: "+companies.isEmpty());
// How to find size of Hashtable in Java
// use hashtable.size() method to find size of hashtable in Java
System.out.println("Size of hashtable in Java: " + companies.size());
// How to get all values form hashtable in Java
// you can use keySet() method to get a Set of all the keys of hashtable
// in Java
Set hashtableKeys = companies.keySet();
// you can also get enumeration of all keys by using method keys()
Enumeration hashtableKeysEnum = companies.keys();
// How to get all keys from hashtable in Java
// There are two ways to get all values form hashtalbe first by using
// Enumeration and second getting values ad Collection
Enumeration hashtableValuesEnum = companies.elements();
Collection hashtableValues = companies.values();
// Hashtable clear example
// by using clear() we can reuse an existing hashtable, it clears all
// mappings.
companies.clear();
}
}
Salida:
Does hashtable contains Google as key: true
Does hashtable contains Japan as value: true
hashtable values: Finland
hashtable values: United States
hashtable values: Japan
Is companies hashtable empty: false
Size of hashtable in Java: 3
