¿Cómo ordena Java los elementos en un HashMap o un HashTable?

Question

Me preguntaba cómo ordena Java elementos en el Map (HashMap o Hashtable) cuando se agregan. ¿Están las teclas ordenadas por el código hash, referencia de memoria o por prioridad de asignación ...?

Es porque me he dado cuenta mismas parejas en la Map no están siempre en el mismo orden

Answer 1

java.util.HashMap es desordenada; no puedes ni debes asumir nada más allá de eso.

Esta clase no garantiza el orden del mapa; en particular, no garantiza que el orden se mantendrá constante a lo largo del tiempo.

java.util.LinkedHashMap usa el orden de inserción.

Esta implementación difiere de HashMap en que mantiene una lista doblemente enlazada que se ejecuta a través de todas sus entradas. Esta lista vinculada define el orden de iteración, que normalmente es el orden en el que las claves se insertaron en el mapa (orden de inserción).

java.util.TreeMap, a SortedMap, utiliza el pedido natural o personalizado de las teclas.

El mapa se ordena de acuerdo con el ordenamiento natural de sus teclas, o por un Comparator previsto al momento de la creación del mapa, dependiendo de la que se utiliza el constructor.

Answer 2

HashMap no ordena a todos. Para un mapa que ordena por valores clave, debe usar TreeMap en su lugar.

De los JavaDocs para TreeMap: implementación basada

árbol

Rojo-Negro de la interfaz SortedMap. Esta clase garantiza que el mapa será en orden ascendente clave, ordenados de acuerdo al orden natural de clase de la llave (vea comparable), o por el comparador proporcionado en tiempo de creación, dependiendo del constructor es utilizado .

De la documentación de HashMap:

Esta clase no ofrece ninguna garantía en cuanto a el orden del mapa; en particular, , no garantiza que la orden se mantenga constante en el tiempo.

Answer 3

Un Map no es una estructura de datos ordenada - que no debe confiar en las entradas de una HashMap están en un orden determinado. Algunas implementaciones de Map, como LinkedHashMap y TreeMap, garantizan cierto orden, pero HashMap no.

Si realmente quiere saber lo que pasa internamente, las operaciones de búsqueda del código fuente de HashMap - se puede encontrar en src.zip que debe estar en el directorio de instalación de JDK.

A HashMap tiene una serie de "cubos" en los que almacena sus entradas. El cubo en el que se almacena una entrada está determinado por el código hash de la clave de la entrada. El orden en el que ve las entradas en el HashMap depende de los códigos hash de las teclas. Pero no escriba programas que dependan de que las entradas estén en cierto orden en un HashMap - la implementación podría cambiar en una versión futura de Java y su programa ya no funcionaría.

Answer 4

No hay un orden definido en una tabla hash. Las claves se colocan en una ranura, en función del código hash, pero incluso eso no es un orden trivial por código hash.

Answer 5

hashmap tiene un orden no definida de los elementos

Answer 6

Primero de todo: HashMap específicamente no proporcionar una ordenación estable y/o definido. Entonces, cualquier cosa que observe es simplemente un detalle de implementación y usted no debe depender de ello de ninguna manera.

Dado que a veces es útil saber la razón de la ordenación aparentemente al azar, aquí está la idea básica:

Un HashMap tiene número de cubos (implementado como una matriz) en el que almacenar las entradas.

Cuando se agrega un artículo al mapa, se asigna a los depósitos según el valor derivado de su hashCode y el tamaño del cubo del HashMap. (Tenga en cuenta que es posible que la cubeta ya esté ocupada, lo que se conoce como colisión. Se maneja con gracia y correctamente, pero ignoraré ese manejo para la descripción porque no cambia el concepto).

El ordenamiento percibido de las entires (como las devueltas al iterar sobre el Map) depende del orden de las entradas en esos segmentos.

Cada vez que se rehice el tamaño (porque el mapa excedió su umbral de plenitud), el número de depósitos cambia, lo que significa que la posición de cada elemento puede cambiar, ya que la posición del cubo también se deriva del número de segmentos .

Answer 7

HashMap almacena los valores utilizando el valor de hash único generado utilizando una parte de la clave. Este hash-value se asigna a la dirección donde se almacenará. Así es como asegura un acceso O (1).

LinkedHashmap, por otro lado, conserva el orden en que se agregó al mapa.