java - resolucion - tablas hash aplicaciones

Los fundamentos de las tablas Hash?

Question

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 se responderían todas mis preguntas: 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?

El código Psuedo o Java sería apreciado como una herramienta de aprendizaje ...

Answer 1

"Estoy más interesado en la forma en que Hash Tables busca la clave y cómo se genera la clave".

1. Hashing transforma un objeto clave en un número. Esto se llama "hash": hace un hash fuera del objeto. Ver la función Hash . Sumar los bytes de una cadena, por ejemplo, es una técnica hash estándar. Calcule la suma módulo 2 ³² para mantener el hash a un tamaño manejable. Hash siempre da la misma respuesta. Este es O (1).

2. El número le da un "espacio" en la tabla Hash. Dado un objeto clave arbitrario, el valor hash calcula un valor hash. El valor hash le da la ranura en la tabla. Por lo general, mod( hash, table size ) . Esto es O (1), también.

Esa es la solución general. Dos cálculos numéricos y ha pasado de objeto arbitrario como clave a objeto arbitrario como valor. Pocas cosas pueden ser tan rápidas.

La transformación del valor de objeto a hash ocurre en una de estas formas comunes.

1. Si se trata de un objeto "primitivo" de 4 bytes, entonces el valor nativo del objeto es un número.

2. La dirección del objeto es de 4 bytes, luego la dirección del objeto se puede usar como un valor hash.

3. Una simple función hash (MD5, SHA1, lo que sea) acumula los bytes del objeto para crear un número de 4 bytes. Los hash avanzados no son simples sumas de bytes, una suma simple no refleja todos los bits de entrada originales con la suficiente precisión.

La ranura en la tabla hash es mod (número, tamaño de la tabla).

Si ese espacio tiene el valor deseado, listo. Si ese no es el valor deseado, debe buscar en otro lugar. Hay varios algoritmos de sondeo populares para buscar un lugar libre en la tabla. Linear es una búsqueda simple para el siguiente lugar libre. Quadratic es un salto no lineal en busca de una ranura libre. Se puede usar un generador de números aleatorios (con una semilla fija) para generar una serie de sondeos que distribuirán los datos de manera uniforme pero arbitraria.

Los algoritmos de prueba no son O (1). Si la tabla 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 sucede una prueba. En ese punto, se convierte en una cuestión de "ajuste y ajuste" para equilibrar el sondeo y el tamaño de la tabla para optimizar el rendimiento. Usualmente hacemos que la mesa sea más grande.

Ver Tabla Hash .

Answer 2

Algo que no he visto específicamente anotado aún:

El objetivo de utilizar una tabla hash en una matriz es el rendimiento.

Iterar a través de una matriz típicamente llevaría desde O (1) a O (x) donde x es la cantidad de elementos en la matriz. Sin embargo, el momento de encontrar su artículo será extremadamente variable , especialmente si estamos hablando de cientos de miles de elementos en el conjunto.

Una tabla hash adecuadamente ponderada normalmente tiene un tiempo de acceso casi constante de algo más de O (1), sin importar cuántos elementos haya en la tabla hash.

Answer 3

Aquí está, en resumen, cómo funciona una tabla hash.

Imagina que tienes una biblioteca llena de libros. Si tuviera que guardar los libros en una matriz, colocaría cada libro en un lugar en un estante, y luego, cuando alguien le pidiera que buscara un libro, miraría a través de todos los estantes, bastante lento. Si alguien dijera "libro n. ° 12345", podría encontrarlo con bastante facilidad.

Digamos que en cambio dices, 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, en el estante 2, en el estante 3 ... y así sucesivamente hasta que identifica la posición del libro. Luego, según el título del libro, puedes saber exactamente dónde debería estar.

Ahora, hay algunos problemas en el algoritmo simplificado de "hashing" que describí: algunos estantes van a estar sobrecargados mientras otros permanecen vacíos, algunos libros serán asignados a la misma ranura ... por lo que las funciones hash reales están cuidadosamente construidas para trata de evitar tales problemas

Pero esta es la idea básica.

Answer 4

Las tablas hash son asociativas . Esta es una gran diferencia de 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 del conjunto al especificar 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á a los 18 .

Creo que esto probablemente responderá la mayoría de tus preguntas. La implementación de una tabla hash es un tema bastante interesante, que Wikipedia aborda muy bien .

Answer 5

No querrá 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 acerca de un estudiante utilizando solo información básica (nombre o ID de estudiante, por ejemplo).

Digamos que tienes 10,000 estudiantes. Si los almacena en una matriz, tiene que recorrer todo el conjunto comparando la identificación de cada entrada con la que está buscando.

Si, en cambio, "hash" (ver a continuación) su número de identificación de estudiante a una posición en el conjunto, entonces solo tiene que buscar los números del alumno que tienen el mismo hash. Mucho menos trabajo para encontrar lo que querías.

En este ejemplo, digamos que los ID de alumno son solo números de 6 dígitos. Nuestra función hash podría usarse solo con los 3 dígitos inferiores del número como la "tecla hash". Por lo tanto, 232145 tiene hash para ordenar la ubicación 145. Por lo tanto, solo necesita una matriz de 999 elementos (cada elemento es una lista de estudiantes).

Eso debería ser un buen comienzo para ti. Debería, por supuesto, leer un libro de texto o una wikipedia para este tipo de información. Pero supongo que ya lo has hecho y estás cansado de leer.

Answer 6

Responderé esa parte sobre la diferencia entre una tabla hash y una matriz ... pero como nunca antes implementé un algoritmo hash de ninguna importación, lo dejo a alguien más informado :)

Una matriz es solo una lista ordenada de objetos. El objeto en sí mismo realmente no importa ... lo importante es que si desea listar los objetos por 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, está indexada por claves, no por orden ... Creo que una búsqueda básica de algoritmos hash te dará mucha más información de la que puedo ... Wikipedia tiene una muy buena ... que determina "cubo" "que las claves entren 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, es necesaria una matriz o algún tipo de lista ordenada. Si la búsqueda rápida mediante una tecla arbitraria (codificada por varias funciones hash) es importante, entonces una tabla hash tiene sentido.

Answer 7

[Esta es la respuesta a un comentario hecho por me.yahoo.com/a arriba]

Eso depende de tu función hash. Supongamos que su función hash ordena 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 forma, no tiene que hacer una matriz igual al tamaño de sus datos.

Answer 8

La pregunta, creo, se responde 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 abstracción mínima, las matrices son solo bloques contiguos de memoria. Dada la dirección de inicio ( startAddress ), size ( sizeOfElement ) y el index de un elemento individual, 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 / visualizar como tablas hash con index como clave y la función anterior como función hash que calcula la ubicación de un valor en O (1)

Answer 9

Las respuestas hasta ahora han ayudado a definir las tablas hash y explicar algunas teorías, 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 con él. La diferencia, como señaló 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 descomunal , en el sentido de que llevarí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 simple es inventar una operación matemática arbitraria que puede realizar en los datos, que devuelve un número N (generalmente un número entero). Luego use ese número como el índice en una matriz de "cubos" y almacene sus datos en el cubo # N El truco está en seleccionar una operación que tienda a colocar valores en diferentes cubos de manera que sea más fácil encontrarlos más adelante.

Ejemplo: un gran centro comercial mantiene una base de datos de los automóviles y lugares de estacionamiento de sus clientes, para ayudar a los compradores a recordar dónde se estacionaron. La base de datos almacena, make , color , license plate y parking location . Al salir de la tienda, un comprador encuentra su automóvil al ingresar en su marca y color. La base de datos devuelve una lista (relativamente corta) de matrículas y plazas de estacionamiento. Un escaneo rápido localiza el automóvil 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 básicamente es solo una lista, puede imaginar implementar la consulta escaneando una matriz para 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 entre 100 y use el resto como el valor hash.

Esta regla convertirá cada elemento en un número entre 0 y 99, esencialmente clasificando los datos en 100 segmentos. Cada vez que un cliente necesita ubicar un automóvil, puede ajustar la marca y el color para encontrar el cubo de 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 buscan en función de decenas de criterios. Una función hash "buena" distribuirá los datos en cubos de forma que se minimice cualquier búsqueda adicional, lo que permite ahorrar una gran cantidad de tiempo.

Answer 10

Primero, debes entender qué es una función hash. Una función hash es una función que toma una tecla (por ejemplo, una cadena de longitud de arbritrary) y devuelve un número tan único como sea posible . La misma clave siempre debe devolver el mismo hash. Una función de hashing de cadena muy simple en Java podría verse como

public int stringHash(String s) {
    int h = s.length();
    for(char c : s.toCharArray()) {
        h ^= c;
    }
    return h;
}

Puedes estudiar una buena función hash en http://www.azillionmonkeys.com/qed/hash.html

Ahora, el mapa hash utiliza 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 de hash para el mismo valor, o dos hashes diferentes para asignar 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;
}

Answer 11

La tabla Hash es una estructura de datos que se crea para una búsqueda rápida.

Las tablas hash no son efectivas cuando el número de entradas es muy pequeño.

referencia

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