“This is the 16th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
A collection,
1. What are the specific implementation classes of collection framework, list, map and set, and what are the differences
List: ordered, repeatable; Index query speed; Insert/delete is slow with data movement
Set: unordered and cannot be repeated
Map: key-value pairs with unique keys and multiple values
List and Set inherit from Collection interface, Map does not
Vector doubles to be thread-safe
2. Thread-safe and non-thread-safe collection classes
LinkedList, ArrayList, and HashSet are not thread-safe; Vector is thread-safe
HashMap is thread-safe, HashTable is thread-safe
StringBuilder is not thread-safe, StringBuffer is thread-safe
3. The difference between arrays and ArrayLists
The bottom of an ArrayList is a variable-length array, so you don’t need to define its size. If it’s not long enough, it will automatically grow to twice its original length
The size of an array is already a fixed value when it is defined and does not automatically expand. Arrays are more efficient than collections
1) overview
In JDK1.8, HashMap array + list + red-black tree implementation, when the list length exceeds the threshold (8), the list is converted to red-black tree
2) Implementation principle
3) Data structures involved in JDK1.8
(1) Bit bucket array
transient Node<k,v>[] table;// An array of buckets
Copy the code(2) Node
implements the Entry interface
//Node is a one-way linked list that implements the Map.Entry interface
static class Node<k.v> implements Map.Entry<k.v> {
final int hash;
final K key;
V value;
Node<k,v> next;
// The constructor Hash the key to the next node
Node(int hash, K key, V value, Node<k,v> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey(a) { return key; }
public final V getValue(a) { return value; }
public final String toString(a) { return key + = + value; }
public final int hashCode(a) {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// Check whether two nodes are equal. If both key and value are equal, return true. Can be true compared to itself
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceofMap.Entry) { Map.Entry<! -? ,? --> e = (Map.Entry<! -? ,? -->)o;if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
Copy the code(3) the red-black tree
/ / the red-black tree
static final class TreeNode<k.v> extends LinkedHashMap.Entry<k.v> {
TreeNode<k,v> parent; / / the parent node
TreeNode<k,v> left; / / the left subtree
TreeNode<k,v> right; / / right subtree
TreeNode<k,v> prev; //needed to unlink next upon deletion
boolean red; // Color attributes
TreeNode(int hash, K key, V val, Node<k,v> next) {
super(hash, key, val, next);
}
// Returns the root node of the current node
final TreeNode<k,v> root(a) {
for (TreeNode<k,v> r = this, p;;) {
if ((p = r.parent) == null)
returnr; r = p; }}..Copy the code