Reashing de colisión hashtable - ¿cómo se leen los valores?

Question

Estoy tratando de entender cómo funcionan las Hashtables en C#. Leí el artículo de MSDN y entiendo que C# Hashtables usa 'rehashing' para colisiones, es decir, si intento insertar un par de clave/valor en la tabla hash, si usa HashFunction H1 da como resultado una colisión, entonces probará HashFunction H2, H3 , etc., hasta que no se encuentren colisiones.

MSDN cita:

La clase Hashtable utiliza una técnica diferente se refiere como rehasing. (Algunas fuentes se refieren a refrito como la doble dispersión.)

obras refrito de la siguiente manera: hay un conjunto de hash de diferentes funciones, H1 ... Hn, y al insertar o recuperar un elemento de la tabla hash, inicialmente se usa la función hash H1. Si esto lleva al a una colisión, se intenta H2 y en su lugar hasta Hn si es necesario. La sección anterior mostraba solo una función hash, que es la función hash inicial (H1). Las otras funciones hash son muy similares a esta función, solo diferenciando por un factor multiplicativo. En general, la función hash Hk se define como:

Hk (clave) = [GetHash (tecla) + k * (1 + (((GetHash (clave) >> 5) + 1)% (hashsize - 1)))]% hashsize

Sin embargo, tomando el ejemplo de la sitio1 MSDN:

private static Hashtable employees = new Hashtable(); 

public static void Main() 
{ 
    // Add some values to the Hashtable, indexed by a string key 
    employees.Add("111-22-3333", "Scott"); 
    employees.Add("222-33-4444", "Sam"); 
} 

vamos a suponer que la adición de la segunda clave resultará en una colisión, por lo H2 tendrá que ser usado. Sin embargo, cuando llamo a los empleados ["222-33-4444"], ¿cómo sabe la tabla hash usar H2? ¿Hay un mapeo separado? Gracias.

Answer 1

Las tablas hash almacenar la clave y el valor de la propia tabla hash. De esta forma, más adelante, durante las operaciones, como las búsquedas en la tabla hash, se puede garantizar que el valor encontrado sea el que coincida con el índice utilizado para la búsqueda. Las tablas hash usan una metodología simple de "probar el método básico de búsqueda hasta el éxito". En este caso, el método de búsqueda es "usar la función hash X", donde X cambia cuando falla.

En otros esquemas, el método de búsqueda es "mirar la entrada X de la tabla" (según lo determinado por una función hash) donde X simplemente aumenta en uno de manera de envolver cada falla.

La pregunta molesta ahora es ¿qué sucede cuando el valor NO está en la tabla? Bueno, eso puede ser bastante feo: cuando tocas una entrada en la tabla que falta o, incluso peor, cuando has iterado tantas entradas como están almacenadas en la tabla, puedes estar seguro de que la entrada no está No, pero eso puede llevar "un tiempo" en el peor de los casos.

Tenga en cuenta que, dado que solo se puede asociar un valor con una tecla, una vez que haya encontrado la clave, ha encontrado el valor. Lo peor que una tabla hash puede hacer es tener que hacer el equivalente de una búsqueda lineal poco amistosa de caché sobre todos los valores en la tabla hash ... pero finalmente, encontrará el valor si está allí porque está comparando la clave almacenada con la clave solicitada para probar si está allí. La única optimización que hacen las tablas hash consiste en mirar primero, en este caso, donde dice la función hash 1, y luego 2, y luego 3 ...

Answer 2

Primero probará H1. Si no encuentra una coincidencia, usará H2. Y así.

Answer 3

Creo que malinterpretas las repeticiones. Solo hay una función hash: la virtual object.GetHashCode() (o, si proporciona un IHashCodeProvider o IEqualityComparer, usa ese objeto para calcular el código hash). Cuando la tabla hash está llena, expande su capacidad y redistribuye los elementos sobre las matrices nuevas y más grandes. El método privado que hace esto se llama Rehash(), pero no recalcula los códigos hash.

CORRECCIÓN

El rehashing no utiliza una nueva función, sino más bien opera sobre el valor precedente del código hash; esto tiene el efecto de buscar ranuras posteriores hasta que se encuentre una vacía (para insertar/configurar) o hasta que todas las claves con el mismo código hash (inicial) hayan sido verificadas con la clave de índice (para su recuperación).

EDITAR

Para responder a su pregunta directamente:

Vamos a suponer que la adición de la segunda llave dará lugar a una colisión, por lo H2 tendrá que ser utilizado. Sin embargo, cuando llamo a los empleados ["222-33-4444"], ¿cómo sabe la tabla hash usar H2? ¿Hay un mapeo separado? Gracias.

1. Calcular el cubo correcto basado en el código hash de la clave pasado.
2. Si ese cubo está vacío, falla.
3. Si la clave del depósito coincide con la clave aprobada, devuelva el valor del depósito.
4. Si el recuento de colisiones hash es cero, falla.
5. Calcule el siguiente código hash del código hash actual.
6. Calcule el cubo correcto según el nuevo código hash.
7. vaya al paso 2.