Collections in Java
Collection: a storage structure that can dynamically store multiple data. It is a public API provided by Java and exists in Java Util package
The architecture of the entire Java collection is as follows:
There are two main branches:
-
Collection can only store one value at a time. The specific storage nature is related to different sub interfaces
The elements stored in Set are unordered and not repeated. Common implementation classes are:
-
HashSet is an unordered and non repeating set
-
LinkedHashSet order non repeating set order is realized through linked list
The elements stored in List are orderly and repeatable. Common implementation classes are:
- The bottom layer of ArrayList is implemented in array mode, which has high reading efficiency but low modification efficiency. ArrayList is often used
- LinkedList bottom layer is realized by two-way linked list. The modification efficiency is high, but the reading efficiency is low
-
Map needs to store one key value pair at a time
Common implementation class HashMap
Collection
Collection Is a top-level class common method for all individual storage elements: •int size(); Return to this collection The number of elements in the. •boolean isEmpty(); Judge this collection Whether the contains elements. •boolean contains(Object obj); Judge this collection Whether to include the specified element. •boolean contains(Collection c); Judge this collection Whether to include the specified collection All elements in. •boolean add(E element); To this collection Add to the elements. •boolean addAll(Collection c);Will specify collection Add all elements in to this collection in •boolean remove(Object element); from then on collection Removes the specified element from the. •boolean removeAll(Collection c); Remove this collection Those are also included in the specified collection All elements in. •void clear(); Remove some collection All elements in. •boolean retainAll(Collection c); Keep this only collection Those are also included in the specified collection Element of. •Iterator iterator(); Return here collection Iterator that iterates over the element of. •T[] toArray(T[] arr); Take this collection Convert to array.
Iterator
Iterator is the parent interface of a Collection, which provides an internal traversal method for collections of Collection type
Common methods:
- hasNext() checks whether there is an element at the next position of the current pointer. If so, it returns true; otherwise, it returns false
- next() moves the pointer to the next element and gets the element back to the caller
- remove() removes the pointer currently traversed
Since JDK5, all variables implemented by Iterator can be traversed by forEach
Set interface
Set interface is a sub interface type of Collection, which is characterized by disorder and non repetition
Corresponding to Set in Mathematics
How to determine whether elements in a Set are repeated:
- Determine whether the values returned by the hashCode() method of the object are equal. If they are equal, it means that the current two objects are equal. Skip the storage steps of the object directly. If they are not equal, they are directly stored in the meta table
- When the values returned by hashCode() are equal, the equals() method of the object is used to determine whether the current two objects are equal. If they are equal, the storage will be skipped. If they are unequal, the stored module will be converted into a linked list for storage. After JDK8, if the length of the linked list reaches 8, the linked list will be converted into a red black tree structure for storage, but this method will rarely trigger
According to the hash code value of the object, its storage index is calculated, and it can be found by a small amount of comparison between the elements in the corresponding position (table element) of the hash table.
The Set system has high efficiency in saving, fetching and deleting objects.
For objects to be stored in the Set collection, the corresponding classes must override the equals() and hashCode(Object obj) methods to implement the object equality rule
Common sub interfaces:
- HashSet does not save the storage order of elements
The bottom layer uses the form of hash table to store data, so the reading efficiency is high, and the corresponding data is read directly according to the hash value
- The underlying layer of the LinkedHashSet is a linked list to ensure the storage order, but it still cannot be repeated
It needs to be orderly and not repeated, but the efficiency is slightly low
List interface
The elements in the collection class that implements the List interface are ordered and allowed to be repeated.
The elements in the List set correspond to an integer serial number, recording their position in the set. The elements in the set can be accessed according to the serial number.
The List collection classes provided by JDK API are commonly used:
- ArrayList
- LinkedList
Common methods:
public Object get(int index) Returns the number of elements in the list public Object add(int index, Object element); Inserts the specified element at the specified position in the list.The current location Element (if any) and all subsequent elements move to the right public Object set(int index, Object element) ; Replaces the element at the specified position in the list with the specified element public Object remove(int index) Removes the element at the specified position in the list public ListIterator listIterator() Returns the list iterator for this list element remove(Object obj) If obj Remove if present remove(int index) Removes the element at the specified location and returns the element to the caller
ArrayList
List collection implemented using array structure
advantage:
- It has good efficiency for extracting elements using index
- It uses indexes to quickly locate objects
Disadvantages:
- Element deletion or insertion is slow
- Because the array is used, the following elements need to be moved to adjust the index order
LinkedList
LinkedList is a collection implemented using a two-way linked list.
LinkedList adds some insertion and deletion methods.
advantage:
- It has high efficiency for frequent insertion or deletion of elements
- It is suitable for implementing stack and queue
Disadvantages:
- Reading data can only traverse one direction in turn, and the search efficiency is low
Map
In a Collection, Map and Collection are a parallel relationship, and their internal functions store key value pairs. And the value of key cannot be repeated and is out of order, and value is not required.
The common implementation classes of Map interface in JDK API are:
-
HashMap uses hash table internally to hash the "key value" mapping pair.
1. The most frequently used set.
-
LinkedHashMap is a subclass of HashMap
1. Use hash table to store mapping pairs
2. Record the insertion order of mapping pairs with a linked list.
The "key value" mapping pair stored in the Map implementation class is uniquely identified by the key, and the "key" at the bottom of the Map is stored by Set. Therefore, the class corresponding to the "key" of the mapping pair stored in the Map must override the hashcode() and equals() methods. String is often used as the "key" of Map.
Common methods of Map interface:
•Object put(Object key, Object value); //Save the specified key value pair into the Map •Object get(Object key); //Returns the value mapped by the specified key •Object remove(Object key); //Removes this key value pair from the Map according to the specified key. •boolean containsKey(Object key); //Determines whether this Map contains a key value pair for the specified key. •boolean containsValue(Object value); //Determines whether the key value pair containing the specified value is included. •boolean isEmpty(); //Determine whether there are elements in this Map. Method name and method introduction public E push(E item) Push the element to the top of the stack public E pop() Removes the object at the top of the stack and returns it as the value of this method public E peek() View the object at the top of the stack, but do not remove it from the stack. public boolean empty() Test whether the stack is empty. public int search(Object o) Returns the position of the object in the stack, based on 1. •int size(); //Get the number of key value pairs in some maps. •void clear(); //Clear all key value pairs in the Map. •Set keySet(); //Returns the Set of keys contained in this Map. •Collection values(); //Returns the Collection set of values contained in this Map. •Set<Map.Entry<K,V>> entrySet(); //Returns the Set of key value pairs contained in this Map
Legacy class
Vector
In the old version of ArrayList, most of its operations are the same as ArrayList, except that Vector is thread synchronized.
It has an enumeration method, which can be accessed through traversal similar to Iterator, or use forEach or enumeration (jdk1.0 is used to traverse the collection, which is not recommended later, and Iterator can be used instead)
Stack
• Stack class is a subclass of Vector. It is a Stack that stores elements in a later in first out (LIFO) manner. Thread synchronization.
Five methods are added to the Stack class to extend the Vector class
| Method name | Method introduction |
|---|---|
| public E push(E item) | Push the element to the top of the stack |
| public E pop() | Removes the object at the top of the stack and returns it as the value of this method |
| public E peek() | View the object at the top of the stack, but do not remove it from the stack. |
| public boolean empty() | Test whether the stack is empty. |
| public int search(Object o) | Returns the position of the object in the stack, based on 1. |
Hashtable
Old version of HashMap, jdk1 0, in jdk2 0 uses HashMap to replace Hashtable, which has the function of thread synchronization.
The usage is roughly the same as HashMap.
Properties
A subclass of Hashtable, which is used to obtain the information in the configuration file in the current project. This class has no generic type, and all key values are of String type
The properties class represents a persistent set of properties. Properties can be saved in or loaded from a stream. Each key and its corresponding value in the property set is a string.
It is not recommended to use put and putAll methods to store elements, but setProperty(String key, String value) methods should be used, because the stored "key value" pairs are strings. Similar values should also use getProperty(String key).
import java.io.IOException;
import java.io.InputStream;
import java.util.Properties;
public class PropertiesTest {
public static void main(String[] args) {
InputStream is = Thread.currentThread()
.getContextClassLoader()
.getResourceAsStream("config.properties");
Properties prop = new Properties();
try {
prop.load(is);
} catch (IOException e) { e.printStackTrace(); }
String name = prop.getProperty("name");
String pwd = prop.getProperty("pwd");
System.out.println(name + ", " + pwd);
}
}
Sorting interface
TreeSet & TreeMap
There is an automatically sorted storage set in the set, and the bottom layer uses red black tree for data storage.
As long as the data stored in the set is arranged by default according to the sorting rules
For data type wrapper classes and String types, sorting interfaces are implemented by default, and data will be arranged in dictionary order
If you want the element to be placed in TreeSet or TreeMap, the object must implement the comparison interface Comparable, otherwise an exception will be thrown during storage
Comparable
Comparison interface. All objects that need to implement sorting rules should implement this interface, indicating that this class is a comparable class.
When implementing Comparable, you need to implement its CompareTo(Object o) method
Determine in ascending order according to the rules:
a. Age > b.age needs to return a positive integer
a. Age < b.age needs to return a negative integer
a.age == b.age needs to return 0
In descending order, you only need to exchange the positions of positive and negative integers
Advantages: unordered. In addition, you can set sorting rules to sort directly in the sortable method
Disadvantages: if Comparable is implemented in a project, the object can only have one sort method by default
public class Student implements Comparable{
private int id; //number
private String name; //full name
private double score; //Test score
public Student(){}
public Student(int id, String name, double score) {
this.id = id; this.name = name; this.score = score;
}
//Omit getter and setter methods for all properties
//Implement the compareTo method and sort it in ascending order by score
public int compareTo(Object o) {
Student other = (Student)o;
if(this.score > other.score){ return 1;
}else if(this.score < other.score){ return -1;
}else{ return 0; }
}
public boolean equals(Object obj) {...}
public int hashCode() { ...}
}
Comparator
Comparator interface. You can customize a class to implement the comparator interface and implement its compare(Object o1,Object o2) method
The comparison rules are consistent with those in Comparable.
Advantages: in a project, different comparators can be defined according to different requirements, and accurate comparison rules can be used to sort data according to specific requirements
Disadvantages: when using, you need to manually inform the sorting interface of the sorting rules (set parameters). If you use it only once, you can see how to use anonymous inner classes or Lambda expressions to implement it
When an object implements the Comparable interface and uses the sort class of Comparator type, if the sort class calling Comparator is displayed, the implementation rules of Comparable will be overwritten. Otherwise, the default sort of Comparable will be used directly
/** Student test score comparator */
class StudentScoreComparator implements Comparator<Student>{
public int compare(Student o1, Student o2) {
if(o1.getScore() > o2.getScore()){ return 1;
}else if(o1.getScore() < o2.getScore()){ return -1;
}else{ return 0; }
}
}
/** Student name comparator */
class StudentNameComparator implements Comparator<Student>{
public int compare(Student o1, Student o2) {
return o1.getName().compareTo(o2.getName());
}
}
//Sort set using different comparators
Set<Student> set = new TreeSet<Student>(new StudentScoreComparator());
Set<Student> set2 = new TreeSet<Student>(new StudentNameComparator());
Collections
The tool class specially designed for the collection provides common functions of the collection, which is convenient for developers to improve development efficiency.
Common methods:
void sort(List list) Assign to elements according to their natural order List The list is sorted in ascending order. List All elements in the list must be Must be realized Comparable Interface. void shuffle(List list) yes List The elements in the list are arranged randomly void reverse(List list) yes List Invert the elements in the list void copy(List dest, List src) take src Copy elements in the list to dest In the list List synchronizedList(List list) Returns the synchronization supported by the specified list(Thread safe)list
Thread safety of collection classes
Most collection classes do not consider thread safety by default. The program must synchronize itself to ensure that the shared data can be accessed without error under multithreading:
Use sync lock
- synchronized(list){ list.add(...); }
Use Java uitl. The synchronizedXxx() method of collections returns a synchronized container object
•List list = Collections.synchronizedList(new ArrayList());
This method should still be decorated with synchronized during iteration
List list = Collections.synchronizedList(new ArrayList());
...
synchronized(list) {
Iterator i = list.iterator(); • while (i.hasNext()) {
foo(i.next());
}
}
From jdk5 Starting from 0, a concurrent package is provided, which specifically provides some objects that are easy to use in concurrent operations. Common objects related to collections are:
- ConcurrentHashMap
- CopyOnWriteArrayList
- CopyOnWriteArraySet
The above objects are balanced in synchronization and efficiency. They only lock when modifying elements and do not lock when reading elements, so as to improve reading efficiency. They are suitable for data with strong concurrency and not long modification.