¿Cómo manejan las HashTables las colisiones?

97

Escuché en mis clases de grado que HashTablecolocará una nueva entrada en el grupo "siguiente disponible" si la nueva entrada clave choca con otra.

¿Cómo HashTabledevolvería el valor correcto si esta colisión se produce al llamar a uno con la tecla de colisión?

Supongo que Keysson de Stringtipo y hashCode()devuelve el valor predeterminado generado por, por ejemplo, Java.

Si implemento mi propia función hash y la uso como parte de una tabla de búsqueda (es decir, un HashMapo Dictionary), ¿qué estrategias existen para hacer frente a las colisiones?

¡Incluso he visto notas relacionadas con números primos! Información no tan clara en la búsqueda de Google.

Alex
fuente

Respuestas:

92

Las tablas hash tratan las colisiones de dos formas.

Opción 1: hacer que cada depósito contenga una lista vinculada de elementos que se han agregado a ese depósito. Esta es la razón por la que una función hash incorrecta puede hacer que las búsquedas en tablas hash sean muy lentas.

Opción 2: si las entradas de la tabla hash están todas llenas, la tabla hash puede aumentar el número de depósitos que tiene y luego redistribuir todos los elementos de la tabla. La función hash devuelve un número entero y la tabla hash tiene que tomar el resultado de la función hash y modificarlo contra el tamaño de la tabla de esa manera puede estar seguro de que llegará al cubo. Entonces, al aumentar el tamaño, repetirá y ejecutará los cálculos de módulo que, si tiene suerte, podrían enviar los objetos a diferentes cubos.

Java usa la opción 1 y 2 en sus implementaciones de tablas hash.

ams
fuente
1
En el caso de la primera opción, ¿hay alguna razón por la que se use una lista vinculada en lugar de una matriz o incluso un árbol de búsqueda binaria?
1
la explicación anterior es de alto nivel, no creo que haya mucha diferencia entre la lista vinculada y la matriz. Creo que un árbol de búsqueda binario sería excesivo. También creo que si profundiza en cosas como ConcurrentHashMap y otras, hay muchos detalles de implementación de bajo nivel que pueden marcar una diferencia de rendimiento, que la explicación de alto nivel anterior no tiene en cuenta.
AMS
2
Si se usa el encadenamiento, cuando se le da una clave, ¿cómo sabemos qué elemento recuperar?
ChaoSXDemon
1
@ChaoSXDemon puede recorrer la lista en la cadena por clave, las claves duplicadas no son el problema, el problema son dos claves diferentes que tienen el mismo código hash.
ams
1
@ams: ¿Cuál es el preferido? ¿Existe algún límite para la colisión de Hash, después de lo cual JAVA ejecuta el segundo punto?
Shashank Vivek
77

Cuando hablaste de "La tabla hash colocará una nueva entrada en el depósito 'siguiente disponible' si la nueva entrada clave choca con otra", estás hablando de la estrategia de direccionamiento abierto de resolución de colisión de la tabla hash.


Existen varias estrategias para que la tabla hash resuelva una colisión.

El primer tipo de método grande requiere que las claves (o punteros a ellas) se almacenen en la tabla, junto con los valores asociados, que además incluye:

  • Encadenamiento separado

ingrese la descripción de la imagen aquí

  • Direccionamiento abierto

ingrese la descripción de la imagen aquí

  • Hash combinado
  • Hash de cuco
  • Hash de robin hood
  • Hash de 2 opciones
  • Hash de rayuela

Otro método importante para manejar la colisión es el cambio de tamaño dinámico , que además tiene varias formas:

  • Cambiar el tamaño copiando todas las entradas
  • Cambio de tamaño incremental
  • Teclas monotónicas

EDITAR : lo anterior se tomó prestado de wiki_hash_table , donde debe ir a echar un vistazo para obtener más información.

herohuyongtao
fuente
3
"[...] requiere que las claves (o punteros a ellas) se almacenen en la tabla, junto con los valores asociados". Gracias, este es el punto que no siempre queda claro de inmediato al leer sobre los mecanismos para almacenar valores.
mtone
27

Hay varias técnicas disponibles para manejar una colisión. Te explicare algunos de ellos

Encadenamiento: en el encadenamiento usamos índices de matriz para almacenar los valores. Si el código hash del segundo valor también apunta al mismo índice, entonces reemplazamos ese valor de índice con una lista vinculada y todos los valores que apuntan a ese índice se almacenan en la lista vinculada y el índice de la matriz real apunta al encabezado de la lista vinculada. Pero si solo hay un código hash que apunta a un índice de matriz, el valor se almacena directamente en ese índice. Se aplica la misma lógica al recuperar los valores. Esto se usa en Java HashMap / Hashtable para evitar colisiones.

Sondeo lineal: esta técnica se utiliza cuando tenemos más índice en la tabla que los valores a almacenar. La técnica de palpado lineal funciona con el concepto de seguir aumentando hasta encontrar una ranura vacía. El pseudocódigo se ve así:

index = h(k) 

while( val(index) is occupied) 

index = (index+1) mod n

Técnica de hash doble: en esta técnica usamos dos funciones de hash h1 (k) y h2 (k). Si la ranura en h1 (k) está ocupada, entonces la segunda función hash h2 (k) se usa para incrementar el índice. El pseudocódigo se ve así:

index = h1(k)

while( val(index) is occupied)

index = (index + h2(k)) mod n

Las técnicas de sondeo lineal y doble hash son parte de la técnica de direccionamiento abierto y solo se pueden usar si las ranuras disponibles son más que la cantidad de elementos que se agregarán. Se necesita menos memoria que el encadenamiento porque no se usa ninguna estructura adicional aquí, pero es lento debido a que ocurren muchos movimientos hasta que encontramos un espacio vacío. También en la técnica de direccionamiento abierto, cuando un elemento se quita de una ranura, colocamos una lápida para indicar que el elemento se quita de aquí y por eso está vacío.

Para obtener más información, consulte este sitio .

Jatinder Pal
fuente
18

Le sugiero que lea esta publicación de blog que apareció recientemente en HackerNews: Cómo funciona HashMap en Java

En resumen, la respuesta es

¿Qué pasará si dos objetos clave HashMap diferentes tienen el mismo código hash?

Se almacenarán en el mismo depósito, pero no en el siguiente nodo de la lista vinculada. Y el método keys equals () se utilizará para identificar el par clave-valor correcto en HashMap.

Zengr
fuente
3
¡Los HashMaps son muy interesantes y profundizan! :)
Alex
1
Creo que la pregunta es sobre HashTables, no HashMap
Prashant Shubham
10

Escuché en mis clases de grado que una HashTable colocará una nueva entrada en el grupo "siguiente disponible" si la nueva entrada clave choca con otra.

En realidad, esto no es cierto, al menos para Oracle JDK ( es un detalle de implementación que podría variar entre diferentes implementaciones de la API). En cambio, cada segmento contiene una lista vinculada de entradas anteriores a Java 8 y un árbol equilibrado en Java 8 o superior.

entonces, ¿cómo devolvería la HashTable el valor correcto si esta colisión se produce al llamar a uno con la clave de colisión?

Utiliza el equals()para encontrar la entrada que realmente coincide.

Si implemento mi propia función hash y la uso como parte de una tabla de búsqueda (es decir, un HashMap o un diccionario), ¿qué estrategias existen para lidiar con las colisiones?

Existen varias estrategias de manejo de colisiones con diferentes ventajas y desventajas. La entrada de Wikipedia sobre tablas hash ofrece una buena descripción general.

Michael Borgwardt
fuente
Es cierto para ambos Hashtabley HashMapen jdk 1.6.0_22 de Sun / Oracle.
Nikita Rybak
@Nikita: no estoy seguro acerca de Hashtable, y no tengo acceso a las fuentes en este momento, pero estoy 100% seguro de que HashMap usa encadenamiento y no sondeo lineal en cada versión que he visto en mi depurador.
Michael Borgwardt
@Michael Bueno, estoy viendo la fuente de HashMap en public V get(Object key)este momento (la misma versión que la anterior). Si encuentra una versión precisa donde aparecen esas listas vinculadas, me interesaría saberlo.
Nikita Rybak
@Niki: Ahora estoy mirando el mismo método, y lo veo usando un bucle for para iterar a través de una lista vinculada de Entryobjetos:localEntry = localEntry.next
Michael Borgwardt
@Michael Lo siento, es mi error. Interpreté el código de manera incorrecta. naturalmente, e = e.nextno lo es ++index. +1
Nikita Rybak
7

Actualización desde Java 8: Java 8 utiliza un árbol autoequilibrado para el manejo de colisiones, mejorando el peor de los casos de O (n) a O (log n) para la búsqueda. El uso de un árbol autoequilibrado se introdujo en Java 8 como una mejora sobre el encadenamiento (usado hasta Java 7), que usa una lista vinculada y tiene el peor caso de O (n) para la búsqueda (ya que necesita atravesar la lista)

Para responder a la segunda parte de su pregunta, la inserción se realiza mapeando un elemento dado a un índice dado en la matriz subyacente del mapa hash; sin embargo, cuando ocurre una colisión, todos los elementos deben conservarse (almacenados en una estructura de datos secundaria , y no solo reemplazado en la matriz subyacente). Esto generalmente se hace haciendo que cada componente de matriz (ranura) sea una estructura de datos secundaria (también conocida como depósito), y el elemento se agrega al depósito que reside en el índice de matriz dado (si la clave no existe ya en el depósito, en cuyo caso se reemplaza).

Durante la búsqueda, la clave se codifica con el índice de matriz correspondiente y se realiza la búsqueda de un elemento que coincida con la clave (exacta) en el depósito dado. Debido a que el bucket no necesita manejar colisiones (compara claves directamente), esto resuelve el problema de las colisiones, pero lo hace a costa de tener que realizar la inserción y búsqueda en la estructura de datos secundaria. El punto clave es que en un mapa hash, tanto la clave como el valor se almacenan, por lo que incluso si el hash choca, las claves se comparan directamente para determinar la igualdad (en el depósito) y, por lo tanto, se pueden identificar de forma única en el depósito.

El manejo de colisiones trae el peor de los casos de inserción y búsqueda de O (1) en el caso de no manejo de colisiones a O (n) para encadenamiento (una lista vinculada se usa como estructura de datos secundaria) y O (log n) para árbol autoequilibrado.

Referencias:

Java 8 viene con las siguientes mejoras / cambios de objetos HashMap en caso de grandes colisiones.

  • Se ha eliminado la función alternativa String hash agregada en Java 7.

  • Los depósitos que contienen una gran cantidad de claves en colisión almacenarán sus entradas en un árbol equilibrado en lugar de en una lista vinculada después de que se alcance cierto umbral.

Los cambios anteriores garantizan el rendimiento de O (log (n)) en el peor de los casos ( https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8 )

Daniel Valland
fuente
¿Puede explicar cómo la inserción en el peor de los casos para un HashMap de lista enlazada es solo O (1) y no O (N)? Me parece que si tiene una tasa de colisión del 100% para claves no duplicadas, termina teniendo que atravesar todos los objetos en el HashMap para encontrar el final de la lista vinculada, ¿verdad? ¿Qué me estoy perdiendo?
mbm29414
En el caso específico de la implementación de hashmap, en realidad tiene razón, pero no porque necesite encontrar el final de la lista. En un caso general de implementación de lista vinculada, un puntero se almacena tanto en la cabeza como en la cola y, por lo tanto, la inserción se puede realizar en O (1) adjuntando el siguiente nodo a la cola directamente, pero en el caso de hashmap, el método de inserción necesita asegurarse de que no haya duplicados y, por lo tanto, debe buscar en la lista para verificar si el elemento ya existe y, por lo tanto, terminamos con O (n). Y por lo tanto, es la propiedad de conjunto impuesta en una lista vinculada la que está causando O (N). Haré una corrección a mi respuesta :)
Daniel Valland
4

Utilizará el método equals para ver si la clave está presente incluso y especialmente si hay más de un elemento en el mismo depósito.

Aerodeslizador lleno de anguilas
fuente
4

Como existe cierta confusión sobre qué algoritmo está usando Java HashMap (en la implementación de Sun / Oracle / OpenJDK), aquí los fragmentos de código fuente relevantes (de OpenJDK, 1.6.0_20, en Ubuntu):

/**
 * Returns the entry associated with the specified key in the
 * HashMap.  Returns null if the HashMap contains no mapping
 * for the key.
 */
final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

Este método (la cita es de las líneas 355 a 371) se llama al buscar una entrada en la tabla, por ejemplo get(), de , containsKey()y algunas otras. El bucle for aquí pasa por la lista vinculada formada por los objetos de entrada.

Aquí el código para los objetos de entrada (líneas 691-705 + 759):

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

  // (methods left away, they are straight-forward implementations of Map.Entry)

}

Inmediatamente después de esto viene el addEntry()método:

/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket.  It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

Esto agrega la nueva entrada en la parte delantera del cubo, con un enlace al antiguo primero entrada anterior (o nula, si no existe). De manera similar, el removeEntryForKey()método recorre la lista y se encarga de eliminar solo una entrada, dejando intacto el resto de la lista.

Entonces, aquí hay una lista de entrada vinculada para cada segmento, y dudo mucho que esto haya cambiado de _20a_22 , ya que fue así desde 1.2 en adelante.

(Este código es (c) 1997-2007 Sun Microsystems, y está disponible bajo GPL, pero para copiar mejor use el archivo original, contenido en src.zip en cada JDK de Sun / Oracle, y también en OpenJDK.)

Paŭlo Ebermann
fuente
1
Marqué esto como wiki de la comunidad , ya que realmente no es una respuesta, más un poco de discusión sobre las otras respuestas. En los comentarios simplemente no hay suficiente espacio para tales citas de código.
Paŭlo Ebermann
3

aquí hay una implementación de tabla hash muy simple en java. en solo implementos put()y get(), pero puede agregar fácilmente lo que quiera. se basa en el hashCode()método de Java que es implementado por todos los objetos. podría crear fácilmente su propia interfaz,

interface Hashable {
  int getHash();
}

y obligarlo a que lo implementen las claves si lo desea.

public class Hashtable<K, V> {
    private static class Entry<K,V> {
        private final K key;
        private final V val;

        Entry(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    private static int BUCKET_COUNT = 13;

    @SuppressWarnings("unchecked")
    private List<Entry>[] buckets = new List[BUCKET_COUNT];

    public Hashtable() {
        for (int i = 0, l = buckets.length; i < l; i++) {
            buckets[i] = new ArrayList<Entry<K,V>>();
        }
    }

    public V get(K key) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        for (Entry e: entries) {
            if (e.key.equals(key)) {
                return e.val;
            }
        }
        return null;
    }

    public void put(K key, V val) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        entries.add(new Entry<K,V>(key, val));
    }
}
Jeffrey Blattman
fuente
2

Existen varios métodos para la resolución de colisiones, algunos de ellos son el encadenamiento separado, el direccionamiento abierto, el hash de Robin Hood, el hash de cuco, etc.

Java usa Separate Chaining para resolver colisiones en tablas Hash. Aquí hay un gran enlace a cómo sucede: http://javapapers.com/core-java/java-hashtable/

Infusión de Ajenjo n Asfodel
fuente