I often encountered such questions during interviews in the past. Ask you to write about the differences and connections between ArrayList.LinkedList.Vector: I didn’t understand it at first, but I don’t know what the difference between these three? Alas, I am ashamed, the foundation is too poor, there is no way, I feel wronged
Now we have to talk about the differences and connections between these three: these three implement the List interface, all have methods defined in the List interface, and also have methods of the Collection interface;
ArrayList: uses array method to store data, query and modification speed is fast, but the addition and deletion speed is slow; threads are out of sync
LinkedList: uses the method of linked list to store data, the query and modification speed is slow, but the addition and deletion speed is fast.
Vector: It also uses arrays for storage. Vector was used before java 1.0, but ArrayList was used after java 1.2, threads are synchronized, and the efficiency is slower than ArrayList; at the same time, Vector query There are four ways of data: iterators, enumerations, get(int index), and indexOf(int index), but ArrayList does not have enumerations
ArrayList and Vector use arrays to store data. The number of elements in this array is larger than the actual stored data to add and insert elements. Both allow direct sequence number indexing elements, but inserting data must be designed to move array elements and other memory operations, so index data is quickly inserted. The data is slow. Vector uses synchronized method (thread safe), so its performance is worse than ArrayList. LinkedList uses a two-way linked list to store. Indexing data according to serial numbers requires forward or backward traversal, but only this item is required when inserting data. The front and back terms are enough, so inserting several degrees faster!
Linear tables, linked lists, and hash tables are commonly used data structures. When developing Java, JDK has provided us with a series of corresponding classes to implement basic data structures. These classes are all in the java.util package. This article attempts to explain to the readers the role of each class and how to use them correctly through a simple description.
Collection ├List │ ├LinkedList │ ├ArrayList │ └Vector │ └Stack └SetMap ├Hashtable ├HashMap └WeakHashMap
Collection interface
Collection is the most basic collection interface. A Collection represents a set of Objects, that is, the elements of the Collection (Elements). Some Collections allow the same elements while others don't. Some can sort but others cannot. The Java SDK does not provide classes that are directly inherited from Collection. The classes provided by the Java SDK are all "subinterfaces" that are inherited from Collection such as List and Set.
All classes that implement the Collection interface must provide two standard constructors: the parameterless constructor is used to create an empty Collection, and there is a Collection parameter constructor is used to create a new Collection, this new Collection and pass. The entered collection has the same element. The latter constructor allows the user to copy a Collection.
How to iterate through every element in a Collection? Regardless of the actual type of the Collection, it supports an iterator() method, which returns an iterator, and uses this iterator to access each element in the Collection one by one. Typical usages are as follows:
Iterator it = collection.iterator(); // Get an 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
List is an ordered collection, and using this interface allows you to accurately control the position of each element insertion. Users can use indexes (the position of elements in List, similar to array subscripts) to access elements in List, which is similar to Java's arrays.
Unlike the Set mentioned below, List allows the same elements.
In addition to the iterator() method that has the necessary 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(), allowing addition, Delete, set elements, and can also traverse forward or backward.
Common classes that implement List interfaces include LinkedList, ArrayList, Vector and Stack.
LinkedList class
LinkedList implements the List interface, allowing null elements. In addition, LinkedList provides additional get, remove, insert methods at the header or tail of the LinkedList. These operations enable LinkedList to be used as a stack, queue, or a two-way queue.
Note that LinkedList does not have a synchronous method. If multiple threads access a List at the same time, you must implement access synchronization by yourself. One solution is to construct a synchronous List when creating it:
List list = Collections.synchronizedList(new LinkedList(...));
ArrayList class
ArrayList implements variable-sized arrays. It allows all elements, including null. ArrayList is not synchronized.
The run time of the size, isEmpty, get, set methods is constant. However, the overhead of the add method is an amortized constant, and it takes O(n) time to add n elements. The other methods have linear run time.
Each ArrayList instance has a Capacity, which is the size of the array used to store elements. This capacity can automatically increase as new elements are constantly added, but the growth algorithm is not defined. When a large number of elements need to be inserted, the ensureCapacity method can be called before inserting to increase the capacity of the ArrayList to improve insertion efficiency.
Like LinkedList, ArrayList is also unsynchronized.
Vector class
Vector is very similar to ArrayList, but Vector is synchronous. Iterator created by Vector, although iterator created by ArrayList, is the same interface as iterator created by ArrayList, because the Vector is synchronized, when one Iterator is created and is being used, another thread changes the status of the Vector (for example, adding or removing some ) At this time, the ConcurrentModificationException will be thrown when the Iterator method is called, so the exception must be caught.
Stack class
Stack inherits from Vector, implementing a last-in first-out stack. Stack provides 5 additional methods to enable Vector to be used as a stack. The basic push and pop methods, and the peek method get the elements at the top of the stack, the empty method tests whether the stack is empty, and the search method detects the position of an element in the stack. Stack is just created and is an empty stack.
Set interface
Set is a collection that does not contain duplicate elements, that is, any two elements e1 and e2 have e1.equals(e2)=false, and Set has at most one null element.
Obviously, Set's constructor has a constraint, and the passed Collection parameter cannot contain duplicate elements.
Please note: Mutable Objects must be operated with care. If a mutable element in a Set changes its own state, causing Object.equals(Object)=true to cause some problems.
Map interface
Please note that Map does not inherit the Collection interface, and Map 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 three types of views of the collection. The content of the map can be regarded as a set of key collections, a set of value collections, or a set of key-value mappings.
Hashtable class
Hashtable inherits the Map interface and implements a hash table with a key-value mapping. Any non-null object can be used as a key or value.
Use put(key, value) to add data, use get(key) to retrieve data. The time overhead of these two basic operations is constant.
Hashtable adjusts performance through the initial capacity and load factor parameters. Usually, the default load factor 0.75 can better achieve time and space balance. Increasing the load factor can save space but the corresponding search time will increase, which will affect operations like get and put.
A simple example of using a Hashtable is as follows: put 1, 2, and 3 into a Hashtable, and their keys are "one", "two", "three" respectively:
Hashtable numbers = new Hashtable();
numbers.put("one", new Integer(1));
numbers.put("two", new Integer(2));
numbers.put("three", new Integer(3));
To take out a number, such as 2, use the corresponding key:
Integer n = (Integer)numbers.get("two");
System.out.println("two = " + n);
Since an object as a key will determine the position of the 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. If you use a custom class as a key, be very careful. According to the definition of the hash function, if the two objects are the same, that is, obj1.equals(obj2)=true, then Their hashCode must be the same, but if the two objects are different, their hashCodes may not be different. If the hashCodes of two different objects are the same, this phenomenon is called conflict. Conflict will increase the time overhead of operating hash tables. Therefore, try to define the hashCode() method well to speed up the operation of the hash table.
If the same object has different hashCodes, the operation on the hash table will have unexpected results (the expected get method returns null). To avoid this problem, you only need to remember one thing: you must rewrite the equals method and hashCode method at the same time. Don't just write one of them.
Hashtable is synchronized.
HashMap class
HashMap is similar to Hashtable, the difference is that HashMap is asynchronous and allows null, i.e. null value and null key. , but when HashMap is considered a Collection (the values() method can return a Collection), its iterative suboperation time overhead is proportional to the capacity of HashMap. Therefore, if the performance of iteration operations is very important, do not set the initialization capacity of HashMap to be too high or the load factor is too low.
WeakHashMap class
WeakHashMap is an improved HashMap that implements "weak reference" to the key. If a key is no longer referenced externally, the key can be recycled by GC.
Summarize
If stack, queue and other operations are involved, you should consider using List. For elements that need to be quickly inserted and deleted, you should use LinkedList. If elements need to be accessed quickly, you should use ArrayList.
If the program is in a single-threaded environment, or access is only in one thread, considering asynchronous classes, it is more efficient. If multiple threads may operate a class at the same time, synchronous classes should be used.
Pay special attention to the operation of hash tables. As the object as the key, the equals and hashCode methods should be copied correctly.
Try to return the interface instead of the actual type, such as returning a List instead of an ArrayList. In this way, if you need to change the ArrayList to a LinkedList in the future, the client code does not need to be changed. This is for abstract programming.
Synchronization
Vector is synchronous. Some methods in this class ensure that the objects in Vector are thread-safe. ArrayList is asynchronous, so the objects in ArrayList are not thread-safe. Because synchronization requirements will affect execution efficiency, using ArrayList is a good choice if you don't need thread-safe collections, which can avoid unnecessary performance overhead due to synchronization.
Data growth
From the internal implementation mechanism, ArrayList and Vector both use arrays (Array) to control objects in the collection. When you add elements to these two types, if the number of elements exceeds the current length of the internal array, they need to expand the length of the internal array. By default, Vector automatically increases the original array length by twice. ArrayList is the original 50% of that, so the last time you get this collection will always take up more space than you actually need. So if you want to save a lot of data in a collection then there are some advantages to using Vector, because you can avoid unnecessary resource overhead by setting the initialization size of the collection.
Usage mode
In ArrayList and Vector, it takes the same time to find data from a specified location (via the index) or to add and remove an element at the end of the set. This time is represented by O(1). However, if elements are added or removed elsewhere in the set, the time spent will grow linearly: O(ni), where n represents the number of elements in the set, and i represents the index position where elements increase or remove elements. Why is this happening? It is thought that when performing the above operations, all elements after the i-th and i-th elements in the set must perform displacement operations. What does all this mean?
This means that you just look for elements in a specific position or just add and remove elements at the end of the collection, then using Vector or ArrayList is OK. If it is another operation, you'd better choose another collection operation class. For example, the time it takes for the LinkList collection class to add or remove elements at any position in the collection is the same? O(1), but it uses a slower use in indexing an element - O(i), where i is The location of the index. Using ArrayList is also easy, because you can simply use the index instead of creating the iterator object. LinkList will also create objects for each inserted element, and all you need to understand will also bring additional overhead.
Finally, in the book Practical Java, Peter Haggar suggests using a simple array (Array) instead of Vector or ArrayList. This is especially true for programs with high execution efficiency. Because using arrays (Array) avoids synchronization, additional method calls and unnecessary reallocation of space operations.