Entiendo que se aplica una técnica de hash a una clave para almacenar su valor en la dirección de la memoria.¿Cómo se almacenan la clave-valor de HashTable y HashMap en la memoria?
Pero no entiendo cómo está ocurriendo la colisión aquí? ¿Qué algoritmo hash utiliza Java para crear un espacio de memoria? ¿Es MD5?
La idea básica de HashMap es la siguiente:
HashMap es realmente una matriz de objetos especiales que sujetan tanto clave y valor.hashCode() que tiene cada objeto. Por lo tanto, cuando escriba un nuevo Class, debe encargarse de la implementación correcta de los métodos hashCode() y equals(). El predeterminado (de la clase Object) toma el puntero de memoria como un número. Pero eso no es bueno para la mayoría de las clases que nos gustaría usar. Por ejemplo, la clase String utiliza un algoritmo que crea el hash de todos los caracteres de la cadena; piénselo de esta manera: hashCode = 1.char + 2.char + 3.char... (simplificado). Por lo tanto, dos cadenas iguales, aunque se encuentren en una ubicación diferente en la memoria, tienen el mismo hashCode().hashCode(), digamos "132", es el número de cubeta donde debería guardarse el objeto si tuviéramos una matriz tan grande. Pero no lo hacemos, la nuestra tiene solo 16 cubos de largo. Por eso, utilizamos el cálculo obvio 'hashcode % array.length = bucket' o '132 mod 16 = 4' y almacenar el par clave-valor en un número cubo 4.HashMap, por lo que debe indicarle a su Maps cuántos cubos utilizará si ya lo conoce.An image, courtesy of Wikipedia: 
En este caso,
mod 256, apuntan a cuatro ranuras diferentes en la matriz.Ahora, si intentas buscar un número de teléfono de Sandra Dee, deberías tachar su nombre, modificarlo por 256, y buscar en el cubo 152. Allí encontrarás a John Smith. Esa no es Sandra, mira más allá ... aha, Sandra está encadenada detrás de John.
Como implementación por defecto hashCode() función en Object Rendimiento de Clase de la dirección de memoria como el hash que se utiliza como clave en HashTable & HashMap.
Por ejemplo, si tiene 100 registros en la tabla HashTable, y desea encontrar una clave con 'Men In Black', ¿qué tan rápido encuentra el valor de la misma? Creo que no tomará más de una iteración encontrarlo Q (1). Lo que sentí es que el compilador crea un código de hash de 'Men In Black' y almacena el valor en esa ubicación de memoria en particular. Más tarde, cuando tratamos de recuperar esto, usa el hascode para encontrar su valor ... ¿Me falta algo? ... Si ese no es el caso, el tiempo de ejecución de la búsqueda de claves es uno ie.Q (1)? – Sahal
Verá la ubicación de la memoria donde se almacena el objeto String con el valor 'Men In Black'. Esta ubicación de memoria se convierte en el código hash que se utiliza para recuperar el valor. Idealmente debería ser Q (1), generalmente debido a una colisión y para optimizar la memoria utilizada, habrá una ligera variación y para todos los propósitos prácticos puede tomarse como Q (1). La variación dependerá de la cantidad de elementos en el cubo en el índice calculado a partir de hashcode. No es necesario que los 100 elementos en hashmap tengan un índice único. –
Además, la clase 'String' tiene su propia implementación' hashCode() ', no toma la ubicación de la memoria como tal, pero usa un algoritmo para hacer un hash a partir de los caracteres reales en la cadena ... –
Aquí Hash no significa que para Hashing técnicas como MD5. Es el HashCode de la ubicación de la memoria utilizada para almacenar un Object para una clave en particular.
Lecturas:
This es algo más clara la explicación de cómo funciona HashMap?
Por ejemplo, si tiene 100 registros en el HashTable y quiere encontrar una clave con 'Men In Black', ¿qué tan rápido encuentra el valor del mismo? Creo que no tomará más de una iteración encontrarlo Q (1). Lo que sentí es que el compilador crea un código de hash de 'Men In Black' y almacena el valor en esa ubicación de memoria en particular. Más tarde, cuando tratamos de recuperar esto, usa el hascode para encontrar su valor ... ¿Me falta algo? ... Si ese no es el caso, el tiempo de ejecución de la búsqueda de claves es uno ie.Q (1)? – Sahal
Lea los enlaces actualizados – Asif
La clave en el mapa se almacena en la posición determinada de la matriz (memoria). La posición la establece RunTime (no el compilador), utilizando un algoritmo que utiliza hashCode transformado de objeto y longitud de matriz. El tiempo necesario para recuperar el elemento es O (1), que no requiere ninguna iteración. –
Después de leer la respuesta de @ Slanec, vea el javadoc de Java-8, ya que hay cambios significativos. Por ejemplo: 'TREEIFY', donde LinkedList se convierte a TreeMap en caso de que se alcance el número de entradas límite por segmento (actualmente 8).
Si encuentra un enlace que explique las imágenes, por favor póngalo aquí ... Eso será muy útil. – Sahal
Listo. Es de [este artículo en wikipedia] (http://en.wikipedia.org/wiki/Hash_table#Separate_chaining_with_list_heads). –
Y ahora, cuando sabes esto, [esta es la implementación de 'hashCode()' real de 'String'] (http://docs.oracle.com/javase/7/docs/api/java/lang/ String.html # hashCode% 28% 29). [Y] (http://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier) [some] (http://stackoverflow.com/ questions/1835976/what-is-a-sensible-prime-for-hashcode-calculation) [random] (http://stackoverflow.com/questions/3613102/why-use-a-prime-number-in-hashcode) enlaces en la selección del número principal en 'hashCode()'. –