Prefacio: Hay muchas cosas nuevas agregadas después de Java 8. Encontré información relevante en línea. Después de abusar de Hashmap, decidí resolver el conocimiento relevante para mí. Este artículo como referencia en la imagen y algún contenido: http://www.vevb.com/article/80446.htm
La estructura de almacenamiento de HASHMAP se muestra en la figura: si hay más de 8 nodos en un cubo, la estructura de almacenamiento es un árbol rojo y negro, y menos de 8 es una lista vinculada unidireccional.
1: Algunas propiedades del hashmap
public class hashmap <k, v> extiende abstractmap <k, v> implementa mapa <k, v>, clonable, serializable {private static final long serialversionUid = 362498820763181265l; // la capacidad inicial predeterminada predeterminada es 16 estatical final intfairtial_initial_capacity = 1 << 4; // máxima capacidad estatic en la máxima introducción estatica intemperánea. 30; // El factor de relleno predeterminado (las versiones anteriores también se llamaron factor de carga) Float final estático Default_Load_Factor = 0.75f; // Este es un umbral. Cuando el número de listas vinculadas en el cubo es mayor que este valor, se convertirá en un árbol rojo y negro. El código del método PUT utiliza static final int treify_threshold = 8; // También es el umbral. Cuando el número de listas vinculadas en el cubo es menor que este valor, el árbol se convierte en una lista vinculada estática final int noteyify_threshold = 6; // Se dice en el código fuente comentario que es: la capacidad mínima del árbol es al menos 4 x treify_threshold = 32. Luego para evitar (volver a evaluar y threatholds) establecido en 64stat en la última intin_treeeify_capacity = 64; Se almacena la matriz de elementos, siempre un múltiplo de 2 nodo transitorio <k, v> [] tabla; conjunto transitorio <map.entry <k, v >> entryset; // El número de elementos almacenados, tenga en cuenta que esto no es igual a la longitud de la matriz. Tamaño transitorio int; // El contador para cada expansión y cambio de estructura de mapa es transitoria int mod; // El valor crítico se expande cuando el tamaño real (capacidad de capacidad * factor de relleno) excede el valor crítico, la capacidad se expande ints umbral; // el factor de relleno Flotfactor de carga flotante final;2: Método de construcción de hashmap
// Constructor para especificar la capacidad inicial y el factor de relleno public HASHMAP (int InitialCapacity, Float LoadFactor) {// La capacidad inicial especificada no es negativa if (InicialCapacity <0) tirar nueva IlegalArgumentException (Capacidad inicial ilegal: +Inicialcapacidad); // la capacidad inicial especificada es mayor que la capacidad máxima, establecida a la capacidad máxima si (Capacidad inicial> inicial); // Maximum_capacity; // La relación de relleno es positiva si (LoadFactor <= 0 || float.isnan (LoadFactor)) arroje nuevo IlegalArgumentException (factor de carga ilegal: +LoadFactor); this.loadFactor = LoadFactor; // Después de especificar la capacidad, el método TableSize para calcular el valor crítico. Si se excede el valor al colocar los datos, se expandirá. El valor es definitivamente un múltiplo de 2.// la capacidad inicial especificada no se ha guardado, y solo se usa para generar un valor crítico this.threshold = tableizeFor (inicialcapacity);} // Este método asegura que siempre devuelve un valor mayor que CAP y un múltiplo de 2. Por ejemplo, pasando en 999 devuelve 1024 estatías intitales finales intitores (int). n >>> 1; n | = n >>> 2; n | = n >>> 4; n | = n >>> 8; n | = n >>> 16; // retorno anidado de los operadores trigonométricos (n <0)? 1: (n> = maximum_capacity)? Maximum_Capacity: n + 1;} // constructor 2public hashmap (int inicialCapacity) {this (inicialCapacity, default_load_factor);} // constructor 3public hashmap () {this.loadfactor = default_load_factor; // Todos los demás campos predeterminados}3: Determine la posición del elemento en la matriz al obtener y poner
static final int hash (clave de objeto) {int h; return (key == null)? 0: (h = key.hashcode ()) ^ (h >>> 16);}Para determinar la ubicación
El primer paso: lo primero es calcular el código hash de la clave, que es un número de tipo int. Los siguientes comentarios H >>> 16 Código fuente dicen: Para evitar colisiones de hash, la posición alta se extiende a la posición baja, que se realiza después de tener en cuenta varios factores, como la velocidad y el rendimiento.
Paso 2: H es el código hash, la longitud es la longitud de la matriz de nodo [] anterior, realice la misma operación H & (longitud-1). Dado que la longitud es un múltiplo de 2-1, su código binario es 1 y el resultado de 1 con otros números puede ser 0 o 1, para garantizar la uniformidad después de la operación. Es decir, el método hash garantiza la uniformidad de los resultados, lo cual es muy importante y afectará en gran medida el rendimiento de PUT y obtendrá el hashmap. Vea la siguiente imagen para comparar:
La figura 3.1 son resultados de hash asimétrico
La figura 3.2 es el resultado del hash equilibrado
No hay muchos datos en estos dos gráficos. Si la lista vinculada es más larga que 8, se convertirá en un árbol rojo y negro. Sería más obvio en ese momento. JDK8 siempre ha sido una lista vinculada antes. La complejidad de la consulta de la lista vinculada es o (n) y la complejidad de los árboles rojos y negros debido a sus propias características es o (log (n)). Si los resultados del hash son desiguales, afectará en gran medida la complejidad de la operación. Hay un <a href = "http://blog.chinaunix.net/uid-26575352-id-3061918.html"> Blog de conocimiento básico de Red and Black Tree </a> Hay otro ejemplo en línea para verificar: un objeto personalizado se usa para hacer claves y ajustar el método hashcode () para que valga la pena que valga la pena.
public class MutableKeyTest {public static void main (string args []) {class mykey {integer i; public void seti (integer i) {this.i = i;} public mykey (Integer i) {this.i = i;}@anveridepublic intSkcode () {// if 1 // return 1retur be implemented @Overridepublic boolean equals(Object obj) {if (obj instanceof MyKey) {return i.equals((((MyKey)obj).i);} else {return false;}}}// My machine configuration is not high. If 25000 is normal for 27ms, you can try 25 million. If hashCode() method returns 1, 2.5 million will be stuck Map<MyKey,String> map = new Hashmap <> (25000,1); fecha begin = new date (); for (int i = 0; i <20000; i ++) {map.put (new myKey (i), "test" + i);} date end = new Date (); System.out.println ("Time (MS)" + (End.GetTime () - Begin.GetTime ()));4: Obtener método
public v get (clave de objeto) {nodo <k, v> e; return (e = getNode (hash (key), key)) == null? nulo: e.Value;} nodo final <k, v> getNode (int hash, clave de objeto) {nodo <k, v> [] tabs; Nodo <k, v> primero, e; int n; K k; // hash & (longitud -1) Obtenga la posición raíz del árbol rojo y negro o el encabezado de la lista vinculada if ((tab = tab.) key.equals (k)))) return First; if ((e = first.next)! = null) {// Si es un árbol, la complejidad de atravesar el árbol rojo y negro es o (log (n)) para obtener el valor de nodo si (primera instancia de treenode) return ((treenode <k, v>) primero) .getTreenod == hash && ((k = e.key) == Key || (Key! = Null && Key.equals (k)))) return e;} while ((e = e.next)! = null);}} return null;}5: Coloque el método, cuando se ponga, localice el cubo de acuerdo con H & (longitud 1) y luego vea si es un árbol rojo y negro o una lista vinculada y Putval
public v put (k key, v value) {return PutVal (hash (clave), clave, valor, falso, verdadero);} final v putval (int hash, k key, v valor, boolean solyifabsent, boolean desalojo) {nodo <k, v> [] tab; Nodo <k, v> p; int n, i; // si la pestaña está vacía o la longitud es 0, la memoria asignada al tamaño () if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize ()). longitud; // (n - 1) y hash encuentra la posición de put. Si está vacío, putif directamente ((p = tab [i = (n - 1) & hash]) == null) tab [i] = newnode (hash, key, value, null); else {nodo <k, v> e; K k; // El valor hash del primer nodo es el mismo, y el valor de la clave es el mismo que la tecla Insertar if (p.hash == hash && ((k = p.key) == clave || (clave! = Null && key.equals (k)))) e = p; else if (p instancia de treenode) // El método de puto de un árbol rojo y negro es relativamente complicado. Después de Putval, debes atravesar todo el árbol. Cuando sea necesario, modifique el valor para garantizar las características del árbol rojo y negro e = ((treeNode <k, v>) p) .putTreeVal (this, tab, hash, key, value); else {// Linked List para (int bincount = 0;; + +bincount) {if ((e = p.next) == null) {// e es vacío, indicando que el valor de la misma manera vacía con el valor del valor con el valor vacío. Fin de la tabla, luego cree un nuevo nodo p.next = newnode (hash, key, valor, nulo); // Después de agregar un nuevo nodo, si el número de nodos alcanza el umbral, convierta la lista vinculada en un árbol rojo y negro si (bincount> = treeify_threshold - 1) // -1 para 1streeifybin (tab, hash); break;} ////1 sea vacía (e.m. hash && ((k = e.key) == Key || (Key! = Null && Key.equals (k)))) Break; P = E;}} // Actualizar el valor del nodo con el mismo valor de hash y valor de clave if (e! = null) {// mapeo existente para keyv antiguo = e.value; if (! soloiFabsent || itlyvalue == nulae == nelle) value; tarloDodeAccess (e); return OldValue;}} ++ modCount; if (++ size> umbral) reize (); foravododeSertion (desalojo); return null;}6: Método de cambio de tamaño
nodo final <k, v> [] resize () {nodo <k, v> [] oldtab = table; int oldCap = (oldtab == null)? 0: Oldtab.length; int Oldthr = Threshold; int NewCap, Newthr = 0; if (OldCap> 0) {if (OldCap> = Maximum_Capacity) {Threshold = Integer.Max_Value; return OldTab;} // Esta oración es más importante, se puede ver que cada expansión es 2 veces más pequeña si ((((neo newCap = newCap << 1 +). && oldCap> = default_initial_capacity) newthr = Oldthr << 1; // umbral doble} else if (Oldthr> 0) // La capacidad inicial se colocó en ThressholdNewCap = Oldthr; else {// cero umbral inicial de umbral utilizando defaultsnewcap = default_initial_capacity; newthr = (int) (default_load_factor * defaultial_initial_capacity);} if (newthr == 0) {float ft = (flat) LoadFactor; Newthr = (NewCap <Maximumum_Capacity && ft <(Float) Maximum_Capacity? (Int) ft: Integer.max_value);} umbral = newthr; @SuppressWarnings ({"" RawTypes "," desanimado "}) nodio <k, v> [] newtab = (nodo <k, v> [k, v> [] vilos Nodo [newCap]; table = newtab; if (oldtab! = Null) {for (int j = 0; j <oldCap; ++ j) {nodo <k, v> e; if ((e = oldtab [j])! = Null) {oldtab [j] = null; if (Next == null) newtab [e.hash & (newcap - 1) TreeNode) ((treeNode <k, v>) e) .split (this, newtab, j, OldCap); else {// preserva ordennode <k, v> lohead = null, lotail = null; node <k, v> hihead = null, hitail = null; node <k, v> next; do {e.next; if ((((e.hash & hiad (lotail == null) lohead = e; elselotail.next = e; lotail = e;} else {if (hitAil == null) hihead = e; elsehitail.next = e; hitail = e;}} while ((e = next)! = null); if (lotail! = null) {loteil.next = null; newtab [j] null) {HitAil.next = null; newtab [j + OldCap] = hihead;}}}}} return newtab;}Lo anterior es el conocimiento relevante sobre el análisis del principio de implementación de Java8 Hashmap introducido por el editor. ¡Espero que te sea útil!