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 └Set Map ├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 a Collection parameter constructor is used to create a new Collection, which has the same elements as the incoming Collection. 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 iterator() method, 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 adding, deleting, setting elements, and traversing 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. Although the Iterator created by Vector is the same interface as the 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 elements), a 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, it causes 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 implements the Map interface to implement 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. The 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, 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 the hash table. Therefore, try to define the hashCode() method 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 should rewrite the equals method and hashCode method at the same time, rather than just writing 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.
Java.util.Collections class package
The java.util.Collections class contains many useful methods that can make the work of programmers easier, but these methods are usually not fully utilized. Javadoc gives the most complete description of the Collections class: "This class contains a dedicated static class that can operate or return a collection.
” 1.2 Methods included
Iterator, ArrayList, Elements, Buffer, Map, Collections
Liezi:
import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import 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]); } double arr[] = {111}; for(int j=0;j<arr.length;j++){ li.add(new Double(arr[j])); } }2. Specific operations
1) Sort (Sort)
Use the sort method to sort the specified list in ascending order according to the natural order of the elements. All elements in the list must implement the Comparable interface. All elements in this list must be compared with each other using the specified comparator
double array[] = {112, 111, 23, 456, 231 }; for (int i = 0; i < array.length; i++) { list.add(new Double(array[i])); } Collections.sort(list); for (int i = 0; i < array.length; i++) { System.out.println(li.get(i)); } //Result: 112,111,23,456,2312) Shuffling
The hybrid arrangement algorithm does exactly the opposite of sort: it disrupts any permutations that may be found in a List. That is, the List is rearranged based on the input of the random source, such an arrangement has the same possibility (assuming that the random source is fair). This algorithm is very useful in implementing a game of luck. For example, it can be used to mix a List of Card objects representing a deck of cards. In addition, it is also very useful when generating test cases.
Collections.Shuffling(list) double array[] = {112, 111, 23, 456, 231 }; for (int i = 0; i < array.length; i++) { list.add(new Double(array[i])); } Collections.shuffle(list); for (int i = 0; i < array.length; i++) { System.out.println(li.get(i)); } //Result: 112,111,23,456,2313) Reverse
Use the Reverse method to sort the specified list in descending order according to the natural order of elements.
Collections.reverse(list) double array[] = {112, 111, 23, 456, 231 }; for (int i = 0; i < array.length; i++) { list.add(new Double(array[i])); } Collections. reverse (list); for (int i = 0; i < array.length; i++) { System.out.println(li.get(i)); } //Result: 231,456,23,111,112 4) Replace all elements in the specified list with the specified element. String str[] = {"dd","aa","bb","cc","ee"}; for(int j=0;j<str.length;j++){ li.add(new String(str[j])); } Collections.fill(li,"aaa"); for (int i = 0; i < li.size(); i++) { System.out.println("list[" + i + "]=" + li.get(i)); } //Result: aaa,aaa,aaa,aaa5) Copy (Copy)
Use two parameters, a target List and a source List, to copy the source element to the target and overwrite its contents. The target List is at least as long as the source. If it is longer, the remaining elements in the target List are not affected.
Collections.copy(list,li): The latter parameter is the target list, the previous one is the source list
double array[] = {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])); } double arr[] = {1131,333}; String str[] = {"dd","aa","bb","cc","ee"}; for(int j=0;j<arr.length;j++){ li.add(new Double(arr[j])); } Collections.copy(list,li); for (int i = 0; i <list.size(); i++) { System.out.println("list[" + i + "]=" + list.get(i)); } //Result: 1131,333,23,456,2316) Returns the smallest element in Collections (min)
Returns the smallest element of the given collection according to the order in which the specified comparator is generated. All elements in the collection must be compared with each other through the specified comparator
Collections.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])); } Collections.min(list); for (int i = 0; i <list.size(); i++) { System.out.println("list[" + i + "]=" + list.get(i)); } //Result: 237) Returns the smallest element (max) in Collections
Returns the maximum element of the given collection according to the order in which the specified comparator is generated. All elements in the collection must be compared with each other through the specified comparator
Collections.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])); } Collections.max(list); for (int i = 0; i <list.size(); i++) { System.out.println("list[" + i + "]=" + list.get(i)); } //Result: 4568) lastIndexOfSubList
Returns the starting position of the specified target list that last appeared in the specified source list
int count = Collections.lastIndexOfSubList(list,li); double array[] = {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])); } double arr[] = {111}; String str[] = {"dd","aa","bb","cc","ee"}; for(int j=0;j<arr.length;j++){ li.add(new Double(arr[j])); } Int locations = Collections. lastIndexOfSubList (list,li); System.out.println("==="+ locations); //Result 39) IndexOfSubList
Returns the starting position of the first time the specified target list appears in the specified source list
int count = Collections.indexOfSubList(list,li); double array[] = {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])); } double arr[] = {111}; String str[] = {"dd","aa","bb","cc","ee"}; for(int j=0;j<arr.length;j++){ li.add(new Double(arr[j])); } Int locations = Collections.indexOfSubList(list,li); System.out.println("==="+ locations); //Result 110) Rotate
Cyclically move elements in the specified list based on the specified distance
Collections.rotate(list,-1);
If it is a negative number, it moves positively, and if it moves positively, it moves positively.
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])); } Collections.rotate(list,-1); for (int i = 0; i <list.size(); i++) { System.out.println("list[" + i + "]=" + list.get(i)); } //Result: 111,23,456,231,112The above article briefly discusses the implementation classes Collection and Map of commonly used data structures in Java. This is all the content I have shared with you. I hope you can give you a reference and I hope you can support Wulin.com more.