The difference and usage of array list Vector LinkedList

ArrayList and Vector store data in an array. The number of elements in this array is greater than the actual stored data of added and inserted elements, both of which allow direct serial number indexing of elements. However, the insertion of data should be designed into memory operations such as array element movement, so the rapid insertion of index data is slow. Vector is worse than ArrayList because it uses the synchronized method (thread safety). LinkedList uses a bidirectional linked list to realize storage, and indexing data by serial number needs to traverse forward or backward, but when inserting data, only two items before and after the item need to be recorded, and it is faster to insert it several times!

Linear table, linked list and hash table are commonly used data structures. When developing Java, JDK provides us with a series of corresponding classes to realize the basic data structure. These classes are all in the java.util package. This paper attempts to explain to readers the functions of various classes and how to use them correctly through simple descriptions.

collection

├List

│├LinkedList

│├ArrayList

│└Vector

│ └Stack

└Set

map

├Hashtable

├HashMap

└WeakHashMap

Collection interface

Collection is the most basic collection interface, and a collection represents a group of objects, that is, the elements of the collection. Some collections allow the same elements, while others do not. Some can sort, some can't. Java SDK does not provide classes that directly inherit from Collection, but all classes provided by Java SDK are "subinterfaces" that inherit from Collection, such as List and Set.

All classes that implement the collection interface must provide two standard constructors: the constructor without parameters is used to create an empty collection, and the constructor with collection parameters is used to create a new collection with the same elements as the incoming collection. The latter constructor allows users to copy a collection.

How to traverse each element in the collection? Regardless of the actual type of the collection, it supports the iterator () method, which returns an iterator with which each element in the collection can be accessed one by one. Typical usage is as follows:

Iterator it = collection.iterator (); //Get the iterator

while(it.hasNext()) {

object obj = it . next()； //Get the next element

}

The two interfaces derived from the collection interface are List and Set.

List interface

A list is an ordered collection. With this interface, you can precisely control the insertion position of each element. Users can access elements in a list by using an index (the position of an element in a list, similar to an array subscript), similar to a Java array.

Unlike the collections mentioned below, this list allows the same elements.

In addition to the Iterator () method required for the collection interface, List also provides a listIterator () method, which returns a ListIterator interface. Compared with the standard iterator interface, ListIterator has more methods such as add (), which allows adding, deleting and setting elements, and can traverse forward or backward.

Commonly used classes that implement List interface include LinkedList, ArrayList, Vector and Stack.

LinkedList class

LinkedList implements the List interface and allows empty elements. In addition, LinkedList provides additional get, remove and insert methods at the head or tail of LinkedList. These operations enable LinkedList to be used as a stack, queue, or bidirectional queue.

Note that LinkedList has no synchronization method. If multiple threads access a list at the same time, they must synchronize their access. One solution is to construct a synchronization list when creating the list:

list list = collections . synchronized list(new linked list(...));

Array list class

ArrayList implements arrays of variable sizes. It allows all elements, including null. Array list is out of sync.

The running time of the size, isEmpty, get and set methods is constant. But the cost of the add method is constant, and it takes O(n) time to add n elements. Other methods run linearly.

Each ArrayList instance has a capacity, which is the size of the array used to store elements. With the continuous addition of new elements, this capacity can be automatically increased, but the growth algorithm is not defined. When a large number of elements need to be inserted, you can call the ensureCapacity method to increase the capacity of ArrayList before insertion to improve the insertion efficiency.

Like LinkedList, ArrayList is asynchronous.

Vector class

Vector is very similar to ArrayList, but Vector is synchronous. Although the iterator created by Vector and the iterator created by ArrayList are the same interface, because the Vector is synchronous, when an iterator is created and being used, another thread changes the state of the Vector (such as adding or deleting some elements) and calls the method of the iterator, it will throw a Concurrentmodification exception, so this exception must be caught.

Stack class

Stack inherits from Vector and implements LIFO stack. Stack provides five additional methods to enable Vector to be used as a stack. Basic push and pop methods, peek method to get the top element of the stack, empty method to test whether the stack is empty, and search method to detect the position of an element in the stack. When it was first created, the stack was an empty stack.

Set interface

Set is a Set that does not contain repeated elements, that is, any two elements e 1 and e2 have e 1.equals(e2)=false, and set has at most one null element.

Obviously, the constructor of Set has a constraint, that is, the passed-in collection parameters cannot contain duplicate elements.

Note that mutable objects must be handled with care. If the variable element in the set changes its state, resulting in Object.equals(Object)=true, it will cause some problems.

map

Note that the mapping does not inherit the collection interface, and it provides a mapping from key to value. A map cannot contain the same key, and each key can only map one value. The Map interface provides views of three sets, and the contents of the Map can be regarded as a set of keys, a set of values or a set of key-value mappings.

Hashtable class

Hashtable inherits the Map interface and implements a hash table of key-value mapping. Any non-empty object can be used as a key or value.

Put(key, value) is used to add data, and get(key) is used to retrieve data. The time cost of these two basic operations is constant.

Hashtable adjusts performance through two parameters: initial capacity and load factor. Usually, the default loading factor of 0.75 strikes a good balance between time and space. Increasing the load factor can save space, but the corresponding search time will increase, which will affect operations such as get and put.

A simple example of using Hashtable is as follows: put 1, 2, 3 into Hashtable, and their keys are "one", "two" and "three" respectively;

Hash table number = new hash table ();

Numbers.put("one ",new integer (1));

Numbers.put("two ",new integer (2));

Numbers.put ("three", new integer (3));

To retrieve a number, such as 2, use the corresponding key:

Integer n = (integer) numbers. get ("two");

system . out . println(" two = "+n)；

Because the object as a key will determine the position of its corresponding value by calculating its hash function, any object as a key must implement the hashCode and equals methods. HashCode and equals methods inherit from the root class object. You should be very careful if you use user-defined classes as keys. According to the definition of hash function, if two objects are the same, that is, obj 1.equals(obj2)=true, their hashcodes must be the same, but if two objects are different, their hashcodes are not necessarily different. If two different objects have the same hashCode, this phenomenon is called conflict, which will increase the time cost of operating hash tables. Therefore, you can speed up the operation of the hash table by defining the hashCode () method as well as possible.

If the same object has different hashCode, the operation on the hash table will produce unexpected results (the expected get method returns null). To avoid this problem, just remember one thing: copy the equals method and the hashCode method at the same time, and don't just write one of them.

Hash tables are synchronized.

HashMap class

HashMap is similar to Hashtable, but the difference is that HashMap is asynchronous and allows null values, that is, null values and null keys. However, when the HashMap is regarded as a set (the values () method can return a set), the time cost of iterating sub-operations is directly proportional to the capacity of the HashMap. Therefore, if the performance of iterative operation is very important, don't set the initialization capacity of HashMap too high or set the loading factor too low.

WeakHashMap class

WeakHashMap is an improved HashMap, which implements a "weak reference" to a key. If a key is no longer externally referenced, it can be recycled by GC.

abstract

If stack, queue and other operations are involved, List should be considered. LinkedList is used for elements that need to be inserted or deleted quickly, and ArrayList is used for elements that need to be accessed quickly and randomly.

If the program is in a single-threaded environment, or access is only in one thread, then it is more efficient to consider asynchronous classes. If multiple threads can operate a class at the same time, then synchronous classes should be used.

Pay special attention to the operation of hash table, and the objects as keys should copy the equals and hashCode methods correctly.

Try to return the interface instead of the actual type, such as returning List instead of ArrayList, so that if you need to change ArrayList to LinkedList in the future, the client code does not need to be changed. This is for abstract programming.

synchronism

Vector synchronization. Some methods in this class ensure that objects in Vector are thread-safe. ArrayList is asynchronous, so the objects in ArrayList are not thread-safe. Because the requirement of synchronization will affect the efficiency of execution, it is a good choice to use ArrayList if thread-safe collection is not needed, so as to avoid unnecessary performance overhead caused by synchronization.

Data growth

From the internal implementation mechanism, ArrayList and Vector both use Array to control the objects in the collection. When adding elements to these two types, if the number of elements exceeds the current length of the internal array, the length of the internal array needs to be extended. By default, Vector automatically doubles the length of the original array, and ArrayList is 50% of the original array, so the space finally obtained is always larger than actually needed. So if you want to save a lot of data in a collection, using Vector has some advantages, because you can avoid unnecessary resource overhead by setting the initialization size of the collection.

Usage pattern

In ArrayList and Vector, it takes the same time to find data from a specified location (by indexing) or to add or remove elements at the end of a collection. This time is represented by O( 1). However, if elements are added or removed from other locations in the collection, the time taken will increase linearly: O(n-i), where n represents the number of elements in the collection and i represents the index location of the added or removed elements. Why is this happening? It is considered that when the above operations are performed, all elements after the i-th and i-th elements in the set will be shifted. What does all this mean?

This means that you can use Vector or ArrayList if you only look for elements in a specific location, or if you add or remove elements at the end of a collection. If it is another operation, it is better to choose another collection operation class. For example, does the LinkList collection class take the same time to add or remove elements anywhere in the collection? O( 1), but its usage when indexing elements is slow-O (i), where i is the location of the index. Using ArrayList is also easy, because you can simply use indexes instead of creating iterator objects. LinkList also creates objects for each inserted element, so you have to understand that it will also bring extra overhead.

Finally, in real Java, Peter Haggar suggested using simple arrays instead of Vector or ArrayList. This is especially true for programs that require high execution efficiency. Because the use of arrays avoids synchronization, extra method calls and unnecessary space reallocation.