“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
,v>

//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