An overview of the
Collection is a basic module in Java, all the collection classes are in the java.util package, which supports multi-threading collection classes are located in the java.util. Concurrent package, interested friends can go to see the relevant source code.
This paper attempts to take a global view of the Java collection framework. The Java collection can be roughly divided into three parts: List, Set, and Map. This article will introduce the functions and differences of the three in turn.
Let’s not Go!!
The Iterator Iterator
Before getting into the specifics of containers, let’s take a look at what an iterator is. Iterators provide a way to iterate over elements in a container, i.e., we can iterate over collection elements through iterators. The Iterator interface defines the functions that iterators should have. The source code is as follows:
public interface Iterator<E> {
/** * determines if the set has another element *@return boolean
*/
boolean hasNext(a);
/** * gets the next element *@return E
*/
E next(a);
/** * The default method provided by Java8 * does not allow elements to be removed during iteration, and will throw operations that do not support exceptions *@throws UnsupportedOperationException
*/
default void remove(a) {
throw new UnsupportedOperationException("remove");
}
/** * The default method provided by Java8 */
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while(hasNext()) action.accept(next()); }}Copy the codeThe hasNext() and next() methods are implemented by concrete containers. Iterators can only be obtained from the container itself. Each container implements its own iterators through inner classes, so iterators are used as follows:
@Test
public void test(a){
List<Integer> list = new ArrayList<>(6);
for (int i = 0; i < 6; i++) {
list.add(i);
}
// Iterators can only be obtained from the container itself (PS: some containers may implement subinterfaces to iterators such as ListIterator, just optimizations)
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()) { System.out.println(iterator.next()); }}Copy the codeCollection
Collection is an interface. It is a highly abstract interface that defines the basic operations of a Collection: add, delete, empty, iterate, empty, get size, and so on. Let’s look at the class diagram for the Collection interface:
AbstractCollection abstract classes are defined for other classes to inherit. AbstractCollection implements most of the methods in Collection. AbstractList and AbstractSet both inherit from AbstractCollection.
Second, we see that the Collection interface depends on the Iterator interface. (Dependencies: Dependencies are when one class A uses another class B, so changes to class B affect class A. For example, someone needs to borrow a boat to cross the river. The relationship between man and boat is dependence. At the code level, class B is used as an argument by class A in A method method.
Collection relies on Iterator. The Collection interface defines the method Iterator
Iterator (), which returns an Iterator to iterate over the Collection. In the List interface, the listIterator() method returns a listIterator object; The ListIterator interface is List specific.
All subclasses of the Collection interface (direct and indirect) must implement two types of constructors: a no-argument constructor and a constructor that takes Collection. A constructor with arguments can be used to convert the type of a Collection. Here is the API defined in the Collection interface (JDK1.8) :
public interface Collection<E> extends 可迭代<E> {
// iterators Each container implements iterators through inner classes
Iterator<E> iterator(a);
// Add elements
boolean add(E e);
// Add elements in batches
boolean addAll(Collection<? extends E> c);
// Remove the element
boolean remove(Object o);
// Delete elements in batches
boolean removeAll(Collection
c);
// Whether to contain element o
boolean contains(Object o);
// Whether to contain a set of elements
boolean containsAll(Collection
c);
// Preserve the element
boolean retainAll(Collection
c);
// Get the set length
int size(a);
// Whether the set is empty
boolean isEmpty(a);
// Convert to an array
<T> T[] toArray(T[] a);
/ / to empty
void clear(a);
/ / the equals method
boolean equals(Object o);
/ / hashCode methods
int hashCode(a);
Java8 default methods are converted to arrays
default <T> T[] toArray(IntFunction<T[]> generator) {
return toArray(generator.apply(0));
}
Java8 provides a default method to remove elements that meet the criteria
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true; }}return removed;
}
// The default method provided by Java8
@Override
default Spliterator<E> spliterator(a) {
return Spliterators.spliterator(this.0);
}
default Stream<E> stream(a) {
return StreamSupport.stream(spliterator(), false);
}
default Stream<E> parallelStream(a) {
return StreamSupport.stream(spliterator(), true); }}Copy the codeList
The List interface is defined as follows:
public interface List<E> extends Collection<E> {
/ /...
}
Copy the codeAs you can see from the List definition, it inherits from the Collection interface, i.e. the List is a type of Collection. A List is an ordered queue that can store duplicate elements. Each element in the List has an index. The index value of the first element is 0, and the index value of subsequent elements is successively + 1.
Let’s look at the class diagram for the List collection:
From the class diagram, we can see that the List interface inherits from the Collection interface, and there is an abstract class AbstractList and subsequent concrete subclasses: ArrayList, LinkedList, etc. Simply looking at the link List —-> AbstractList —-> ArrayList/LinkedList, there is a smell of template method pattern. The top-level interface defines the concrete behavior, and the abstract class provides a reusable algorithm skeleton. Then the specific subclass can customize the related functions according to its own characteristics.
Returning to List, it naturally contains all of its apis because it inherits the Collection interface, but since List is an ordered Collection, it also has its own additional API:
Add (int, E), add(int, E), add(int, E), add(int, E), get(index), etc.
The specific source code is as follows:
public interface List<E> extends Collection<E> {
// Query Operations
int size(a);
boolean isEmpty(a);
boolean contains(Object o);
Iterator<E> iterator(a);
Object[] toArray();
<T> T[] toArray(T[] a);
// Modification Operations
boolean add(E e);
boolean remove(Object o);
// Bulk Modification Operations
boolean containsAll(Collection
c);
boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c);
boolean removeAll(Collection
c);
boolean retainAll(Collection
c);
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while(li.hasNext()) { li.set(operator.apply(li.next())); }}@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for(Object e : a) { i.next(); i.set((E) e); }}void clear(a);
// Comparison and hashing
boolean equals(Object o);
int hashCode(a);
// Positional Access Operations
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
// Search Operations
int indexOf(Object o);
int lastIndexOf(Object o);
// List Iterators
ListIterator<E> listIterator(a);
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);
@Override
default Spliterator<E> spliterator(a) {
return Spliterators.spliterator(this, Spliterator.ORDERED); }}Copy the codeAbstractList
The AbstractList abstract class is defined as follows:
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
//....
}
Copy the codeAbstractList extends AbstractCollection abstractclasses and implements the List interface. It implements a List in addition to a get (int index) most method (PS: many methods on the implementation details of just throws an UnsupportedOperationException exception, a bit not understand its meaning).
From a source point of view, AbstractList mainly provides operations related to iterative traversal (implemented through iterators), which simplifies iterative traversal for subsequent subclasses.
AbstractSequentialList
An AbstractSequentialList abstract class is defined as follows:
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
// ...
}
Copy the codeFrom the definition we can see it inherited from AbstractList abstract class, it is to do what’s actually use? Let’s take a look at its API:
As you can see, most of the API it overrides has the parameter index.
AbstractSequentialList implements random access/operations such as GET (int index), Add (int Index, E element) on data storage structures (e.g., linked lists) that can only be accessed sequentially. AbstractSequentialList abstract classes provide array-like random access to sequentiallist data storage structures that can only be accessed sequentially. The underlying implementation is based on sequential iterator traversal (traversal is necessary after all, but it does this for us).
In general, data structures that support random access (such as ArrayList) inherit AbstractList, while data structures that do not support random access (such as LinkedList) inherit AbstactSequentialList. Note, however, that ArrayList and LinkedList both heavily rewrite AbstractList and AbstactSequentialList implementations.
Vectors and Stacks like orphans from the past
In the class diagram of List, we see two classes labeled legacy: Vector and Stack.
Vector is a thread-safe List. We can use CopyOnWriteArrayList instead. Stack provides the Stack function, and we can use LinkedList instead.
In addition, ArrayList and LinkedList have a special introduction, refer to the article:
-
Java ArrayList ArrayList (JDK1.8)
-
List of LinkedList (JDK1.8)
Set
Set is defined as follows:
public interface Set<E> extends Collection<E> {
// ...
}
Copy the codeFrom the definition, we can see that the Set interface descends from Collection, which is also a kind of Collection. It stands for the mathematical concept of Collection — there can be no repeating elements.
If you look at the source code, you can see that Set does not define its own API like List does; All methods in a Set inherit from the Collection interface.
Let’s look at the family members of Set:
As can be seen from the class diagram, TreeSet, HashSet and LinkedHashSet are the three main classes used by us in the Set family.
-
TreeSet: an ordered store that sorts elements of a Set using a red black tree. TreeSet is actually a subclass of SortedSet. TreeSet implements all SortedSet methods and sorts using the comparator() method.
-
HashSet: The underlying data structure is implemented by the keys of the HashMap. The order of the elements in the collection is not guaranteed, that is, the order of iteration is not guaranteed to be the same as the order of insertion. Is thread unsafe.
-
LinkedHashSet: The underlying layer is implemented by a linked list that iterates in the order in which elements are inserted, that is, the output of the iteration is in the same order as the insertion.
For a full description of all three, please refer to the following article:
-
todo1:
-
todo2:
-
todo3:
Map
A Map is defined as follows:
public interface Map<K.V> {
// ..
}
Copy the codeWe can see that the Map interface does not inherit from Collection; A Map is a container for associating key objects with value objects. For keys, like sets, keys in a Map cannot be duplicated, that is, keys are unique, and a key can Map only one value object, value. There is no unique requirement for the value object value. In theory, multiple keys can be mapped to the same value. Although the program does not report errors, it may cause confusion to the user (which key is mapped from it?).
Note: Since the key object in the Map calculates its hash function to determine where to store its value, any key object must implement the hashCode and equals methods.
Let’s look at the family members of the Map collection:
From the class diagram, we can see that Map series provides 6 subclasses for use, which are HashMap, LinkedHashMap, WeakHashMap, HashTable(former Orphans), IdentityHashMap and TreeMap. In actual development, the most frequently used are: HashMap, LinkedHashMap and TreeMap.
Subsequent articles will also analyze the source code for these three maps.
As a collection, Map provides the following functions: Add, delete, and search…… Let’s take a look at the specific apis the JDK designers have designed for it.
public interface Map<K.V> {
// Returns the length of the collection
int size(a);
// Check whether the set is empty
boolean isEmpty(a);
// Whether to contain the specified key
boolean containsKey(Object key);
// Whether to include the specified value
boolean containsValue(Object value);
// Obtain the corresponding value by key
V get(Object key);
// Modification Operations
// Add keys and values to the collection map
V put(K key, V value);
// Remove the key-value pair based on key and return the corresponding value
V remove(Object key);
// Bulk Operations
// Add keys in batches
void putAll(Map<? extends K, ? extends V> m);
// Clear all key-value pairs in the set map
void clear(a);
// Views
// Get the set of keys
Set<K> keySet(a);
Collection<V> values(a);
Set<Map.Entry<K, V>> entrySet();
// Entry is a stored key-value pair object
interface Entry<K.V> {
K getKey(a);
V getValue(a);
V setValue(V value);
boolean equals(Object o);
int hashCode(a);
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return(Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue()); }}// Comparison and hashing
boolean equals(Object o);
int hashCode(a);
// Defaultable methods
default V getOrDefault(Object key, V defaultValue) {
V v;
return(((v = get(key)) ! =null) || containsKey(key))
? v
: defaultValue;
}
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw newConcurrentModificationException(ise); } action.accept(k, v); }}default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Objects.requireNonNull(function);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
// ise thrown from function is not a cme.
v = function.apply(k, v);
try {
entry.setValue(v);
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw newConcurrentModificationException(ise); }}}default V putIfAbsent(K key, V value) {
V v = get(key);
if (v == null) {
v = put(key, value);
}
return v;
}
default boolean remove(Object key, Object value) {
Object curValue = get(key);
if(! Objects.equals(curValue, value) || (curValue ==null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}
default boolean replace(K key, V oldValue, V newValue) {
Object curValue = get(key);
if(! Objects.equals(curValue, oldValue) || (curValue ==null && !containsKey(key))) {
return false;
}
put(key, newValue);
return true;
}
default V replace(K key, V value) {
V curValue;
if(((curValue = get(key)) ! =null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}
default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
Objects.requireNonNull(mappingFunction);
V v;
if ((v = get(key)) == null) {
V newValue;
if((newValue = mappingFunction.apply(key)) ! =null) {
put(key, newValue);
returnnewValue; }}return v;
}
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue;
if((oldValue = get(key)) ! =null) {
V newValue = remappingFunction.apply(key, oldValue);
if(newValue ! =null) {
put(key, newValue);
return newValue;
} else {
remove(key);
return null; }}else {
return null; }}default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue = get(key);
V newValue = remappingFunction.apply(key, oldValue);
if (newValue == null) {
// delete mapping
if(oldValue ! =null || containsKey(key)) {
// something to remove
remove(key);
return null;
} else {
// nothing to do. Leave things as they were.
return null; }}else {
// add or replace old mapping
put(key, newValue);
returnnewValue; }}default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);
V oldValue = get(key);
V newValue = (oldValue == null)? value : remappingFunction.apply(oldValue, value);if(newValue == null) {
remove(key);
} else {
put(key, newValue);
}
returnnewValue; }}Copy the codeconclusion
This article mainly introduces the whole picture of Java collection from the global point of view. Java collection is also a relatively basic module. Also is the knowledge point that is often asked in interview process!