¿Cómo implementar la tabla hash con el encadenamiento?

Question

Esta es probablemente una pregunta estúpida, pero no puedo por amor de Dios averiguar qué me falta aquí en la teoría detrás de las tablas hash con encadenamiento.

Esto es lo que entiendo:

Una tabla hash utiliza un hash para asociar una clave a un lugar donde se almacena un valor. A veces, un hash producirá la misma ubicación para diferentes claves, es decir, pueden producirse colisiones.

En este caso podemos implementar el encadenamiento almacenando todos los valores con la misma ubicación en una lista vinculada en esa ubicación.

Lo que no entiendo es lo siguiente:

Cuando se introduce una llave y la función de hash produce una ubicación en la que está el encadenamiento, ¿cómo determinar qué valor en la lista enlazada en ese lugar pertenece a esa clave específica, a diferencia de otra clave involucrada en la colisión?

Me doy cuenta de que esta es la teoría básica, pero si alguien puede señalar errores en mi razonamiento o decirme lo que me falta, lo agradecería muchísimo.

Answer 1

Manera simple: mantener una lista vinculada de "entradas de la tabla hash", que son pares clave/valor. Una vez que llegue al cubo, verifique su clave de consulta con todas las claves del depósito.

Answer 2

Cuando ingresa una clave y la función hash produce una ubicación en la que hay encadenamiento, ¿cómo determina qué valor en la lista vinculada en esa ubicación pertenece a esa clave específica, en lugar de otra clave involucrada en la colisión?

Usted acaba de recurrir a la búsqueda lineal del cubo por la clave.

Es posible apreciar la siguiente implementación de mini tabla hash escrito en C#, tomada de this blog post:

> let hashtbl xs = 
    let spine = [|for _ in xs -> ResizeArray()|] 
    let f k = spine.[k.GetHashCode() % spine.Length] 
    Seq.iter (fun (k, v) -> (f k).Add (k, v)) xs 
    fun k -> Seq.pick (fun (k', v) -> if k=k' then Some v else None) (f k);; 
val hashtbl : seq<'a * 'b> -> ('a -> 'b) when 'a : equality 

Esta función hashtbl toma una secuencia de asociación xs de pares clave-valor, construye una tabla hash representado como un spine array de ResizeArray buckets y devuelve una función lambda que encuentra el depósito apropiado y realiza una búsqueda lineal en él para la clave k dada. La búsqueda lineal se realiza utilizando la función Seq.pick.