¿Cómo lidian las HashTables con las colisiones?

Question

He escuchado en mis clases de grado que un HashTable colocará una nueva entrada en el segmento 'siguiente disponible' si la nueva entrada de Llave colisiona con otra.

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

Supongo que el Keys es String y el hashCode() devuelve el valor predeterminado generado por ejemplo Java.

Si implemento mi propia función hash y la utilizo como parte de una tabla de consulta (es decir, HashMap o Dictionary), ¿qué estrategias existen para hacer frente a 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

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 los 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 de hash están llenos a continuación la tabla hash puede aumentar el número de cubos que ha 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 utiliza las opciones 1 y 2 en sus implementaciones de tabla hash.

Answer 2

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

Answer 3

que he oído en mis clases de grado que un HashTable colocará una nueva entrada en la 'próxima disponibles' balde si la nueva entrada clave choca con otro.

Esto es en realidad no es cierto, al menos por el JDK de Oracle (que 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 sería la HashTable todavía devolver el valor correcto si esto colisión ocurre cuando se llama por una atrás con la tecla colisión?

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

Si puedo implementar mi propia función hash y lo uso como parte de una tabla de consulta (es decir, un HashMap o diccionario), lo que existen estrategias para tratar con colisiones?

Existen diversas estrategias de manejo de colisiones con diferentes ventajas y desventajas. Wikipedia's entry on hash tables ofrece una buena visión general.

Answer 4

le recomiendo que lea esta entrada del blog que apareció en HackerNews recientemente: How HashMap works in Java

En resumen, la respuesta es

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

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

Answer 5

Como hay cierta confusión acerca de lo que HashMap del algoritmo de Java es el uso (en el/implementación de Sun de Oracle/OpenJDK), aquí los fragmentos de código fuente pertinente (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 desde las líneas 355 a 371) se invoca al buscar una entrada en la tabla, por ejemplo, desde get(), containsKey() y algunos otros. El bucle for aquí va a través de la lista enlazada formada por los objetos de entrada.

el código aquí los objetos de entrada (líneas 691 a 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) 

} 

Justo después de esto viene la 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 añade la nueva entrada en la parte frontal del segmento, con un enlace a la antigua primera entrada (o nulo, si no hay tal). De manera similar, 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 6

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

interface Hashable { 
    int getHash(); 
} 

y obligarlo a ser implementado por las teclas, si quieres.

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 7

Hay varios métodos para resolution.Some colisión de ellos están encadenamiento separado, direccionamiento abierto, Robin Hood hash, etc. cuco Hashing

Java utiliza encadenamiento separado para resolver las colisiones en Hash es tables.Here un gran enlace a cómo sucede: http://javapapers.com/core-java/java-hashtable/

Answer 8

Cuando usted habló "Tabla de Hash colocará una nueva entrada en la 'próxima disponibles' balde si la nueva entrada clave choca con otro", se habla de la Estrategia de direccionamiento abierto de resolución de colisión de tabla hash.

---

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

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

• independiente encadenamiento

• direccionamiento abierto

• coalescentes hashing
• cuco hashing
• Robin Hood hashing
• 2-elección hashing
• Rayuela hash

---

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

• Cambiar el tamaño de la copia de todas las entradas
• Cambio de tamaño incremental
• teclas monótonas

---

EDIT: lo anterior son tomados de wiki_hash_table, donde hay que ir a echar un vistazo para obtener más información.

Answer 9

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

Encadenamiento: En el encadenamiento 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 utiliza 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 tiene este aspecto ..

index = h (k)

mientras (val (índice) está ocupada)

index = (índice + 1) mod n

Doble técnica de hashing: En esta técnica, utilizamos 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 tiene este aspecto ..

index = h1 (k)

mientras (val (índice) está ocupada)

índice = (+ h2 índice (k)) mod n

Las técnicas de sondeo lineal y doble hashing son parte de la técnica de direccionamiento abierto y solo se pueden usar si las ranuras disponibles son más que el número 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/