Java interview summary summary, including Java key knowledge, as well as common open source framework, welcome to read. The article may have wrong place, because individual knowledge is limited, welcome everybody big guy to point out! The article continues to be updated at……
ID The title address 1 Design Mode Interview Questions (Most comprehensive summary of interview questions) Juejin. Cn/post / 684490… 2 Java Basics (most comprehensive interview questions) Juejin. Cn/post / 684490… 3 Java Set interview Questions (the most comprehensive interview questions) Juejin. Cn/post / 684490… 4 JavaIO, BIO, NIO, AIO, Netty Interview Questions (Most comprehensive summary of interview questions) Juejin. Cn/post / 684490… 5 Java Concurrent Programming Interview questions (most comprehensive interview questions) Juejin. Cn/post / 684490… 6 Java Exception Interview Questions (The most comprehensive interview Questions) Juejin. Cn/post / 684490… 7 Java Virtual Machine (JVM) Interview Questions Juejin. Cn/post / 684490… 8 Spring Interview Questions (the most comprehensive interview questions) Juejin. Cn/post / 684490… 9 Spring MVC Interview Questions (The most comprehensive interview Questions) Juejin. Cn/post / 684490… 10 Spring Boot Interview Questions (Most comprehensive summary of interview questions) Juejin. Cn/post / 684490… 11 Spring Cloud Interview Questions (The most comprehensive interview questions) Juejin. Cn/post / 684490… 12 Redis Interview Questions (most comprehensive summary of interview questions) Juejin. Cn/post / 684490… 13 MyBatis Interview Questions (most comprehensive interview questions) Juejin. Cn/post / 684490… 14 MySQL Interview Questions (most comprehensive interview questions) Juejin. Cn/post / 684490… 15 TCP, UDP, Socket, HTTP interview questions Juejin. Cn/post / 684490… 16 Nginx Interview Questions (The most comprehensive interview Questions) Juejin. Cn/post / 684490… 17 ElasticSearch interview questions 18 Kafka interview questions 19 RabbitMQ interview questions (most comprehensive summary of interview questions) Juejin. Cn/post / 684490… 20 Dubbo Interview Questions (the most comprehensive interview questions) Juejin. Cn/post / 684490… 21 ZooKeeper Interview Questions Juejin. Cn/post / 684490… 22 Netty Interview Questions (Most comprehensive summary of interview questions) 23 Tomcat Interview Questions (The most comprehensive interview questions) Juejin. Cn/post / 684490… 24 Linux Interview Questions (Most comprehensive Summary of interview questions) Juejin. Cn/post / 684490… 25 Internet Related interview Questions (the most comprehensive summary of interview questions) 26 Internet Security Questions (Summary of the most comprehensive interview questions)
Collection Container Overview
What is a set
-
A collection is a container for data, or more specifically, references to data objects
-
Collection classes store references to objects, not objects themselves
-
There are three main types of sets: set, list, and map.
Characteristics of sets
- The characteristics of the collection are as follows:
-
A collection is a container for storing objects. Objects are used to encapsulate data. A large number of objects also need centralized storage management.
-
The size of an object compared to an array is uncertain. Because the set is variable length. Arrays need to be sized in advance
-
The difference between collections and arrays
-
Arrays are fixed length; Set of variable length.
-
Arrays can store both primitive data types and reference data types. Collections can only store reference data types.
-
The elements of an array must be of the same data type; Collections can store objects of different data types.
Benefits of using a collection framework
- Capacity growth;
- It provides high-performance data structures and algorithms to make coding easier and improve program speed and quality.
- Collections can be easily extended or overwritten, improving code reuse and operability.
- By using the JDK’s own collection classes, you can reduce the cost of code maintenance and learning new apis.
What are the common collection classes?
- The Map and Collection interfaces are the parent interfaces of all collections frameworks:
- The subinterfaces of the Collection interface include Set interface and List interface
- The Map interface implementation classes include HashMap, TreeMap, Hashtable, ConcurrentHashMap, and Properties
- The main implementation classes of Set interface are: HashSet, TreeSet, LinkedHashSet and so on
- List interface implementation classes are: ArrayList, LinkedList, Stack and Vector, etc
What’s the difference between List, Set and Map?
-
Java containers are divided into Collection and Map. The subinterfaces of Collection include Set, List, and Queue. We usually use Set and List, Map interface is not a subinterface of collection.
-
A Collection consists of two main interfaces: List and Set
- List: An ordered container in which elements are placed in the same order as they are fetched. Elements can be repeated, multiple null elements can be inserted, and elements have indexes. Common implementation classes are ArrayList, LinkedList, and Vector.
- Set: an unordered container that cannot store duplicate elements. Only one null element is allowed. The element must be unique. Common implementation classes for the Set interface are HashSet, LinkedHashSet, and TreeSet.
-
A Map is a collection of key-value pairs that store mappings between keys, values, and values. Key unordered, unique; Value does not require order and allows repetition. Map does not inherit from the Collection interface. When retrieving elements from a Map Collection, the corresponding value object is returned whenever a key object is given.
- Common implementation classes of Map include HashMap, TreeMap, HashTable, LinkedHashMap, and ConcurrentHashMap
Collection framework underlying data structure
-
Collection
-
List
-
Arraylist: Object array
-
Vector: an Object array
-
LinkedList: a two-way circular list
-
-
Set
- HashSet (unordered, unique) : Implemented based on HashMap, the underlying use of HashMap to store elements
- LinkedHashSet: LinkedHashSet inherits from HashSet and is internally implemented through LinkedHashMap. It’s a bit like LinkedHashMap, which is internally implemented based on Hashmap, but with a slight difference.
- TreeSet (ordered, unique) : red-black tree (self-balanced sorted binary tree)
-
-
Map
- A HashMap: In JDK1.8, a HashMap consists of an array, which is the body of a HashMap, and a list, which is primarily used to resolve hash collisions. Transform linked lists into red-black trees to reduce search time
- LinkedHashMap: LinkedHashMap inherits from HashMap, so the underlying LinkedHashMap is still based on a pulled hash structure consisting of arrays and linked lists or red-black trees. In addition, LinkedHashMap adds a two-way linked list to the above structure, allowing the above structure to maintain the insertion order of key-value pairs. At the same time, the related logic of access order is realized by the operation of linked list.
- HashTable: An array, which is the body of a HashMap, and a list, which is used to resolve hash conflicts
- TreeMap: red-black tree (self-balanced sorted binary tree)
Which collection classes are thread-safe?
- Vector: Is a bit more synchronized than Arraylist, and is less recommended today because it is less efficient.
- HashTable: This is more synchronized than hashMap and is not recommended.
- ConcurrentHashMap: a high-concurrency, high-throughput thread-safe implementation of Java5 HashMap. It consists of a Segment array structure and a HashEntry array structure. The Segment array acts as a lock in ConcurrentHashMap, and the HashEntry is used to store key-value pairs. A ConcurrentHashMap contains an array of segments. The Segment structure is similar to that of a HashMap. A Segment contains an array of hashentries. Each HashEntry is an element of a linked list. Each Segment guards an element in a HashEntry array. When modifying the HashEntry array, you must first acquire its Segment lock. (Recommended)
- .
Fail-fast, a fast failure mechanism for Java collections?
-
Fail-fast is a Java collection error detection mechanism that can occur when multiple threads make structural changes to a collection.
-
Such as: Let’s say there are two threads (thread 1 and thread 2). Thread 1 Iterator iterates through the elements of set A, and thread 2 at some point changes the structure of set A (the structure changes, rather than simply changing the contents of the elements). So when the program will throw ConcurrentModificationException, resulting in a fail – fast mechanism.
-
Reason: The iterator accesses the contents of the collection directly during traversal and uses a modCount variable during traversal. If the contents of the collection change during traversal, the value of modCount is changed. Whenever the iterator iterates over the next element using hashNext()/next(), it checks whether the modCount variable is the expectedmodCount value and returns the traversal if it is; Otherwise, an exception is thrown and the traversal is terminated.
-
Solutions:
-
In traversal, add synchronized wherever it is worth changing modCount.
-
Use CopyOnWriteArrayList instead of ArrayList
-
How do I ensure that a collection cannot be modified?
-
You can use the collections.unmodifiablecollection (Collection C) method to create a read-only Collection, This change of set any operation will throw Java. Lang. UnsupportedOperationException anomalies.
-
Example code is as follows:
List<String> list = new ArrayList<>(); list. add("x"); Collection<String> clist = Collections. unmodifiableCollection(list); clist. add("y"); // The runtime reported an error System. out. println(list. size()); Copy the code
The Collection interface
The List interface
What is an Iterator?
- The Iterator interface provides an interface to iterate over any Collection. We can get an iterator instance from a Collection using the iterator method. Iterators replace Enumeration in the Java collection framework by allowing callers to remove elements during iteration.
- Because all Collection connections inherit from the Iterator
How do I use Iterator? What are the characteristics?
-
Iterator uses the following code:
List<String> list = new ArrayList<>(); Iterator<String> it = list. iterator(); while(it. hasNext()){ String obj = it. next(); System. out. println(obj); } Copy the code -
The characteristics of the Iterator is only one-way traverse, but safer, because it can ensure that, in the current traverse a collection of elements are changed, will throw ConcurrentModificationException.
How do I iterate over and remove elements from a Collection?
-
The only correct way to iterate over a Collection while modifying it is to use the iterator.remove () method, as follows:
Iterator<Integer> it = list.iterator(); while(it.hasNext()){ *// do something* it.remove(); } Copy the code
One of the most common error codes is as follows:
for(Integer i : list){
list.remove(i)
}
Copy the code- Run the above error code will be submitted to the ConcurrentModificationException anomalies. This is because when foreach(for(Integer I: list) is used, an iterator is automatically generated to iterate over the list, while the list is being modified by iterator.remove (). Java generally does not allow one thread to iterate over a Collection while another thread changes it.
What is the difference between Iterator and ListIterator?
- Iterator can iterate over sets and lists, whereas ListIterator can only iterate over lists.
- Iterator can traverse only one way, whereas ListIterator can traverse both ways (forward/back).
- ListIterator implements the Iterator interface and then adds some additional functionality, such as adding an element, replacing an element, and getting the index position of the preceding or following element.
What are the different ways to traverse a List? How does each approach work? What are the best practices for List traversal in Java?
-
The traversal modes are as follows:
- For loop traversal, based on counters. Maintains a counter outside the collection, then reads the elements at each location in turn, stopping when the last element is read.
- Iterator: Iterator. Iterator is an object-oriented design pattern designed to mask the characteristics of different sets of data and unify the interface of traversing collections. Java supports the Iterator schema in Collections.
- Foreach loop traversal. Foreach also uses Iterator internally, without explicitly declaring Iterator or counters. Advantage is simple code, not easy to make mistakes; The disadvantage is that it can only do simple traversal, and can not operate the data set in the traversal process, such as delete and replace.
-
Best practice: The Java Collections framework provides a RandomAccess interface to flag whether the List implementation supports RandomAccess.
-
If a data collection implements this interface, it means that it supports Random Access, with an average time complexity of O(1) to read elements by position, such as ArrayList.
-
If this interface is not implemented, Random Access, such as LinkedList, is not supported.
-
It is recommended that Random Access-enabled lists be iterated through with a for loop, otherwise Iterator or foreach are recommended.
-
Talk about the pros and cons of ArrayList
-
ArrayList has the following advantages:
- ArrayList is a random access pattern, implemented as an array. ArrayList implements the RandomAccess interface, making it very fast to find.
- Arraylists are handy when adding an element sequentially.
-
ArrayList has the following disadvantages:
- When deleting an element, an element copy is required. If you have a lot of elements to copy, it can be performance expensive.
- When inserting an element, you also need to copy the element.
-
ArrayList is suitable for sequential addition and random access scenarios.
How to convert an array to a List?
- Array to List: Use arrays.aslist (array) for conversion.
- List toArray: use the toArray() method that comes with List.
-
Code examples:
// list to array List<String> list = new ArrayList<String>(); list.add("123"); list.add("456"); list.toArray(); // array to list String[] array = new String[]{"123"."456"}; Arrays.asList(array); Copy the code
What is the difference between ArrayList and LinkedList?
- Data structure implementation: ArrayList is a data structure implementation of dynamic arrays, while LinkedList is a data structure implementation of bidirectional linked lists.
- Random access efficiency: ArrayList is more efficient than LinkedList at random access, because LinkedList is linear data storage, so you need to move the pointer back and forth.
- Add and delete efficiency: LinkedList is more efficient at adding and deleting non-beginning and end than ArrayList, because ArrayList adds and deletes affect the subscripts of other data in the array.
- Memory footprint: LinkedList takes up more memory than ArrayList, because in addition to storing data, the node of LinkedList stores two references, one to the previous element and one to the latter.
- Thread-safe: ArrayList and LinkedList are asynchronous, that is, not thread-safe;
-
In general, ArrayList is recommended for frequent reads of elements in a collection, and LinkedList is recommended for heavy inserts and deletions.
-
The bidirectional LinkedList, also known as a doubly LinkedList, is a type of LinkedList in which each data node has two Pointers to direct successors and direct precursors. So, starting from any node in a bidirectional linked list, you can easily access its predecessors and successors.
What is the difference between ArrayList and Vector?
-
Both classes implement the List interface (which inherits the Collection interface), and they are both ordered collections
- Thread-safe: Vector uses Synchronized for thread synchronization and is thread-safe, whereas ArrayList is non-thread-safe.
- Performance: ArrayList outperforms Vector in terms of performance.
- Capacity expansion: ArrayList and Vector both dynamically adjust their capacity based on actual needs, except that Vector doubles its capacity each time it expands, whereas ArrayList only increases its capacity by 50%.
-
All methods of the Vector class are synchronized. It is possible for two threads to access a Vector safely, but for one thread to access a Vector, the code takes a lot of time to synchronize operations.
-
Arraylist is not synchronous, so it is recommended when thread safety is not required.
Which is faster when inserting data, ArrayList, LinkedList, or Vector? ArrayList, Vector, LinkedList storage performance and features
-
The underlying implementations of ArrayList and Vector use arrays to store data. The number of elements in an array is larger than the actual stored data in order to add and insert elements. Both of them allow indexing elements directly by ordinal number, but inserting elements involves memory operations such as moving array elements, so indexing data is fast and inserting data is slow.
-
The methods in Vector are thread-safe because of the synchronized modifier, but perform worse than ArrayList.
-
LinkedList uses bidirectional LinkedList to realize storage. Index data by serial number needs to be traversed forward or backward, but when inserting data, only the items before and after the current item need to be recorded, so LinkedList inserts quickly.
How to use ArrayList in multithreaded scenarios?
-
Arraylists are not thread-safe, and can be converted into thread-safe containers for use in multithreaded scenarios through Collections’ synchronizedList method. For example:
List<String> synchronizedList = Collections.synchronizedList(list); synchronizedList.add("aaa"); synchronizedList.add("bbb"); for (int i = 0; i < synchronizedList.size(); i++) { System.out.println(synchronizedList.get(i)); } Copy the code
Why is the elementData of an ArrayList decorated with transient?
-
The arrays in ArrayList are defined as follows:
private transient Object[] elementData;
-
Look again at the definition of ArrayList:
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess.Cloneable.java.io.Serializable Copy the code -
You can see that ArrayList implements the Serializable interface, which means that ArrayList supports serialization. WriteObject is a transient array that does not want to be serialized.
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{*// Write out element count, and any hidden stuff* int expectedModCount = modCount; s.defaultWriteObject(); *// Write out array length* s.writeInt(elementData.length); *// Write out all elements in the proper order.* for (int i=0; i<size; i++) s.writeObject(elementData[i]); if(modCount ! = expectedModCount) {throw new ConcurrentModificationException(); } Copy the code -
At each serialization, defaultWriteObject() is called to serialize the non-transient elements in the ArrayList, and elementData is iterated to serialize only the stored elements. The serialized file size is also reduced.
Difference between a List and a Set
-
List and Set are inherited from the Collection interface
-
A List is an ordered container. Elements can be repeated. Multiple null elements can be inserted. Common implementation classes are ArrayList, LinkedList, and Vector.
-
A Set is an unordered container that cannot store duplicate elements. Only one null element is allowed to store, and the element must be unique. Common implementation classes for the Set interface are HashSet, LinkedHashSet, and TreeSet.
-
In addition, List supports for loop, that is, traversal by subscript, can also use iterators, but set can only be used iteration, because it is unordered, can not use subscript to get the desired value.
-
Compare Set with List
- Set: It is inefficient to retrieve elements, but efficient to delete and insert elements. Insert and delete elements do not change their positions.
- List: Like an array, a List can grow dynamically. It is efficient to find elements, but inefficient to insert and delete elements, because it causes other elements to change positions
The Set interface
How does HashSet work?
- HashSet is implemented based on HashMap. The value of HashSet is stored on the key of HashMap, and the value of HashMap is presented. Therefore, the implementation of HashSet is relatively simple. Basically, this is done by directly calling the related methods of the underlying HashMap, and the HashSet does not allow duplicate values.
How does a HashSet check for repetitions? How does a HashSet guarantee that data is not repeatable?
-
When adding () elements to a HashSet, the existence of elements is determined not only by comparing hash values, but also by comparing them with the EQules method.
-
The add () method in a HashSet uses the Put () method of a HashMap.
-
The key of a HashMap is unique, and the value added to the HashSet is the key of the HashMap. In a HashMap, if K/V are the same, the new V overwrites the old V and returns the old V. So there is no duplication (HashMap compares keys to equals first hashCode then equals).
-
HashSet HashSet HashSet
private static final Object PRESENT = new Object(); private transient HashMap<E,Object> map; public HashSet(a) { map = new HashMap<>(); } public boolean add(E e) { // Call the put method of the HashMap. PRESENT is a virtual value that is the same throughout return map.put(e, PRESENT)==null; } Copy the code
HashCode () equals ()
- If two objects are equal, the Hashcode must also be the same
- HashCode is a value of type int computed by the JDK from the address of the object or from a string or number
- Return true for both equals methods when two objects are equal
- Two objects have the same hashCode value, and they are not necessarily equal
- If equals is overridden, hashCode must be overridden as well
- The default behavior of hashCode() is to generate unique values for objects on the heap. If hashCode() is not overridden, the two objects of the class will never be equal anyway (even if they point to the same data).
== = equals
- Equals equals determines whether two variables or instances refer to the same memory space
- Equals () compares the contents of strings
Difference between HashSet and HashMap
HashMap HashSet The Map interface is implemented Implementing the Set interface Store key-value pairs Store only objects Call put () to add elements to the map Call the add () method to add elements to the Set A HashMap computes a Hashcode using a Key A HashSet uses member objects to calculate the hashCode value. Hashcode may be the same for two objects, so equals() is used to determine the equality of the objects, and returns false if the two objects are different A HashMap is faster than a HashSet because it uses a unique key to get objects A HashSet is slower than a HashMap
The Map interface
What is a Hash algorithm
- A hash algorithm maps a binary of arbitrary length to a smaller binary of fixed length, called a hash value.
What is a linked list
-
Linked list can connect discontinuous data on physical addresses, and operate physical addresses through Pointers, realizing functions such as adding, deleting, modifying, and searching.
-
Linked lists can be roughly divided into single linked lists and bidirectional linked lists
-
Single linked list: Each node contains two parts: one is data, which holds the data variable, and the other is the next pointer to the next node
-
Bidirectional linked list: In addition to the section containing the single linked list, add the pointer to the previous node of the pre
-
-
Advantages of linked lists
- Fast insertion and deletion (because the next pointer points to the next node, it is convenient to add and delete elements by changing the pointer pointer)
- High memory utilization, no memory waste (can use small discontinuous space in memory (larger than the size of node nodes), and only create space when needed)
- Size is not fixed, expansion is flexible.
-
Disadvantages of linked lists
- It cannot be searched randomly, but must be traversed from the first, which is inefficient
How does HashMap work?
-
Overview of HashMap: HashMap is an asynchronous implementation of the Map interface based on hash tables. This implementation provides all optional mapping operations and allows null values and NULL keys. This class does not guarantee the order of the mapping, and in particular it does not guarantee that the order is constant.
-
The data structure of HashMap: In the Java programming language, the most basic structure is two kinds, one is an array, the other is a mock pointer (reference), all data structures can be constructed with these two basic structures, HashMap is no exception. A HashMap is actually a “linked list hash” data structure, which is a combination of arrays and lists.
-
HashMap is implemented based on the Hash algorithm
-
When we put an element into a HashMap, we rehash the index of the current object’s element in the array using the key’s hashCode
-
If keys with the same hash value are used during storage, there are two scenarios.
(1) If the key is the same, the original value is overwritten;
(2) If the key is different (conflict occurs), the current key-value will be put into the linked list
-
When obtaining the hash value, it directly finds the subscript corresponding to the hash value and further checks whether the key is the same to find the corresponding value.
-
After understanding the above process, it is not difficult to understand how HashMap solves the problem of hash conflicts. The core is to use the storage mode of array, and then put the objects of the conflicting keys into the linked list. Once the conflicts are found, further comparison will be made in the linked list.
-
-
In Jdk 1.8, the implementation of HashMap is optimized. When there are more than eight nodes in the list, the list will be converted to a red-black tree to improve query efficiency, from O(n) to O(logn).
How does HashMap differ in JDK1.7 and JDK1.8? The underlying implementation of HashMap
- In Java, there are two relatively simple data structures for storing data: arrays and linked lists. The characteristics of arrays are: easy to address, insert and delete difficult; Linked lists are difficult to address, but easy to insert and delete; So we combine arrays and linked lists, playing to the strengths of both, using a method called the zipper method to resolve hash conflicts.
Before a HashMap JDK1.8
- Previously, JDK1.8 used the zipper method. Zipper method: Combine linked lists and arrays. That is, create an array of linked lists, where each cell is a linked list. If a hash conflict is encountered, add the value of the conflict to the linked list.
After a HashMap JDK1.8
- Compared to previous versions, JDK1.8 has a major change in resolving hash conflicts by converting lists to red-black trees when their length is greater than the threshold (8 by default) to reduce search time.
Comparison of JDK1.7 VS JDK1.8
- JDK1.8 mainly addresses or optimizes the following issues:
- Resize Capacity expansion optimization
- Red black tree is introduced to avoid the query efficiency caused by the excessively long single linked list. Please refer to the algorithm of red black tree
- It solves the problem of multi-thread dead-loop, but it is still non-thread-safe, which may cause data loss problems when multi-threading.
different JDK 1.7 JDK 1.8 Storage structure Array + linked list Array + linked list + red-black tree Initialization mode Individual functions: inflateTable()Directly integrated into the capacity expansion function resize()In theHash value calculation method Perturbation = 9 perturbations = 4 bit operations + 5 XOR operations Perturbation = 2 perturbations = 1 bit operation + 1 xOR operation Rules for storing data When there are no conflicts, store arrays. In case of conflicts, store the linked list When there are no conflicts, store arrays. Collision & List length < 8: store single linked list; Collision & list length > 8: tree and red black tree Data insertion mode Head insertion method (first move the data from the original position to the last 1 bit, and then insert the data to the position) Tail insertion (directly into the end of the list/red-black tree) How to calculate the storage location after capacity expansion Do all the calculations in the original way (i.e. HashCode ->> Perturbation function ->> (h&Length-1)) Calculate according to the rule after expansion (i.e. location after expansion = original location or original location + old capacity)
What is a red-black tree
What is a binary tree when we talk about red-black trees
-
A binary tree simply means that each node can be associated with two child nodes
-
A / \ b c / \ / \ d e f g / \ / \ / / \ / / h I j k l m n oCopy the code
-
Red and black tree
-
Red-black tree is a special binary search tree. Each node of a red-black tree has a memory bit to indicate the color of the node, which can be Red or Black.
-
Every node of a red-black tree is black or red. Anyway, his root is black. Every leaf node is also black (a leaf node is a terminal node, a terminal node). .
-
If a node is red, its children must be black.
-
Every node goes through the same number of black nodes to the leaf node NIL. Make sure no path is twice as long as any other, so a red-black tree is relatively close to a balanced binary tree!
-
The basic operations of red-black trees are add and delete. The rotation method is used after adding or deleting a red-black tree. Why is that? The reason is very simple, after adding or deleting nodes in a red-black tree, the structure of the red-black tree changes. It may not meet the above three properties, and it is no longer a red-black tree, but an ordinary tree. By rotating and changing colors, the tree can be turned back into a red-black tree. Simply put, the purpose of rotation and color change is to keep the tree red-black.
How does a HashMap put function flow?
-
HashCode () and key.hashcode ()>>>16. The hash method actually performs xor on key.hashcode () and key.hashcode ()>>>16. So the hash function basically does this: the high 16bit stays the same, and the low 16bit and the high 16bit do an xor to reduce collisions. Index = (table.length-1) & hash (index = (table.length-1) &hash (index = (table.length-1) &hash); After considering the speed, function, and quality, the designers use xOR of high and low 16bits to simplify the process to reduce collisions, and JDK8 uses O (logn) tree structure to improve performance under collisions.
-
PutVal method execution flowchart
public V put(K key, V value) {
return putVal(hash(key), key, value, false.true);
}
static final int hash(Object key) {
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
// Implement map.put and related methods
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// Step 1: If TAB is empty, create one
// The table is not initialized or has a length of 0
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// Step 2: calculate index and handle null
// (n-1) &hash (n - 1) hash (n - 1) hash (n - 1) hash (n - 1) hash (n - 1) hash (n - 1) hash (n - 1) hash (n - 1) hash (n - 1) hash
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// Elements already exist in the bucket
else {
Node<K,V> e; K k;
// Step 3: The node key exists, overwriting the value directly
// Compare the hash value of the first element (node in the array) and the key value
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
// Assign the first element to e, denoted by e
e = p;
// Step 4: Determine that the chain is a red-black tree
// Hash values are not equal, that is, keys are not equal; Is a red-black tree node
// If the current element type is TreeNode, it is a red-black tree. PutTreeVal returns the node to be stored. E may be null
else if (p instanceof TreeNode)
// Put it in the tree
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// Step 5: The chain is a linked list
// Is a linked list node
else {
// Insert nodes at the end of the list
for (int binCount = 0; ; ++binCount) {
// get to the end of the list
// Check whether the list tail pointer is null
if ((e = p.next) == null) {
// Insert a new node at the end
p.next = newNode(hash, key, value, null);
// Determine whether the length of the list reaches the critical value of converting a red-black tree. The critical value is 8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// List structure to tree structure
treeifyBin(tab, hash);
// Break the loop
break;
}
// Check whether the key value of the node in the list is equal to the key value of the inserted element
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
// equal, out of the loop
break;
E = p.ext; // This is used to iterate over the bucket listp = e; }}// If the hash value is the same as the hash value, the new hash value will be returned
if(e ! =null) {
// Record the value of e
V oldValue = e.value;
// onlyIfAbsent Is false or the old value is null
if(! onlyIfAbsent || oldValue ==null)
// Replace the old value with the new value
e.value = value;
// Callback after access
afterNodeAccess(e);
// Return the old value
returnoldValue; }}// Structural changes
++modCount;
// Step 6: Expand the capacity when the capacity exceeds the maximum
// If the actual size is greater than the threshold, expand the capacity
if (++size > threshold)
resize();
// Callback after insertion
afterNodeInsertion(evict);
return null;
}
Copy the code- Check whether the key-value pair array table[I] is empty or null; otherwise, perform resize() for expansion.
- Table [I]==null; if table[I] is not null, go to ⑥; if table[I] is not null, go to ③;
- Check whether the first element of table[I] is the same as the first element of key.
- Check whether table[I] is a treeNode, that is, whether table[I] is a red-black tree. If table[I] is a red-black tree, insert a key-value pair directly into the tree; otherwise, change to 5.
- Table [I] is traversed to determine whether the length of the linked list is greater than 8. If the length is greater than 8, the linked list is converted into a red-black tree and the insertion operation is performed in the red-black tree; otherwise, the insertion operation of the linked list is carried out. If the key already exists in the traversal process, the value can be overwritten directly.
- After the insert is successful, check whether the number of existing key value pairs size exceeds the maximum capacity threshold. If so, expand the capacity.
How is the HashMap expansion operation implemented?
-
In JDK1.8, the resize method is called when the key pair in the hashMap exceeds the threshold or during initialization.
-
Every time it expands, it’s twice as big;
-
After the extension, the Node object is either in the same position or moved to twice the original offset.
-
In putVal(), we see that the resize() method is used twice in this function. Resize () means that it will be expanded during the first initialization. Or if the actual size of the array is greater than the critical value (12 for the first time), the element above the bucket will be redistributed during expansion. This is also an optimization in JDK1.8. In 1.7, after expansion, the Hash value needs to be re-computed and distributed according to the Hash value. In version 1.8, however, it is determined whether (e.hash & oldCap) is 0 in the same bucket position. After the hash assignment, the position of the element will either stay at the original position or move to the original position + the increased array size
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table;//oldTab points to the hash bucket array int oldCap = (oldTab == null)?0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) {// If oldCap is not empty, the hash bucket array is not empty if (oldCap >= MAXIMUM_CAPACITY) {// If it is larger than the maximum capacity, the value is assigned to the maximum integer threshold threshold = Integer.MAX_VALUE; return oldTab;/ / return }// If the current hash bucket array length is still smaller than the maximum capacity and oldCap is greater than the default value 16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold Double capacity expansion threshold } // The old capacity is 0, but the threshold is greater than zero, indicating that the parameter structure has cap incoming, threshold has been initialized to the minimum power of 2 n // Assign the value directly to the new capacity else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // Create a map with no parameters, giving the default capacity and threshold 16, 16*0.75 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // New threshold = new cap * 0.75 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; // Assign the new array length to the current member variable table @SuppressWarnings({"rawtypes"."unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];// Create a hash bucket array table = newTab;// Copy the value of the new array to the old hash bucket array // If the original array is not initialized, then the initialization of resize is finished. Otherwise, the element rearrangement logic is entered to make it evenly dispersed if(oldTab ! =null) { // Iterate over all bucket subscripts in the new array for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if((e = oldTab[j]) ! =null) { // The bucket index of the old array is assigned to the temporary variable e, and the old array is unreferenced, otherwise the array cannot be collected by GC oldTab[j] = null; // If e.next==null, there is only one element in the bucket and no linked list or red-black tree exists if (e.next == null) // Add the element to the new array using the same hash mapping algorithm newTab[e.hash & (newCap - 1)] = e; // If e is TreeNode and e.next! =null, then the rearrangement of elements in the tree is processed else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // e is the head of the list and e.next! =null, then the linked list elements are rearranged else { // preserve order // loHead,loTail indicates that the subscript need not be changed after expansion, see note 1 Node<K,V> loHead = null, loTail = null; // hiHead,hiTail stands for subscript after expansion, see note 1 Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // Iterate over the list do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) // Initialize head to point to the current list element e, e may not be the first list element, after initialization loHead // represents the first element of the list whose subscript remains unchanged loHead = e; else // lotail. next points to current e loTail.next = e; // loTail points to the current element e // After initialization, loTail and loHead point to the same memory, so when lotail.next points to the next element, // The next reference to the element in the underlying array changes accordingly, resulting in lowhead.next-next..... // Follow loTail so that lowHead can be linked to all elements belonging to the list. loTail = e; } else { if (hiTail == null) // Initialize head to the current list element e, hiHead represents the subscript changed list header element hiHead = e; elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null); // At the end of the loop, point tail to null and place the list header into the corresponding index of the new array to form a new map. if(loTail ! =null) { loTail.next = null; newTab[j] = loHead; } if(hiTail ! =null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } Copy the code
How does HashMap resolve hash conflicts?
- A: Before we can solve this problem, we first need to know what hash conflict is, and before we can understand hash conflict, we need to know what hash is.
What is a hash?
- A Hash is the use of a Hash algorithm that maps a binary of arbitrary length to a smaller binary value of fixed length, which is called a Hash.
What is the Hashish conflict?
- When two different input values compute the same hash value according to the same hash function, we call it a hash collision.
The data structure of the HashMap
- In Java, there are two relatively simple data structures for storing data: arrays and linked lists.
- The characteristics of arrays are: easy to address, insert and delete difficult;
- Linked lists are difficult to address, but easy to insert and delete;
- So we combine arrays and linked lists, taking advantage of their respective strengths, and can use two methods: linked address method and open address method to resolve hash conflicts:
- Linked list method is to organize objects with the same hash value into a linked list and put them in the corresponding slot of hash value.
- The open address method uses a detection algorithm to search for the next available slot when a slot is already occupied.
- DEFAULT_INITIAL_CAPACITY = 1 << 4 (that is, 2 to the fourth power of 16) is much smaller than the size of the int returned by hashCode. Therefore, if we simply use hashCode to get the corresponding bucket, it will greatly increase the probability of hash collisions, and in the worst case, it will turn the HashMap into a single linked list, so we need to optimize hashCode to some extent
Hash () function
-
The problem mentioned above is mainly because if hashCode is used for mod, only the low value of hashCode will participate in the operation, and the high value will not play any role. Therefore, our idea is to let the high value of hashCode also participate in the operation, so as to further reduce the probability of hash collision and make the data distribution more even. We call this operation a perturbation, and the hash() function in JDK 1.8 looks like this:
static final int hash(Object key) { int h; return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);// Move 16 bits to the right for xOR (high and low xor) } Copy the code -
This is much cleaner than in JDK 1.7, where only one bit and one xor (two perturbations) were performed, compared to four bits and five xor operations (nine perturbations) in 1.7.
conclusion
- Here’s a quick summary of the methods that HashMap uses to effectively resolve hash conflicts:
- Linked list method is to organize objects with the same hash value into a linked list and put them in the corresponding slot of hash value.
- The open address method uses a detection algorithm to search for the next available slot when a slot is already occupied.
Can I use any class as a Map key?
You can use any class as a Map key, but before you use it, consider the following:
-
If a class overrides equals(), it should also override hashCode().
-
All instances of a class need to follow rules related to equals() and hashCode().
-
If a class does not use equals(), it should not be used in hashCode().
-
The best practice for the user-defined Key class is to make it immutable so that hashCode() values can be cached for better performance. Immutable classes also ensure that hashCode() and equals() do not change in the future, which would solve the mutable problem.
Why wrapper classes like String and Integer in HashMap are suitable for K?
- A: The features of wrapper classes such as String and Integer ensure the immodification of Hash values and the accuracy of calculation, which can effectively reduce the probability of Hash collisions
- Both types are final, that is, immutable, to ensure that keys cannot be modified and hash values cannot be obtained differently
- The interior has been rewritten
equals(),hashCode()And other methods comply with the internal specification of HashMap (if not clear, you can see the process of putValue above), which is not prone to Hash value calculation errors;
What if you use Object as the Key of a HashMap?
- A: rewrite
hashCode()andequals()methods- Rewrite hashCode() because you need to calculate where the data is stored, and you need to be careful not to try to improve performance by excluding critical parts of an object from the Hash code calculation, which is faster but may result in more Hash collisions;
- Override equals() with reflexivity, symmetry, transitivity, consistency, and x.equals(null) must return false for any non-null reference value x to ensure uniqueness of keys in the hash table.
Why not use the hash value of hashCode() as the subscript of the table?
-
A: The hashCode() method returns an int integer ranging from -(2 ^ 31) to (2 ^ 31-1), which is about 4 billion mapping Spaces. The size of a HashMap ranges from 16 (the default value) to 2 ^ 30. It is also difficult to provide so much storage space on the device that the hash calculated by hashCode() may not be in the array size range and thus cannot match the storage location.
-
So what’s the solution?
-
HashMap implements its own hash() method, which makes the high and low bits of its hash value perform xOR operation by itself through two perturbations, reducing the probability of hash collision and making the data distribution more even.
-
When the array length is a power of 2, it is more efficient to use the hash() value and (&) (array length -1) to get the index of the array. H &(length-1) is equivalent to h%length. Thirdly, the problem of “the hash value does not match the array size range” is solved.
-
Why is the length of a HashMap a power of 2
-
In order for HashMap access to be efficient, there should be as few collisions as possible, that is, data should be distributed as evenly as possible, with each list/red-black tree roughly the same length. The implementation is the algorithm that stores the data in the linked list/red-black tree.
-
How should this algorithm be designed?
- The first thing we might think of is doing % mod. Hash %length== Hash &(leng-1) hash%length==hash&(leng-1) if length is 2 to the n; .” And the binary operation & is more efficient than %, which explains why the length of a HashMap is a power of 2.
-
So why two disturbances?
- A: In this way, the randomness of the lower part of the Hash value is increased to make the distribution more uniform, so as to improve the randomness and uniformity of the corresponding array storage index position, and finally reduce the Hash conflict. Only two times is enough, which has reached the purpose of the high and low part of the operation at the same time.
What is the difference between HashMap and HashTable?
- Thread safetyHashMap is thread-safe, HashTable is thread-safe; The internal methods of HashTable basically pass through
synchronizedModification. (Use ConcurrentHashMap if you want to be thread-safe); - Efficiency: Because of thread-safety issues, HashMap is a little more efficient than HashTable. Also, HashTable is largely obsolete, so don’t use it in your code; (Use ConcurrentHashMap if you want to be thread-safe);
- Support for Null keys and Null values: In a HashMap, Null can be used as a key. There is only one such key, and there can be one or more keys corresponding to the value Null. NullPointerException is thrown whenever a key value in a HashTable contains a NULL.
- The difference between the initial capacity and each expansion capacity ：
- If you do not specify an initial capacity when creating a Hashtable, the default initial size of the Hashtable is 11. After each expansion, the original capacity is 2N +1. The default initialization size of a HashMap is 16. After each expansion, the capacity is doubled.
- If you create a Hashtable with an initial capacity, the Hashtable will use the size you gave it, and the HashMap will expand it to a power of two. That is, a HashMap always uses a power of 2 as its hash table size, and I’ll explain why later.
- Underlying data structure: HashMap since JDK1.8 has a major change in resolving hash collisions, converting lists to red-black trees to reduce search time when the list length is greater than the threshold (8 by default). Hashtable has no such mechanism.
- Recommended use: As you can see in the class annotation of Hashtable, Hashtable is a reserved class and is not recommended to be used. It is recommended to use HashMap in single-threaded environments, or ConcurrentHashMap in multi-threaded environments.
What is a TreeMap introduction
- A TreeMap is an ordered set of key-values implemented through a red-black tree.
- TreeMap is implemented based on a red-black tree. The map is sorted according to the natural order of its keys, or according to the Comparator provided when the map was created, depending on the constructor used.
- TreeMap is thread asynchronous.
How do I decide to use HashMap or TreeMap?
- A HashMap is the best choice for inserting, deleting, and positioning elements into a Map. However, if you need to iterate over an ordered set of keys, TreeMap is a better choice. Depending on the size of your collection, it may be faster to add elements to the HashMap, replacing the map with TreeMap for an ordered key traversal.
The difference between HashMap and ConcurrentHashMap
- ConcurrentHashMap segments the entire bucket array, and then protects each Segment with a lock lock. Compared with synchronized lock of HashTable, the granularity is finer and the concurrency performance is better. Not thread-safe. (after JDK1.8, ConcurrentHashMap is implemented in a new way, using the CAS algorithm.)
- A HashMap allows NULL key-value pairs, but ConCurrentHashMap does not.
ConcurrentHashMap and Hashtable?
-
The main difference between ConcurrentHashMap and Hashtable is in the way thread-safe is implemented.
- ConcurrentHashMap in JDK1.7 uses a partitionalized array + linked list. The data structure used in JDK1.8 is the same as that in HashMap1.8: array + linked list/red-black binary tree. The underlying data structure of Hashtable and HashMap before JDK1.8 is similar to that of array + linked list. Array is the body of HashMap, while linked list is mainly used to solve hash conflicts.
- Thread-safe way to implement:
- In JDK1.7, ConcurrentHashMap segments the entire bucket array. Each lock locks only a portion of the container’s data. When multiple threads access different data segments in the container, there is no lock contention, which improves the concurrent access rate. (The default allocation of 16 segments is 16 times more efficient than Hashtable.) In JDK1.8, the concept of Segment has been abandoned, but directly using Node array + linked list + red-black tree data structure to achieve concurrency control using synchronized and CAS to operate. The whole thing looks like an optimized, thread-safe HashMap. Although you can still see the Segment data structure in JDK1.8, the attributes have been simplified to make it compatible with older versions.
- ② Hashtable: Synchronized is an inefficient way to ensure thread safety. When one thread accesses the synchronous method, other threads also access the synchronous method, and may enter the blocking or polling state. For example, if you use PUT to add elements, another thread cannot use PUT to add elements, nor can it use GET. The competition becomes increasingly fierce and the efficiency becomes lower.
-
A comparison of the two:
1, HashTable:
2. ConcurrentHashMap for JDK1.7
3, JDK1.8 ConcurrentHashMap (TreeBin: red and black binary tree Node: linked list Node) :
- A: ConcurrentHashMap combines the best of both HashMap and HashTable. HashMap does not consider synchronization, HashTable does consider synchronization and uses the synchronized keyword, so a HashTable locks the entire structure every time a synchronization is performed. The way the ConcurrentHashMap lock works is slightly fine-grained.
Is the ConcurrentHashMap underlying implementation known? What is the implementation principle?
JDK1.7
-
First, the data is divided into sections for storage, and then each section of data is assigned a lock. When a thread uses the lock to access one section of data, the data of other sections can also be accessed by other threads.
-
In JDK1.7, ConcurrentHashMap is implemented using Segment + HashEntry.
-
A ConcurrentHashMap contains an array of segments. The structure of a Segment is similar to that of a HashMap. It is an array and a linked list structure. Each Segment contains a HashEntry array. When modifying the data in a HashEntry array, you must first acquire the lock on the corresponding Segment.
- This class contains two static inner classes, HashEntry and Segment; The former is used to encapsulate key-value pairs of the mapping table, while the latter acts as locks.
- A Segment is a ReentrantLock. Each Segment guards an element in a HashEntry array. When modifying a HashEntry array, you must first obtain the corresponding Segment lock.
JDK1.8
-
In JDK1.8, the design of Segment bloating is abandoned, and instead Node + CAS + Synchronized is used to ensure concurrency safety. Synchronized only locks the first Node of the current linked list or red-black binary tree, so as long as hash does not conflict, concurrency will not occur. Efficiency goes up another N times.
-
The structure is as follows:
-
Additional source code, there is a need to see
-
Insert element process (recommend to see source code) :
-
If the Node is not initialized, CAS is called to insert the corresponding data.
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } Copy the code -
If the Node at the corresponding position is not empty and the current Node is not in the moving state, a synchronized lock is applied to the Node. If the hash of the Node is not less than 0, the linked list is traversed to update the Node or a new Node is inserted.
if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) { oldVal = e.val; if(! onlyIfAbsent) e.val = value;break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; }}}Copy the code
- If the node is a TreeBin node, it is a red-black tree structure. Insert the node into the red-black tree using putTreeVal. If binCount is not 0, the put operation affects the data. If the number of linked lists reaches 8, the value is converted to a red-black tree using the treeifyBin method. If oldVal is not empty, the value is an update operation and does not affect the number of elements.
- If a new node is inserted, the addCount() method attempts to update the number of elements baseCount;
Auxiliary tools class
What’s the difference between Array and ArrayList?
- Array can store basic data types and objects, and ArrayList can store only objects.
- Array is assigned a fixed size, whereas ArrayList is automatically expanded.
- There are not as many built-in Array methods as ArrayList. For example, addAll, removeAll, iteration, and other methods are available only in ArrayList.
For primitive type data, collections use automatic boxing to reduce the coding effort. However, this approach is relatively slow when dealing with basic data types of fixed size.
How to convert between Array and List?
- Array to List: array.aslist (Array);
- List toArray: the toArray() method of List.
Comparable and Comparator?
- The Comparable interface is actually from the java.lang package, which has a compareTo(Object obj) method for sorting
- The comparator interface is actually from the java.util package, which has a compare(Object obj1, Object obj2) method for sorting
- When we need to use custom sorting on a collection, we need to override compareTo or compare. When we need to implement two sorting methods on a collection, for example, we need to use one sorting method on the name of a song and one sorting method on the name of an artist. We could override the compareTo method and use our own Comparator method or implement song and star name sorting with two comparators, the second meaning that we could only use the two-parameter version of collections.sort ().
What’s the difference between a Collection and a Collection?
- Java.util. Collection is a Collection interface (a top-level interface of the Collection class). It provides generic interface methods for performing basic operations on collection objects. The Collection interface has many concrete implementations in the Java class library. The significance of Collection interface is to provide maximum unified operation mode for various specific collections, and its direct inheritance interfaces are List and Set.
- Collections is a utility/helper class of the collection class that provides a set of static methods for sorting, searching, and thread-safe operations on the elements in the collection.
How do TreeMap and TreeSet compare elements when sorting? How does the sort() method in the Collections utility class compare elements?
-
TreeSet requires that the class to which the object belongs implement the Comparable interface, which provides a compareTo() method for comparing elements that is called back to compare their size when they are inserted. TreeMap requires that the keys of a stored key-value pair map implement the Comparable interface to sort elements by key.
-
The Sort method of the Collections utility class comes in two overloaded forms,
-
The first requires the comparison of objects in the incoming container to be sorted to implement the Comparable interface to enable the comparison of elements.
?
- The Comparable interface is actually from the java.lang package, which has a compareTo(Object obj) method for sorting
- The comparator interface is actually from the java.util package, which has a compare(Object obj1, Object obj2) method for sorting
- When we need to use custom sorting on a collection, we need to override compareTo or compare. When we need to implement two sorting methods on a collection, for example, we need to use one sorting method on the name of a song and one sorting method on the name of an artist. We could override the compareTo method and use our own Comparator method or implement song and star name sorting with two comparators, the second meaning that we could only use the two-parameter version of collections.sort ().
What’s the difference between a Collection and a Collection?
- Java.util. Collection is a Collection interface (a top-level interface of the Collection class). It provides generic interface methods for performing basic operations on collection objects. The Collection interface has many concrete implementations in the Java class library. The significance of Collection interface is to provide maximum unified operation mode for various specific collections, and its direct inheritance interfaces are List and Set.
- Collections is a utility/helper class of the collection class that provides a set of static methods for sorting, searching, and thread-safe operations on the elements in the collection.
How do TreeMap and TreeSet compare elements when sorting? How does the sort() method in the Collections utility class compare elements?
-
TreeSet requires that the class to which the object belongs implement the Comparable interface, which provides a compareTo() method for comparing elements that is called back to compare their size when they are inserted. TreeMap requires that the keys of a stored key-value pair map implement the Comparable interface to sort elements by key.
-
The Sort method of the Collections utility class comes in two overloaded forms,
-
The first requires the comparison of objects in the incoming container to be sorted to implement the Comparable interface to enable the comparison of elements.
-
The second, non-mandatory, requires that the elements in the container be comparable, but requires passing in a second argument that is a subtype of the Comparator interface (the compare method needs to be overridden to compare elements). It is also an application of the callback pattern (Java’s support for functional programming).