Crear una tabla hash con dos matrices

Question

¿Alguien sabe cómo hacerlo y cómo se vería el seudo código?

Como todos sabemos, una tabla hash almacena claves, pares de valores y cuando se llama a una tecla, la función devolverá el valor asociado con esa clave. Lo que quiero hacer es comprender la estructura subyacente al crear esa función de mapeo. Por ejemplo, si viviéramos en un mundo en el que no existían funciones definidas con anterioridad, a excepción de las matrices, ¿cómo podríamos replicar los Hashmaps que tenemos hoy?

Answer 1

En realidad, algunos de los actuales implentations Hashmap son realmente hechos de matrices a medida que proponen. Permítanme esbozar cómo funciona esto:

Hash Función Una función hash transforma sus llaves en un índice para la primera matriz (matriz K). Para esto se puede usar una función hash como MD5 o una más simple, que generalmente incluye un operador de módulo.

Cubetas Una implementación de Hashmap basada en una matriz simple podría usar cubos para hacer frente a las colisiones. Cada elemento ('cubo') en el conjunto K contiene un conjunto (conjunto P) de pares. Al agregar o consultar un elemento, la función hash lo dirige al cubo correcto en K, que contiene la matriz deseada P. Luego itera sobre los elementos en P hasta que encuentra una clave coincidente, o asigna un nuevo elemento al final de P.

teclas de asignación de cubos utilizando el hash Usted debe asegurarse de que el número de cubos (es decir, el tamaño de K) es una potencia de 2, digamos que 2^b. Para encontrar el índice de cubo correcto para alguna clave, calcule Hash (clave) pero solo guarde los primeros b bits. Este es su índice cuando se lanza a un número entero.

Rescaling Calcular el hash de una tecla y encontrar el cubo correcto es muy rápido. Pero una vez que un cubo se llena, tendrá que repetir más y más elementos antes de llegar a la correcta. Por lo tanto, es importante tener cubos suficientes para distribuir correctamente los objetos, o su Hashmap será lento.

Como generalmente no sabe cuántos objetos desea almacenar en el Hashmap de antemano, es conveniente aumentar o reducir dinámicamente el mapa. Puede contar el número de objetos almacenados, y una vez que supera un determinado umbral, vuelve a crear toda la estructura, pero esta vez con un tamaño mayor o menor para la matriz K.De esta forma, algunos de los cubos en K que estaban muy llenos ahora tendrán sus elementos divididos en varios cubos, por lo que el rendimiento será mejor.

Alternativas También puede utilizar una matriz de dos dimensiones en lugar de una matriz-de-matrices, o puede intercambiar arreglo P para una lista enlazada. Además, en lugar de mantener un conteo total de los objetos almacenados, simplemente puede optar por recrear (es decir, reescalar) el hashmap una vez que uno de los depósitos contiene más de una cantidad configurada de elementos.

Una variación de lo que está preguntando se describe como 'tabla hash de matriz' en el Hash table Wikipedia entry.

Código Para muestras de código, consulte here.

Espero que esto ayude.

Answer 2

¿Podría ser más preciso? ¿Una matriz contiene las claves, el otro los valores?

Si es así, aquí hay un ejemplo en Java (pero hay algunas características específicas de esta lengua aquí):

for (int i = 0; i < keysArray.length; i++) { 
    map.put(keysArray[i], valuesArray[i]); 
} 

Por supuesto, tendrá que crear una instancia de su objeto map (si está utilizando Java, Sugiero usar un HashMap<Object, Object> en lugar de un HashTable obsoleto), y también probar sus matrices para evitar objetos null y comprobar si tienen el mismo tamaño.

Answer 3

¿Te refieres a esto?

El siguiente es el uso de Ruby irb como una ilustración:

cities = ["LA", "SF", "NY"] 
=> ["LA", "SF", "NY"] 

items = ["Big Mac", "Hot Fudge Sundae"] 
=> ["Big Mac", "Hot Fudge Sundae"] 

price = {} 
=> {} 

price[[cities[0], items[1]]] = 1.29 
=> 1.29 

price 
=> {["LA", "Hot Fudge Sundae"]=>1.29} 

price[[cities[0], items[0]]] = 2.49 
=> 2.49 

price[[cities[1], items[0]]] = 2.99 
=> 2.99 

price 
=> {["LA", "Hot Fudge Sundae"]=>1.29, ["LA", "Big Mac"]=>2.49, ["SF", "Big Mac"]=>2.99} 

price[["LA", "Big Mac"]] 
=> 2.49 

Answer 4

Muestra Explicación:

En la fuente a continuación, básicamente, hace dos cosas:

1. Mapa de representación

• Algunos (X número de lista) de las listas
• X es 2 poder N número de listas es malo. A (2 potencia N) -1, o (2 potencia N) +1, o un número primo es bueno.

Ejemplo:

List myhashmap [hash_table_size]; 
// an array of (short) lists 
// if its long lists, then there are more collisions 

NOTA: esto es matriz de matrices, no dos matrices (no puedo ver una posible hashmap genérico, en el buen sentido con sólo 2 arrays)

Si conoce Algoritmos> Teoría de gráficos> Lista de adyacencia, este parece exactamente lo mismo.

2.función Hash

Y la función hash Convierte cadena (entrada) a un número (valor hash), que es el índice de una matriz

• inicializar el valor de hash a primera char (después de convertir a int)
• para cada Char más, desplazamiento a la izquierda 4 bits, a continuación, añadir char (después de convertir a int)

ejemplo,

int hash = input[0]; 
for (int i=1; i<input.length(); i++) { 
    hash = (hash << 4) + input[i] 
} 

hash = hash % list.size() 
// list.size() here represents 1st dimension of (list of lists) 
//  that is 1st dimension size of our map representation from point #1 
//  which is hash_table_size 

Ver en el primer enlace:

int HTable::hash (char const * str) const 

Fuente:
http://www.relisoft.com/book/lang/pointer/8hash.html
How does a hash table work?

actualización
esta es la mejor fuente: http://algs4.cs.princeton.edu/34hash/