Las tablas lineales, las listas vinculadas y las tablas hash son estructuras de datos utilizadas comúnmente. Al desarrollar Java, JDK nos ha proporcionado una serie de clases correspondientes para implementar estructuras de datos básicas. Estas clases están todas en el paquete java.util. Este artículo intenta explicar a los lectores el papel de cada clase y cómo usarlos correctamente a través de una descripción simple.
Colección ├list │✜linkedList │✜ArrayList │└Vector │└Stack └set Map ├hashtable ├hashmap └weakhashmap
Interfaz de colección
La colección es la interfaz de colección más básica. Una colección representa un conjunto de objetos, es decir, los elementos de la colección (elementos). Algunas colecciones permiten los mismos elementos, mientras que otras no. Algunos pueden ordenarse, pero otros no pueden. El Java SDK no proporciona clases que se heredan directamente de la recolección. Las clases proporcionadas por Java SDK son todas "subinterfaces" que se heredan de la colección como List and Set.
Todas las clases que implementan la interfaz de colección deben proporcionar dos constructores estándar: el constructor sin parámetros se utiliza para crear una colección vacía, y se utiliza un constructor de parámetros de colección para crear una nueva colección, que tiene los mismos elementos que la colección entrante. El último constructor permite al usuario copiar una colección.
¿Cómo iterar a través de cada elemento de una colección? Independientemente del tipo real de la colección, admite un método Iterator (), que devuelve un iterador, y utiliza este iterador para acceder a cada elemento en la colección uno por uno.
Los usos típicos son los siguientes:
Iterador it = collection.iterator (); // Obtener un iterador while (it.hasnext ()) {object obj = it.next (); // Obtén el siguiente elemento} Las dos interfaces derivadas de la interfaz de colección son listas y establecidas.
Interfaz de lista
La lista es una colección ordenada, y el uso de esta interfaz le permite controlar con precisión la posición de cada inserción de elementos. Los usuarios pueden usar índices (la posición de los elementos en la lista, similares a los subíndices de matriz) para acceder a elementos en la lista, que es similar a las matrices de Java.
A diferencia del conjunto mencionado a continuación, la lista permite los mismos elementos.
Además del método Iterator () que tiene el método iterador () necesario, la lista también proporciona un método ListIterator (), que devuelve una interfaz ListIterator. En comparación con la interfaz iteradora estándar, ListIterator tiene más métodos como add (), permitiendo agregar, eliminar, configurar elementos y atravesar hacia adelante o hacia atrás.
Las clases comunes que implementan interfaces de lista incluyen LinkedList, ArrayList, Vector y Stack.
Clase de LinkedList
LinkedList implementa la interfaz de la lista, permitiendo elementos nulos. Además, LinkedList proporciona métodos adicionales Get, Eliminar, Insertar en el encabezado o la cola de LinkedList. Estas operaciones permiten que LinkedList se use como pila, cola o cola de dos vías.
Tenga en cuenta que LinkedList no tiene un método sincrónico. Si varios subprocesos acceden a una lista al mismo tiempo, debe implementar la sincronización de acceso usted mismo. Una solución es construir una lista sincrónica al crearla:
List list = collections.synchronizedList (new LinkedList (...));
Clase ArrayList
ArrayList implementa matrices de tamaño variable. Permite todos los elementos, incluido NULL. ArrayList no está sincronizada.
El tiempo de ejecución del tamaño, isEmty, get, set métodos es constante. Sin embargo, la sobrecarga del método ADD es una constante amortizada, y se necesita tiempo para agregar N elementos. Los otros métodos tienen tiempo de ejecución lineal.
Cada instancia de ArrayList tiene una capacidad, que es el tamaño de la matriz utilizada para almacenar elementos. Esta capacidad puede aumentar automáticamente a medida que se agregan constantemente elementos nuevos, pero el algoritmo de crecimiento no está definido. Cuando se necesita insertar una gran cantidad de elementos, se puede llamar al método Ensurecapacity antes de insertar para aumentar la capacidad de ArrayList para mejorar la eficiencia de la inserción.
Al igual que LinkedList, ArrayList también no está sincronizado.
Clase vectorial
El vector es muy similar a ArrayList, pero el vector es sincrónico. Aunque el iterador creado por vector es la misma interfaz que el iterador creado por ArrayList, debido a que el vector se sincroniza, cuando se crea un iterador y se usa, otro subproceso cambia el estado del vector (por ejemplo, por ejemplo, agregando o eliminando algunos elementos), se lanza una medición de medición concurrente cuando se lanza el método de iterador, por lo tanto, la excepción debe ser ceñida.
Clase de pila
La pila hereda de Vector, implementando una pila de primera entrada. Stack proporciona 5 métodos adicionales para permitir que Vector se utilice como pila. Los métodos básicos de empuje y POP, y el método PEEK obtienen los elementos en la parte superior de la pila, el método vacío prueba si la pila está vacía y el método de búsqueda detecta la posición de un elemento en la pila. Stack acaba de crear y es una pila vacía.
Establecer interfaz
SET es una colección que no contiene elementos duplicados, es decir, dos elementos E1 y E2 tienen E1.Equals (E2) = False, y SET tiene como máximo un elemento nulo.
Obviamente, el constructor de SET tiene una restricción, y el parámetro de recolección aprobado no puede contener elementos duplicados.
Tenga en cuenta: los objetos mutables deben operarse con cuidado. Si un elemento mutable en un conjunto cambia su propio estado, causa objeto.equals (objeto) = verdadero para causar algunos problemas.
Interfaz de mapa
Tenga en cuenta que MAP no hereda la interfaz de colección, y MAP proporciona una asignación de clave a valor. Un mapa no puede contener la misma clave, y cada clave solo puede asignar un valor. La interfaz MAP proporciona tres tipos de vistas de la colección. El contenido del mapa puede considerarse como un conjunto de colecciones de clave, un conjunto de colecciones de valor o un conjunto de asignaciones de valor clave.
Clase hashtable
Hashtable implementa la interfaz MAP para implementar una tabla hash con un mapeo de valor clave. Cualquier objeto no nulo se puede usar como clave o valor.
Use Put (clave, valor) para agregar datos, use Get (Key) para recuperar datos. La sobrecarga de tiempo de estas dos operaciones básicas es constante.
La hashtable ajusta el rendimiento a través de la capacidad inicial y los parámetros del factor de carga. Por lo general, el factor de carga predeterminado 0.75 puede lograr mejor el tiempo y el equilibrio de espacio. Aumentar el factor de carga puede ahorrar espacio, pero el tiempo de búsqueda correspondiente aumentará, lo que afectará las operaciones como Get and Put.
Un ejemplo simple de usar un hashtable es el siguiente: poner 1, 2 y 3 en un hashtable, y sus claves son "una", "dos", "tres" respectivamente:
HASHTABLE NÚMEROS = new Hashtable ();
números.put ("one", nuevo entero (1));
números.put ("dos", nuevo entero (2));
números.put ("tres", nuevo entero (3));
Para sacar un número, como 2, use la clave correspondiente:
Entero n = (entero) números.get ("dos");
System.out.println ("two =" + n);
Dado que un objeto como clave determinará la posición del valor correspondiente calculando su función hash, cualquier objeto como clave debe implementar los métodos hashcode e igual. El hashcode y los métodos equivalentes heredan del objeto de clase raíz. Si usa una clase personalizada como clave, tenga mucho cuidado. De acuerdo con la definición de la función hash, si los dos objetos son los mismos, es decir, obj1.equals (obj2) = verdadero, su húsico debe ser el mismo, pero si los dos objetos son diferentes, sus hascones pueden no ser diferentes. Si los hashcodes de dos objetos diferentes son los mismos, este fenómeno se llama conflicto. El conflicto aumentará la sobrecarga del tiempo de operar la tabla hash. Por lo tanto, intente definir el método hashcode () para acelerar el funcionamiento de la tabla hash.
Si el mismo objeto tiene diferentes hashcodes, la operación en la tabla hash tendrá resultados inesperados (el método get esperado devuelve nulo). Para evitar este problema, solo necesita recordar una cosa: debe reescribir el método igual y el método hashcode al mismo tiempo, en lugar de simplemente escribir uno de ellos.
La hashtable está sincronizada.
Clase de hashmap
Hashmap es similar a la hashtable, la diferencia es que HASHMAP es asíncrono y permite que NULL, es decir, valor nulo y clave nula. , pero cuando hashmap se considera una colección (el método valores () puede devolver una colección), su gastos generales de tiempo de suboperación iterativo es proporcional a la capacidad de HASHMAP. Por lo tanto, si el rendimiento de las operaciones de iteración es muy importante, no establece que la capacidad de inicialización de HASHMAP sea demasiado alta o el factor de carga es demasiado bajo.
Clase de Deakhashmap
Deakhashmap es un hashmap mejorado que implementa una "referencia débil" a la clave. Si ya no se hace referencia a una clave externamente, la clave puede ser reciclada por GC.
Resumir
Si la pila, la cola y otras operaciones están involucradas, debe considerar el uso de la lista. Para elementos que deben insertarse y eliminarse rápidamente, debe usar LinkedList. Si se deben acceder a elementos rápidamente, debe usar ArrayList.
Java.util.Collections Class Package
La clase java.util.collections contiene muchos métodos útiles que pueden facilitar el trabajo de los programadores, pero estos métodos generalmente no se utilizan completamente. Javadoc ofrece la descripción más completa de la clase de colecciones: "Esta clase contiene una clase estática dedicada que puede operar o devolver una colección.
"1.2 Métodos incluidos
Iterador, arraylist, elementos, búfer, mapa, colecciones
Liezi:
import java.util.arrayList; import java.util.collection; import java.util.collections; importar java.util.comparator; import java.util.list; Public Class CollectionsSort {public CollectionsSort () {} public static void main (string [] args) {double array [] = {111, 111, 23, 456, 231}; List List = new ArrayList (); List li = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new Double (Array [i])); //list.add(""+Array[i]); } doble arr [] = {111}; for (int j = 0; j <arr.length; j ++) {li.add (new double (arr [j])); }}2. Operaciones específicas
1) Sort (ordenar)
Use el método de clasificación para ordenar la lista especificada en orden ascendente de acuerdo con el orden natural de los elementos. Todos los elementos de la lista deben implementar la interfaz comparable. Todos los elementos de esta lista deben compararse entre sí utilizando el comparador especificado
Doble matriz [] = {112, 111, 23, 456, 231}; for (int i = 0; i <array.length; i ++) {list.add (new Double (Array [i])); } Colección.sort (lista); for (int i = 0; i <array.length; i ++) {system.out.println (li.get (i)); } // Resultado: 112,111,23,456,2312) barajarse
El algoritmo de disposición híbrido hace exactamente lo contrario del tipo: interrumpe cualquier permutación que se pueda encontrar en una lista. Es decir, la lista se reorganiza en función de la entrada de la fuente aleatoria, dicha disposición tiene la misma posibilidad (suponiendo que la fuente aleatoria sea justa). Este algoritmo es muy útil para implementar un juego de suerte. Por ejemplo, se puede usar para mezclar una lista de objetos de cartas que representan un mazo de cartas. Además, también es muy útil al generar casos de prueba.
Colección.shuffling (list) Double Array [] = {112, 111, 23, 456, 231}; for (int i = 0; i <array.length; i ++) {list.add (new Double (Array [i])); } Colección.shuffle (lista); for (int i = 0; i <array.length; i ++) {system.out.println (li.get (i)); } // Resultado: 112,111,23,456,2313) Reverse
Use el método inverso para ordenar la lista especificada en orden descendente de acuerdo con el orden natural de los elementos.
Colección.reverse (list) Double Array [] = {112, 111, 23, 456, 231}; for (int i = 0; i <array.length; i ++) {list.add (new Double (Array [i])); } Colecciones. reverso (lista); for (int i = 0; i <array.length; i ++) {system.out.println (li.get (i)); } // Resultado: 231,456,23,111,112 4) Reemplace todos los elementos en la lista especificada con el elemento especificado. Cadena str [] = {"dd", "aa", "bb", "cc", "ee"}; for (int j = 0; j <str.length; j ++) {li.add (nueva cadena (str [j])); } Colección.fill (li, "aaa"); for (int i = 0; i <li.size (); i ++) {system.out.println ("list [" + i + "] =" + li.get (i)); } // Resultado: AAA, AAA, AAA, AAA5) Copia (copia)
Use dos parámetros, una lista de destino y una lista de origen, para copiar el elemento de origen al destino y sobrescribir su contenido. La lista de destino es al menos tanto como la fuente. Si es más largo, los elementos restantes en la lista de destino no se ven afectados.
Collections.copy (list, li): el último parámetro es la lista de destino, la anterior es la lista de origen
Doble matriz [] = {112, 111, 23, 456, 231}; List List = new ArrayList (); List li = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new Double (Array [i])); } doble arr [] = {1131,333}; Cadena str [] = {"dd", "aa", "bb", "cc", "ee"}; for (int j = 0; j <arr.length; j ++) {li.add (new double (arr [j])); } Colección.copy (list, li); for (int i = 0; i <list.size (); i ++) {system.out.println ("list [" + i + "] =" + list.get (i)); } // Resultado: 1131,333,23,456,2316) Devuelve el elemento más pequeño en las colecciones (min)
Devuelve el elemento más pequeño de la colección dada de acuerdo con el orden en que se genera el comparador especificado. Todos los elementos de la colección deben compararse entre sí a través del comparador especificado
Colección.min (list) Double Array [] = {112, 111, 23, 456, 231}; List List = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new Double (Array [i])); } Colección.min (lista); for (int i = 0; i <list.size (); i ++) {system.out.println ("list [" + i + "] =" + list.get (i)); } // resultado: 237) Devuelve el elemento más pequeño (máximo) en las colecciones
Devuelve el elemento máximo de la colección dada de acuerdo con el orden en el que se genera el comparador especificado. Todos los elementos de la colección deben compararse entre sí a través del comparador especificado
Colección.max (list) Double Array [] = {112, 111, 23, 456, 231}; List List = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new Double (Array [i])); } Colección.max (lista); for (int i = 0; i <list.size (); i ++) {system.out.println ("list [" + i + "] =" + list.get (i)); } // resultado: 4568) lastindexofsublist
Devuelve la posición inicial de la lista de destino especificada que apareció por última vez en la lista de origen especificada
int count = Collections.lastIndexOfSublist (List, Li); Doble matriz [] = {112, 111, 23, 456, 231}; List List = new ArrayList (); List li = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new Double (Array [i])); } doble arr [] = {111}; Cadena str [] = {"dd", "aa", "bb", "cc", "ee"}; for (int j = 0; j <arr.length; j ++) {li.add (new double (arr [j])); } INT ubicaciones = colecciones. lastindexofsublist (lista, li); System.out.println ("==="+ ubicaciones); // resultado 39) índicefsublist
Devuelve la posición inicial de la primera vez que la lista de destino especificada aparece en la lista de origen especificada
int count = Collections.IndexOfSublist (List, Li); Doble matriz [] = {112, 111, 23, 456, 231}; List List = new ArrayList (); List li = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new Double (Array [i])); } doble arr [] = {111}; Cadena str [] = {"dd", "aa", "bb", "cc", "ee"}; for (int j = 0; j <arr.length; j ++) {li.add (new double (arr [j])); } Int ubicaciones = colección.indexofsublist (list, li); System.out.println ("==="+ ubicaciones); // resultado 110) Rotar
Mueve cíclicamente elementos en la lista especificada basada en la distancia especificada
Colección.rotate (lista, -1);
Si es un número negativo, se mueve positivamente, y si se mueve positivamente, se mueve positivamente.
Doble matriz [] = {112, 111, 23, 456, 231}; List List = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new Double (Array [i])); } Colección.rotate (lista, -1); for (int i = 0; i <list.size (); i ++) {system.out.println ("list [" + i + "] =" + list.get (i)); } // Resultado: 111,23,456,231,112El artículo anterior analiza brevemente la recopilación y el mapa de las clases de implementación de las estructuras de datos de uso común en Java. Este es todo el contenido que he compartido contigo. Espero que pueda darle una referencia y espero que pueda apoyar más a Wulin.com.