java - ¿Cómo lidian las HashTables con las colisiones?

collision-detection

Question

He escuchado en mis clases de grado que una HashTable colocará una nueva entrada en la categoría ''siguiente disponible'' si la nueva entrada clave choca con otra.

¿Cómo HashTable aún la HashTable el valor correcto si se produce esta colisión cuando se solicita una copia de seguridad con la clave de colisión?

Supongo que las Keys son de tipo String y hashCode() devuelve el valor predeterminado generado por, por ejemplo, Java.

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

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

Answer 1

He escuchado en mis clases de grado que una HashTable colocará una nueva entrada en la categoría ''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.

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

Utiliza los equals() para encontrar la entrada realmente coincidente.

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

Existen diversas estrategias de manejo de colisiones con diferentes ventajas y desventajas. wiki_hash_table ofrece una buena visión general.

Answer 2

Aquí hay una implementación de tabla hash muy simple en java. en solo implementa put() y get() , pero puedes agregar fácilmente lo que quieras. se basa en el método hashCode() java implementado por todos los objetos. puedes crear fácilmente tu propia interfaz,

interface Hashable {
  int getHash();
}

y obligarlo a ser implementado por las teclas 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));
    }
}

Answer 3

Como hay cierta confusión sobre qué algoritmo está usando el HashMap de Java (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 (cita de las líneas 355 a 371) se invoca cuando se busca una entrada en la tabla, por ejemplo de get() , containsKey() y algunos otros. El bucle for aquí va a través de la lista enlazada 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 viene el método addEntry() :

/**
 * 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 frontal del depósito, con un enlace a la primera entrada anterior (o nulo, si no hay tal). De manera removeEntryForKey() , el método removeEntryForKey() pasa por la lista y se encarga de eliminar solo una entrada, dejando intacto el resto de la lista.

Por lo tanto, aquí hay una lista de entradas vinculadas para cada segmento, y dudo mucho de que esto haya cambiado de _20 a _22 , ya que era 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).

Answer 4

Cuando habló sobre "Hash Table colocará una nueva entrada en el cubo ''siguiente disponible'' si la nueva entrada clave choca con otra.", Usted está hablando de la estrategia de direccionamiento abierto de la resolución de colisión de la tabla hash.

Hay varias estrategias para que la tabla hash resuelva la 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 incluyen:

• Cadena separada

• Direccionamiento abierto

• Hashing coalescido
• Hash de cuco
• Robin Hood hashing
• Hashing de 2 elecciones
• Hashing Rayuela

Otro método importante para manejar la colisión es mediante 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
• Llaves monotónicas

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

Answer 5

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

Java usa el encadenamiento separado para resolver colisiones en tablas hash. Aquí hay un excelente enlace a cómo sucede: http://javapapers.com/core-java/java-hashtable/

Answer 6

Hay múltiples técnicas disponibles para manejar la colisión. Explicaré algunos de ellos

Encadenamiento: al encadenar utilizamos índices de matriz para almacenar los valores. Si el código hash de 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 matriz real apunta al encabezado de la lista vinculada. Pero si solo hay un código hash que apunta a un índice de matriz, entonces el valor se almacena directamente en ese índice. La misma lógica se aplica al recuperar los valores. Esto se usa en Java HashMap / Hashtable para evitar colisiones.

Sonda lineal: esta técnica se usa cuando tenemos más índice en la tabla que los valores que se almacenan. La técnica de sondeo lineal funciona con el concepto de seguir incrementando hasta encontrar la ranura vacía. El pseudo código se ve así ..

índice = h (k)

while (val (índice) está ocupado)

índice = (índice + 1) mod n

Técnica de doble hash: en esta técnica usamos dos funciones 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 pseudo-código se ve así ..

índice = h1 (k)

while (val (índice) está ocupado)

índice = (índice + 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 lenta debido a la gran cantidad de movimiento que se produce hasta que encontramos una ranura vacía. También en la técnica de direccionamiento abierto cuando un elemento se elimina de una ranura, colocamos una lápida para indicar que el artículo se quitó de aquí y por eso está vacío.

Tomado de http://coder2design.com/hashing/

Answer 7

Las tablas Hash se ocupan de las colisiones en una de dos formas.

Opción 1: al hacer que cada depósito contenga una lista vinculada de elementos que están actualizados para ese depósito. Esta es la razón por la cual una mala función hash puede hacer que las búsquedas en las 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 cubetas que tiene y luego redistribuir todos los elementos en 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 modificarla con el tamaño de la tabla para asegurarse de que llegue al cubo. Por lo tanto, al aumentar el tamaño, volverá a calcular y ejecutar los cálculos del módulo que, si tiene suerte, podría enviar los objetos a diferentes cubos.

Java usa las opciones 1 y 2 en sus implementaciones de tabla hash.

Answer 8

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 hashcode?

Se almacenarán en el mismo contenedor, pero no en el próximo nodo de la lista vinculada. Y el método keys equals () se usará para identificar el par de valores clave correctos en HashMap.

Answer 9

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 cubo.