Una pregunta simple de programación Java sobre matrices. Ayude a los expertos principales a verificar el código.

En términos del mecanismo de implementación interna, tanto ArrayList como Vector se almacenan en forma de matriz de Objeto. Cuando agrega elementos a estos dos tipos, si el número de elementos excede la longitud actual de la matriz interna, ambos necesitan extender la longitud de la matriz interna. Vector aumenta automáticamente la longitud de la matriz al doble de la longitud original de forma predeterminada. ArrayList tiene la longitud original del 50%, por lo que el espacio que obtienes al final siempre es mayor de lo que realmente necesitas. Entonces, si va a guardar una gran cantidad de datos en una colección, usar Vector tiene algunas ventajas porque puede evitar una sobrecarga innecesaria de recursos configurando el tamaño inicial de la colección.

Espero que lo siguiente le resulte útil

La diferencia y el uso de ArrayList Vector LinkedList

ArrayList, LinkedList y Vestor implementan java.util.List interfaz, pero tienen diferentes características, principalmente las siguientes:

1. Sincronicidad

ArrayList y LinkedList no están sincronizados, mientras que Vestor sí. Entonces, si se requiere seguridad para subprocesos, puede usar ArrayList o LinkedList, que pueden ahorrar la sobrecarga de la sincronización. Pero en el caso de subprocesos múltiples, a veces es necesario utilizar Vector. Por supuesto, también puede envolver ArrayList y LinkedList de alguna manera para sincronizarlos, pero la eficiencia puede verse reducida.

2. Crecimiento de datos

En términos del mecanismo de implementación interna, tanto ArrayList como Vector se almacenan en forma de matriz de Objeto. Cuando agrega elementos a estos dos tipos, si el número de elementos excede la longitud actual de la matriz interna, ambos necesitan extender la longitud de la matriz interna. Vector aumenta automáticamente la longitud de la matriz al doble de la longitud original de forma predeterminada. ArrayList tiene la longitud original del 50%, por lo que el espacio que obtienes al final siempre es mayor de lo que realmente necesitas. Entonces, si va a guardar una gran cantidad de datos en una colección, usar Vector tiene algunas ventajas porque puede evitar una sobrecarga innecesaria de recursos configurando el tamaño inicial de la colección.

3. Eficiencia de recuperar, insertar y eliminar objetos

En ArrayList y Vector, recupere un objeto de una posición específica (usando el índice), o inserte o elimine un objeto al final. de la colección El tiempo para los objetos es el mismo y se puede expresar como O(1). Sin embargo, si se agregan o eliminan elementos en otra parte del conjunto, el tiempo invertido aumentará linealmente: O (n-i), donde n representa el número de elementos en el conjunto e i representa la posición de índice del elemento agregado o eliminado. ¿Por qué sucede esto? Se cree que al realizar la operación anterior, todos los elementos de la colección después de los elementos i-ésimo e i-ésimo deben realizar la operación de desplazamiento de (n-i) objetos.

En LinkedList, el tiempo dedicado a insertar y eliminar elementos en cualquier posición de la colección es el mismo: O(1), pero es más lento al indexar un elemento, que es O(i), donde i es la posición del índice.

Entonces, si solo deseas buscar elementos en una posición específica o solo agregar o eliminar elementos al final de la colección, puedes usar Vector o ArrayList.

Si se trata de una operación de inserción o eliminación en otras ubicaciones especificadas, es mejor elegir LinkedList

ArrayList y Vector usan matrices para almacenar datos. La cantidad de elementos en esta matriz es mayor que los datos almacenados reales. que se permite agregar e insertar elementos. Indexar elementos directamente por número de serie, pero insertar datos requiere operaciones de memoria, como mover elementos de matriz, por lo que la indexación de datos es rápida y la inserción de datos es lenta. El rendimiento es peor que ArrayList. LinkedList usa una lista doblemente vinculada para el almacenamiento. La indexación de datos por número de serie requiere un recorrido hacia adelante o hacia atrás, pero al insertar datos, solo necesita registrar los elementos antes y después de este elemento, por lo que la inserción es más rápida. !

Las listas lineales, las listas enlazadas y las tablas hash son estructuras de datos de uso común. Al desarrollar Java, JDK nos ha proporcionado una serie de clases correspondientes para implementar estructuras de datos básicas. Estas clases están en el paquete java.util. Este artículo intenta explicar a los lectores la función de cada clase y cómo usarlas correctamente a través de una descripción simple.

Colección

├List

│├LinkedList

│├ArrayList

│└Vector

│ └Pila

└Establecer

Mapa

├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 grupo de objetos, es decir, los elementos de la colección. Algunas Colecciones permiten elementos idénticos y otras no. Algunos tipos y otros no. El SDK de Java no proporciona clases que heredan directamente de la Colección. Las clases proporcionadas por el SDK de Java son todas "subinterfaces" que heredan de la Colección, como List y Set.

Todas las clases que implementan la interfaz Colección deben proporcionar dos constructores estándar: un constructor sin parámetros para crear una Colección vacía y un constructor con parámetros de Colección para crear una nueva Colección. Esta nueva Colección tiene los mismos elementos que la Colección. Colección pasada. El último constructor permite al usuario copiar una Colección.

¿Cómo recorrer cada elemento de la Colección? Independientemente del tipo real de Colección, admite un método iterador (), que devuelve un iterador que puede usarse para acceder a cada elemento de la Colección uno por uno. El uso típico es el siguiente:

Iterador it = collection.iterator(); // Obtener un iterador

while(it.hasNext()) {

Object obj = it.next(); // Obtener el siguiente elemento

}

Las dos interfaces derivadas de la interfaz Collection son List y Set.

Interfaz de lista

La lista es una colección ordenada. Con esta interfaz, puede controlar con precisión la posición de inserción de cada elemento. Los usuarios pueden acceder a los elementos de la Lista utilizando el índice (la posición del elemento en la Lista, similar a un subíndice de matriz), que es similar a una matriz de Java.

A diferencia del Set que se menciona a continuación, List permite los mismos elementos.

Además del método iterator() necesario para la interfaz Collection, List también proporciona un método listIterator(), que devuelve una interfaz ListIterator. En comparación con la interfaz Iterator estándar, ListIterator tiene más add(). Los métodos de clase permiten agregar, eliminar, configurar elementos y avanzar o retroceder.

Las clases comunes que implementan la interfaz List incluyen LinkedList, ArrayList, Vector y Stack.

Clase LinkedList

LinkedList implementa la interfaz List y permite elementos nulos. Además, LinkedList proporciona métodos adicionales de obtención, eliminación e inserción al principio o al final de LinkedList. Estas operaciones permiten que LinkedList se utilice como pila, cola o deque.

Tenga en cuenta que LinkedList no tiene métodos de sincronización. Si varios subprocesos acceden a una Lista al mismo tiempo, deben implementar la sincronización de acceso ellos mismos. Una solución es construir una Lista sincronizada al crear la Lista:

List list = Collections.synchronizedList(new LinkedList(...));

ArrayList class

<); p>ArrayList implementa una matriz de tamaño variable. Permite todos los elementos, incluido nulo. ArrayList no está sincronizado.

El tiempo de ejecución de los métodos size, isEmpty, get y set es constante. Sin embargo, el costo del método de suma es una constante amortizada y agregar n elementos requiere O(n) tiempo. Otros métodos tienen un tiempo de ejecución lineal.

Cada instancia de ArrayList tiene una capacidad (Capacity), que es el tamaño del array utilizado para almacenar elementos. Esta capacidad aumenta automáticamente a medida que se agregan nuevos elementos, pero el algoritmo de crecimiento no está definido. Cuando es necesario insertar una gran cantidad de elementos, se puede llamar al método sureCapacity para aumentar la capacidad de ArrayList antes de insertarlo para mejorar la eficiencia de la inserción.

Al igual que LinkedList, ArrayList tampoco está sincronizado.

Clase Vector

Vector es muy similar a ArrayList, pero Vector está sincronizado. Aunque el Iterador creado por Vector tiene la misma interfaz que el Iterador creado por ArrayList, debido a que Vector está sincronizado, cuando se crea y se utiliza un Iterador, otro hilo cambia el estado del Vector (por ejemplo, agregando o eliminando algún elemento) , Se generará ConcurrentModificationException al llamar al método Iterator, por lo que se debe detectar la excepción.

Clase Stack

Stack hereda de Vector e implementa una pila de último en entrar, primero en salir. Stack proporciona 5 métodos adicionales que permiten utilizar Vector como pila. Los métodos básicos push y pop, así como el método peek, colocan el elemento 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. La pila es una pila vacía después de su creación.

Interfaz Set

Set es una colección que no contiene elementos repetidos, es decir, dos elementos cualesquiera e1 y e2 tienen e1.equals(e2)=false, Set tiene el mayor Hay un elemento nulo.

Obviamente, el constructor Set tiene la restricción de que el parámetro Collection pasado no puede contener elementos duplicados.

Tenga en cuenta: los objetos mutables deben manipularse con cuidado.

Si un elemento mutable en un Conjunto cambia su estado causando Object.equals(Object)=true, causará algunos problemas.

Interfaz de mapa

Tenga en cuenta que Map no hereda la interfaz de Colección. 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 del Mapa proporciona tres tipos de vistas de conjuntos. El contenido del Mapa puede considerarse como un conjunto de conjuntos de claves, un conjunto de conjuntos de valores o un conjunto de asignaciones de valores clave.

Clase Hashtable

Hashtable hereda la interfaz Map e implementa una tabla hash de mapeo clave-valor. Cualquier objeto no nulo se puede utilizar como clave o valor.

Para agregar datos, use put(key, value) y para eliminar datos, use get(key). El costo de tiempo de estas dos operaciones básicas es constante.

Hashtable ajusta el rendimiento a través de dos parámetros: capacidad inicial y factor de carga. Normalmente, el factor de carga predeterminado de 0,75 logra un mejor equilibrio entre tiempo y espacio. Aumentar el factor de carga puede ahorrar espacio, pero el tiempo de búsqueda correspondiente aumentará, lo que afectará operaciones como get y put.

Un ejemplo simple del uso de Hashtable es el siguiente. Coloque 1, 2 y 3 en Hashtable, y sus claves son "uno", "dos" y "tres" respectivamente:

Números de tabla hash = new Hashtable();

números.put(“uno”, nuevo entero(1));

números.put(“dos”, nuevo entero( 2)) ;

numbers.put(“tres”, new Integer(3));

Para recuperar un número, como 2, use la clave correspondiente:

Entero n = (Entero)números.get(“dos”);

System.out.println(“dos =” + n

Desde el objeto); como pasará la clave Su función hash se calcula para determinar la posición del valor correspondiente, por lo que cualquier objeto utilizado como clave debe implementar los métodos hashCode y equals. Los métodos hashCode y equals heredan de la clase raíz Object. 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 iguales, es decir, obj1.equals (. obj2) = verdadero, entonces su código hash debe ser el mismo, pero si dos objetos son diferentes, su código hash no es necesariamente diferente. Si el código hash de dos objetos diferentes es el mismo, este fenómeno se denomina conflicto. El tiempo de sobrecarga de operación de la tabla hash aumentará. Por lo tanto, intente definir un método hashCode() bien definido para acelerar las operaciones de la tabla hash.

Si el mismo objeto tiene diferentes hashCode, la operación de la tabla hash tendrá resultados inesperados (el método get esperado devuelve nulo). Para evitar este problema, solo necesitas recordar una cosa: ambos en el. Al mismo tiempo, anule el método equals y el método hashCode, en lugar de simplemente escribir uno de ellos.

Hashtable es sincrónico.

Clase HashMap

HashMap es similar a Hashtable, excepto que HashMap es asíncrono y permite valores nulos, es decir, valores nulos y claves nulas. , pero cuando se trata a HashMap como una Colección (el método de valores() puede devolver una Colección), su costo de tiempo de suboperación de iteración es proporcional a la capacidad de HashMap.

Por lo tanto, si el rendimiento de las operaciones iterativas es muy importante, no establezca la capacidad inicial de HashMap demasiado alta ni el factor de carga demasiado bajo.

Clase WeakHashMap

WeakHashMap es un HashMap mejorado, que implementa "referencias débiles" a claves. Si ya no se hace referencia a una clave externamente, GC puede reciclar la clave.

Resumen

Si hay operaciones como pilas y colas involucradas, debería considerar usar List. Para una inserción y eliminación rápida de elementos, debe usar LinkedList si necesita un acceso aleatorio rápido. a elementos, debes usar ArrayList.

Si el programa está en un entorno de un solo subproceso, o el acceso se realiza solo en un subproceso, considere las clases asincrónicas, que son más eficientes. Si varios subprocesos pueden operar una clase al mismo tiempo, las clases sincronizadas. debe usarse.

Presta especial atención al funcionamiento de la tabla hash. El objeto utilizado como clave debe sobrescribir correctamente los métodos equals y hashCode.

Intente devolver la interfaz en lugar del tipo real, como devolver List en lugar de ArrayList, de modo que si necesita reemplazar ArrayList con LinkedList en el futuro, no sea necesario cambiar el código del cliente. Esto es programación para la abstracción.

Sincronicidad

El vector está sincronizado. Algunos métodos de esta clase garantizan que los objetos de Vector sean seguros para subprocesos. ArrayList es asincrónico, por lo que los objetos en ArrayList no son seguros para subprocesos. Debido a que los requisitos de sincronización afectarán la eficiencia de la ejecución, si no necesita una colección segura para subprocesos, usar ArrayList es una buena opción para evitar una sobrecarga de rendimiento innecesaria causada por la sincronización.

Crecimiento de datos

En términos del mecanismo de implementación interna, tanto ArrayList como Vector utilizan matrices (Array) para controlar los objetos de la colección. Cuando agrega elementos a estos dos tipos, si el número de elementos excede la longitud actual de la matriz interna, ambos necesitan extender la longitud de la matriz interna. Vector aumenta automáticamente la longitud de la matriz al doble de la longitud original de forma predeterminada. ArrayList tiene la longitud original del 50%, por lo que el espacio que obtienes al final siempre es mayor de lo que realmente necesitas. Entonces, si va a guardar una gran cantidad de datos en una colección, usar Vector tiene algunas ventajas porque puede evitar una sobrecarga innecesaria de recursos configurando el tamaño inicial de la colección.

Patrón de uso

En ArrayList y Vector, el tiempo que lleva encontrar datos de una posición específica (a través del índice) o agregar o eliminar un elemento al final de la colección es similar , usamos O (1) para representar este tiempo. Sin embargo, si se agregan o eliminan elementos en otra parte del conjunto, el tiempo invertido aumentará linealmente: O (n-i), donde n representa el número de elementos en el conjunto e i representa la posición de índice del elemento agregado o eliminado. ¿Por qué sucede esto? Se cree que al realizar la operación anterior, todos los elementos de la colección después de los elementos i-ésimo e i-ésimo deben realizar operaciones de desplazamiento. ¿Qué significa todo esto?

Esto significa que si solo desea buscar elementos en una posición específica o solo agregar o eliminar elementos al final de la colección, puede usar Vector o ArrayList. Si se trata de otras operaciones, será mejor que elija otras clases de operaciones de recopilación. Por ejemplo, la clase de colección LinkList tarda el mismo tiempo en agregar o eliminar elementos en cualquier posición de la colección O (1), pero es más lento en indexar un elemento: O (i), donde i es la ubicación del índice. Usar un ArrayList también es fácil porque simplemente puedes usar el índice en lugar de crear un objeto iterador. LinkList también crea objetos para cada elemento insertado, por lo que debes comprender que también genera una sobrecarga adicional.

Finalmente, en el libro "Practical Java", Peter Haggar sugiere usar una matriz simple (Array) en lugar de Vector o ArrayList. Esto es especialmente cierto para programas que requieren una alta eficiencia de ejecución.

Porque el uso de una matriz (Array) evita la sincronización, llamadas a métodos adicionales y reasignaciones innecesarias de espacio.