Durante mucho tiempo, la lista de datos que se usa con más frecuencia en el código es principalmente una lista, y todos son ArrayList. Parece que esto es suficiente. ArrayList es una clase de herramienta de envoltura utilizada para implementar matrices dinámicas, de modo que al escribir código, puede entrar y salir, iterar y recorrer, lo cual es bastante conveniente.
No sé cuándo comencé a comenzar lentamente las clases de herramientas como Hashmap y Hashset a menudo aparecen en el código. Debe decirse que HASHMAP es más común, y también es una pregunta de entrevista clásica, por lo que leeré más en la vida diaria. Cuando comencé a usarlo, simplemente lo entendí como una tabla correspondiente de valor clave, y es más conveniente usar claves para encontrar datos. Después de una investigación adicional, descubrí
Esta cosa tiene algunos secretos, especialmente después de que la nueva versión de JDK cambia el hashmap a un árbol, el código es un poco complicado.
Comencé a usar menos set, pero accidentalmente encontré un conjunto de árboles en un código. Descubrí que esta clase puede venir con suavidad. Se sintió bastante interesante. Poco a poco descubrí que esta también es una buena herramienta.
Si escribe demasiado código, sentirá la importancia de lo básico, así que aquí escribo un artículo breve para organizar brevemente algún conocimiento sobre la colección.
Ok, solucionemos brevemente:
• Lista: es decir, una lista, que admite las funciones de matrices y listas vinculadas, y generalmente es lineal.
• Mapa: es una tabla de mapeo, que almacena la relación correspondiente entre claves y valores.
• Establecer: Medios establecidos, utilizados principalmente para ordenar los datos y clasificar
Echemos un vistazo a la lista
La lista es una ventana para almacenar datos lineales, como: ArrayList para Arrays y LinkedList para listas vinculadas.
Lista de matriz
Esta es una lista de matriz, pero proporciona una función de expansión automática para realizar la interfaz de la lista. Se accede a operaciones externas a través del método de declaración de interfaz, que es seguro y conveniente.
La clave para ArrayList es la expansión de capacidad automática. La capacidad inicial se puede establecer cuando se inicializa el objeto o se puede medir la capacidad predeterminada. Si el tamaño de la matriz no es particularmente claro, el tamaño inicial no se puede especificar. Si está claro, se puede especificar un tamaño, lo que reduce el retraso causado por la expansión dinámica. Hablando de esto, necesitamos hablar sobre cómo se implementa la expansión. Mira el siguiente código:
Private void Grow (int mincapacity) {// Overflow-Concscious Code int OldCapacity = elementData.length; int newCapacity = OldCapacity + (OldCapacity >> 1); if (newCapacity - mincapacity <0) newCapacity = mincapacity; if (newCapacity - max_array_size> 0) newCapacity = HugeCapacity (mincapacity); // La mincapacidad generalmente está cerca del tamaño, por lo que esta es una victoria: elementData = arrays.copyOf (elementData, newCapacity); }Grow es un método que desencadena ArrayList al agregar elementos o algunas verificaciones fáciles. Proceso principal:
1. Obtenga la longitud de la matriz y muévala correctamente, lo que es equivalente a la capacidad antigua/2, y obtenga la nueva longitud
2. Si esta longitud es menor que la capacidad mínima, es fácil usarla directamente.
3. Si es mayor que el máximo, tome un valor máximo. Aquí se llamará a un método de HugeCapacity, principalmente para comparar mincapacity con max_array_size. Si MinCapacity es mayor que max_array_size, tome integer.max_value, de lo contrario, tome max_array_size. Curiosamente, max_array_size toma integer.max_value - 8; No sé cuál es el significado de hacer esto
4. Finalmente, llame a un método de copia para copiar el número existente en una nueva matriz.
Debido a este proceso de copia, si la matriz es relativamente grande, la expansión ciertamente causará retraso. Entonces, si conoce el valor máximo desde el principio y es fácil crecer a este valor, entonces especificar el tamaño al comenzar la inicialización tendrá un cierto efecto.
Linkedlist
Esta es una clase de herramientas para listas vinculadas. Las ventajas de las listas vinculadas son que agregan y eliminan las cosas más rápido, pero las encontrarán más lentas.
En cuanto al código, parece que nada especial es que está vinculado por una cadena de punteros. Por supuesto, Java usa objetos en su lugar para crear un objeto de nodo. El nodo en sí apunta al nodo anterior y al siguiente nodo. Esta es la estructura de la lista vinculada:
Nodo de clase estática privada <E> {E item; Nodo <E> siguiente; Nodo <E> anterior; Nodo (nodo <E> prev, e elemento, nodo <E> next) {this.item = element; this.next = siguiente; this.prev = prev; }}Luego use dos nodos para apuntar a la cabeza y la cola y está hecho. El siguiente código:
/*** Puntero al primer nodo. * Invariante: (primero == NULL && Last == NULL) || * (first.prev == null && first.item! = NULL) */ NODO TRANSIENTE <E> Primero; /*** Puntero al último nodo. * Invariante: (primero == NULL && Last == NULL) || * (last.next == null && last.item! = null) */ nodo transitorio <e> last;
Ver una operación de agregar:
/*** Enlace E como último elemento. */ void linklast (e e) {nodo final <e> l = último; nodo final <E> newnode = nuevo nodo <> (l, e, nulo); Último = Newnode; if (l == null) primero = newnode; else L.Next = Newnode; tamaño ++; ModCount ++; }El pasado es:
1. Obtenga el último nodo y póngalo en L
2. Cree un nuevo nodo y obtenga los datos en este nodo. El proceso de creación apuntará la previa del nuevo nodo a L, para que se conecte a la cadena.
3. Luego apunte a este nuevo nodo
4. Luego determine si L es nulo. Si NULL es nulo, significa que es una lista vinculada vacía. El nuevo nodo es el primer elemento. De esta manera, el primero también debe apuntar a Newnode
5. Si no está vacío, apunte al siguiente a Newnode
6. Contador de acumulación
La operación de eliminación también es el nodo delantero y posterior que apunta a la operación de movimiento de este nodo.
Echemos un vistazo al mapa
MAP es una aplicación de una tabla de mapeo para claves y valores. Las principales clases de implementación: Hashmap, Hashtable, Treemap
Hashmap y hashtable
Hashmap es el que utiliza el algoritmo hash para el mapeo de valor clave. Hashtable es una clase segura de hilo con sincronización. Esta es la principal diferencia entre ellos. El principio es similar, y todos se logran a través de la combinación de cadena de cubo +. El cubo se usa para almacenar claves, y el valor debe almacenarse en una lista vinculada debido a la colisión hash.
• La importancia del cubo radica en la eficiencia y puede colocarse en un paso a través de los cálculos hash.
• El significado de las listas vinculadas es acceder a los datos del hash repetido
El principio específico que escribí un "Notas de estudio: hashtable y hashmap" antes
Pero acabo de ver que el hashmap de JDK1.8 ha cambiado su estructura de almacenamiento y adopta una estructura de árbol rojo y negro. ¿Esto puede resolver la eficiencia de la búsqueda de listas vinculadas? No se realizó un estudio detallado.
Treemap
Después de leer el Código de Treemap, descubrí que todavía uso la estructura del árbol, los árboles rojos y negros. Dado que se ordenan los árboles rojos y negros, naturalmente tienen la función de clasificación. Por supuesto, también puede especificar el método de comparación a través del comparador para lograr una clasificación específica.
Debido a que la estructura del árbol se usa para almacenar, será más problemático agregar y eliminar datos. Echemos un vistazo al código de put:
public v put (k key, V value) {Entry <k, v> t = root; if (t == null) {compare (clave, clave); // escriba (y posible nulo) verifica root = nueva entrada <> (clave, valor, nulo); tamaño = 1; ModCount ++; regresar nulo; } int cmp; Entrada <k, v> padre; // Comparador dividido y comparador comparable Comparador <? Super K> CPR = Comparador; if (cpr! = null) {do {parent = t; CMP = CPR.Compare (Key, T.Key); if (cmp <0) t = t.left; else if (cmp> 0) t = t.right; else return t.setValue (valor); } while (t! = null); } else {if (key == null) tire nuevo nullpointerException (); @SupessWarnings ("no está marcado") Comparable <? super k> k = (comparable <? Super k>) clave; do {parent = t; cmp = k.compareto (t.key); if (cmp <0) t = t.left; else if (cmp> 0) t = t.right; else return t.setValue (valor); } while (t! = null); } Entrada <k, v> e = nueva entrada <> (clave, valor, parent); if (cmp <0) parent.left = e; el más parent.right = e; fixafterinsertion (e); tamaño ++; ModCount ++; regresar nulo; }1. Primero verifique si el nodo raíz existe. Si no existe, significa que es la primera pieza de datos y se usa directamente como la raíz del árbol.
2. Determine si hay un comparador. Si lo hay, use el comparador para encontrar la ubicación de almacenamiento de los datos. Si el resultado del comparador regresa es inferior a 0, tome la izquierda y tome la derecha, de lo contrario, reemplace el valor del nodo actual directamente.
3. Si no hay comparador, la clave se compara directamente con la clave del nodo. La comparación es la misma que el método anterior.
4. El siguiente paso es crear un nodo infantil en el padre encontrado y ponerlo en los nodos infantiles izquierdo o derecho.
5. Fixafterinsion es para nodos de color
6. Procesamiento del acumulador
También será un poco problemático al eliminar los datos. Además de eliminar los datos, también debe reequilibrar los árboles rojos y negros.
Además, TreemAP implementa la interfaz NavigableMap <K, V>, por lo que también proporciona algunas operaciones de retorno en el conjunto de datos.
Finalmente, eche un vistazo al set
El conjunto tiene principalmente dos tipos de aplicaciones: hashset y Treeset.
Hashset
El significado literal es muy claro, utilizando una colección de hash. La característica de esta colección es usar el algoritmo hash para almacenar datos, por lo que los datos no están duplicados y el acceso es relativamente rápido. ¿Cómo se hizo?
public boolean add (e e) {return map.put (e, presente) == null; }Resulta que hay un objeto de mapa. Veamos qué es el mapa?
Hashmap transitorio privado <e, objeto> mapa;
Es un hashmap. Aquellos que conocen HashMap comprenderán que dichos datos no se repetirán. Debido a que el objeto en sí se almacena como una clave cuando se deposita, solo existirá una copia en el hashmap.
Después de entender esto y otras cosas, lo entenderás muy bien.
Árbol de árboles
Este conjunto se utiliza para clasificar el conjunto, lo que significa que, además de la capacidad de clasificar pesado, también puede tener su propia función de clasificación. Pero después de mirar el Código de Treeset, descubrí que se implementaba en los conceptos básicos de Treemap. Más precisamente, debería ser una clase derivada de navegable. TreeSet se basa en Treemap sin especificar MAP por defecto.
public treeSet () {this (new Treemap <e, object> ()); }Entonces, ¿a qué podemos prestar más atención aquí es cómo TreeSet es pesado? Echemos un vistazo al método de ADD:
public boolean add (e e) {return m.put (e, presente) == null; }Es algo similar a Hashset, que se basan en las características del mapa para lograr una carga pesada. Es realmente simple y efectivo.
Lo anterior es la explicación detallada de Set, List y Map en Java que el editor le trae. Espero que puedas apoyar a Wulin.com más ~