The Collection Collection
List
ArrayList
attribute
// Default initialization length
private static final int DEFAULT_CAPACITY = 10;
/ / an empty array
private static final Object[] EMPTY_ELEMENTDATA = {};
// Default empty array
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// The built array
transient Object[] elementData;
// Array length
private int size;
AbstractArrayList = AbstractArrayList */
protected transient int modCount = 0;
Copy the codeInitialize the
// 1. Create a default empty array object with no arguments
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Create an array object of the specified length
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// Create an empty array object with a length of 0
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}// 3. The argument is the construction of the collection
public ArrayList(Collection<? extends E> c) {
// Convert the collection to an array object
Object[] a = c.toArray();
if((size = a.length) ! =0) {
// Sets of type ArrayList are directly converted to the current object
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
// Copies the transformed array and builds the copied values into the current ArrayList objectelementData = Arrays.copyOf(a, size, Object[].class); }}else {
// replace with empty array.elementData = EMPTY_ELEMENTDATA; }}Copy the codeThe add method
// Add a single element
public boolean add(E e) {
/** * 1. Check the length of the array and modify the value * 2. New elements are added to the array */
ensureCapacityInternal(size + 1); // Increments modCount!!
// Add the element to the last available space
elementData[size++] = e;
return true;
}
Copy the code/** * adds the element to the specified index position * 1. Verifies that the subscript meets the current set * 2. */
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// Moves the specified index index and subsequent elements backward
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// Assign the index subscript to the array
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the codeCheck and expand the array before adding:
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// Return the length of the array
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// Check whether the current array is an empty array object
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Compare the default length with the current minimum length and return the maximum length
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// Make sure the array is long. If there is no available length, expand the array
private void ensureExplicitCapacity(int minCapacity) {
// The number of changes is increased by 1
modCount++;
// overflow-conscious code
// Compare the required minimum length with the maximum length of the current array to determine whether the array needs to be expanded
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
// The maximum length of the current array
int oldCapacity = elementData.length;
// The maximum length of the new array is 0.5 times larger than the current array
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
// If the array length exceeds the maximum length that can be created
// Returns the maximum number of arrays that can be created
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// Copy the data from the old array into the newly created array
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
Copy the codeThe remove method
// Remove the labeled element in the array
public E remove(int index) {
// Check whether the current subscript is out of range of the array
rangeCheck(index);
// The number of times the array has been modified increases by 1
modCount++;
// Retrieves the value to be deleted
E oldValue = elementData(index);
// The subscript of the element to be deleted
int numMoved = size - index - 1;
if (numMoved > 0)
// Move the array element after the specified index+1 position to the front of the image
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// Empty the last element of the array to facilitate JVM recycling
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
// Deletes the specified element
public boolean remove(Object o) {
if (o == null) {
// If the element is empty, iterate over the number group and delete the empty element
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true; }}else {
// Iterate through the array to delete the specified element
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true; }}return false;
}
// The logic to remove elements from an array
private void fastRemove(int index) {
// The number of times the array has been modified increases by 1
modCount++;
// The subscript of the element to be deleted
int numMoved = size - index - 1;
if (numMoved > 0)
// Move the array element after the specified index+1 position to the front of the image
System.arraycopy(elementData, index+1, elementData, index,numMoved);
// Empty the last element of the array to facilitate JVM recycling
elementData[--size] = null; // clear to let GC do its work
}
Copy the codeLinkedList
attribute
// List length
transient int size = 0;
/ / the first node
transient Node<E> first;
/ / end nodes
transient Node<E> last;
AbstractArrayList = AbstractArrayList */
protected transient int modCount = 0;
Copy the codeInitialize the
// Create a linked list with no arguments
public LinkedList(a) {}
// A collection object with parameters
public LinkedList(Collection<? extends E> c) {
this(a); addAll(c); }Copy the code// addAll method to add collection data to the linked list
// Add one by one
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/** * add the collection to the list **@paramIndex Position of the node to be inserted *@paramC Set data to be inserted */
public boolean addAll(int index, Collection<? extends E> c) {
// Check whether the specified node position is in the linked list
checkPositionIndex(index);
// The collection to be inserted is converted to an array object
Object[] a = c.toArray();
// The length of the array to be inserted
int numNew = a.length;
if (numNew == 0)
return false;
// Temporary node, the last node before pre, succ current node
Node<E> pred, succ;
// Insert node position is the tail node
if (index == size) {
succ = null;
pred = last;
} else {
// Insert the node into the middle part of the node
succ = node(index);
pred = succ.prev;
}
// iterate over the insert node
for (Object o : a) {
@SuppressWarnings("unchecked")
E e = (E) o;
// Create a node
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
// A new node is inserted, and the pointer moves backwards
pred = newNode;
}
// Connect the disconnected list to the inserted node
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
// Change the length of the list
size += numNew;
// Modify the number of set changes
modCount++;
return true;
}
Copy the codeThe add method
/ / new
public boolean add(E e) {
linkLast(e);
return true;
}
// Use the tail insertion method to add
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
// Insert nodes at the head of the list
public void addFirst(E e) {
linkFirst(e);
}
// Insert a node with a header
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
Copy the codeThe remove method
Empty parameter delete: remove()
Data of the first node of the node to be deleted
// Delete node elements
public E remove(a) {
return removeFirst();
}
// Delete the first node element
public E removeFirst(a) {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
Copy the codeRemove the first element: removeFirst()
public E removeFirst(a) {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
Copy the codeThe first node breaks the chain
// Disconnect the first node from the list
private E unlinkFirst(Node<E> f) {
// assert f == first && f ! = null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
Copy the codeRemove (Object o)
// Remove the specified element from the list
public boolean remove(Object o) {
// Whether the element to be deleted is empty
if (o == null) {
// Iterate from the first node
for(Node<E> x = first; x ! =null; x = x.next) {
// Check whether the element is to be deleted
if (x.item == null) {
// Delete the link
// For details, see the chain breaking operation
unlink(x);
return true; }}}else {
// The element to be deleted is not empty
for(Node<E> x = first; x ! =null; x = x.next) {
// Check whether the element is to be deleted
if (o.equals(x.item)) {
// Delete the link
// For details, see the chain breaking operation
unlink(x);
return true; }}}return false;
}
Copy the codeRemove (int index)
public E remove(int index) {
// Verify that the specified location is in the list
checkElementIndex(index);
// Delete the link
// For details, see the chain breaking operation
return unlink(node(index));
}
private void checkElementIndex(int index) {
if(! isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
Node<E> node(int index) {
// assert isElementIndex(index);
// Determine whether the current position is in the first half or the second half
// Walk through the list to find elements
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
returnx; }}Copy the codeBreak the chain operation
// Break the chain to remove elements
// the x node is not empty
E unlink(Node<E> x) {
// assert x ! = null;
// Current node value
final E element = x.item;
// The next node of the current node
final Node<E> next = x.next;
// The last node of the current node
final Node<E> prev = x.prev;
// If the last node of the current node is empty, the current node is the first node
if (prev == null) {
// Set the next node to the first node
first = next;
} else {
// Set the next pointer to the next node of the current node
// (graphic: wechat image _20210316145013.png)
prev.next = next;
x.prev = null;
}
// If the next node of the current node is empty, the current node is the last node
if (next == null) {
// Set the last node to the tail node
last = prev;
} else {
// Add the current node's
// image :(wechat image _2021031614501.png)
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
Copy the codeRemove endpoints: removeLast()
public E removeLast(a) {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
// The end node breaks the chain
private E unlinkLast(Node<E> l) {
// assert l == last && l ! = null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
Copy the codeRemoveFirstOccurrence (Object O)
public boolean removeFirstOccurrence(Object o) {
// Call the delete method
return remove(o);
}
Copy the codeMap
HashMap
attribute
/ / = = = = = = = = = = = = = = = = = = = = default configuration = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
/* The default initial capacity - MUST be a power of two. */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/** * maximum length, * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two < = 1 < < 30. * /
static final int MAXIMUM_CAPACITY = 1 << 30;
/* The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75 f;
* The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */
static final int TREEIFY_THRESHOLD = 8;
/** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */
static final int UNTREEIFY_THRESHOLD = 6;
/** * The minimum size of the array when the list is converted to a red-black tree * Tree operations will not exist * The smallest table capacity for which bins may be treeified. * (Otherwise The table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */
static final int MIN_TREEIFY_CAPACITY = 64;
/* ---------------- Fields -------------- */
/** * array, initialized at first use, Allocated tokens * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */
transient Node<K,V>[] table;
/** * Holds cached entrySet(). Note that AbstractMap fields are used * for keySet() and values(). */
transient Set<Map.Entry<K,V>> entrySet;
/** * The number of key-value mappings contained in this map. */
transient int size;
/** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). */
transient int modCount;
/** * The next size value at which to resize (capacity * load factor). **@serial* /
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
/** * The load factor for The hash table. **@serial* /
final float loadFactor;
Copy the codeDefined data structures
Node
static class Node<K.V> implements Map.Entry<K.V> {
// Hash value of the node
final int hash;
// The key value in the key-value pair
final K key;
// The value of the key-value pair
V value;
// Pointer to the next node
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
/ /... Contains get, set, hashCode, and toString methods
}
Copy the codeTreeNode
static final class TreeNode<K.V> extends LinkedHashMap.Entry<K.V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/ /... Methods in nodes
}
// LinkedHashMap.Entry
static class Entry<K.V> extends HashMap.Node<K.V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next); }}Copy the codeInitialize the
// An empty parameter construct that specifies the default load factor
public HashMap(a) {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// Specify a constructor for the initialization length
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/** * specifies the initialization length and load factor constructor **@paramInitialCapacity Initialization length *@paramLoadFactor loadFactor */
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
// The argument is a collection constructor
// Default load factor
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/** * Implements Map. PutAll and Map constructor@param m the map
* @paramEvict false when initially constructing this map, else * true (relayed to method afterNodeInsertion). True: uninitialized call */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
// Set is empty
if (table == null) { // pre-size
// Calculate the required map set length
// The underlying table of HashMap will be expanded when entry_count>table_size*load_factory is used.
// To prevent HashMap from expanding, table_size >= entry_count/load_factor is required.
// Size in the formula ((float)s/loadFactor) + 1.0f is computed using float, + 1.0f is computed because ((float)s/loadFactor) is computed using float and is rounded when converted to an integer
// In order to ensure that the final calculated size is large enough not to trigger expansion, + 1.0f operation is performed
float ft = ((float)s / loadFactor) + 1.0 F;
// The required length is compared to the maximum length
int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
// The perturbation function recalculates the required length
threshold = tableSizeFor(t);
}
else if (s > threshold)
// Perform capacity expansion
resize();
// Iterate over the collection to be inserted, saving the element to the new collection
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict); }}}Copy the codePut method
// Save the element
public V put(K key, V value) {
return putVal(hash(key), key, value, false.true);
}
Copy the codePutVal method
/ * * * *@paramHash Hash value of the key in the map *@paramKey Indicates the key value * in the key-value pair@paramValue Value * in a key value pair@paramOnlyIfAbsent (True /false) The current value * is not changed when the value is true@paramEvict false: initial call, true: uninitial call */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
// the TAB object, the data node in p, the length of n, the subscript in I
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// If the array is empty or its length is 0, the array is initialized
n = (tab = resize()).length;
// Check whether the new key has data in the corresponding position
// Whether a hash collision occurs
if ((p = tab[i = (n - 1) & hash]) == null)
// Add the new element to the array
tab[i] = newNode(hash, key, value, null);
else {
// A hash collision occurs
// p is the original data node
Node<K,V> e; K k;
// p.hash == hash The hash value of the original data node is the same as that of the newly stored node
// (k = p.key) == key The key of the original data node is the same as the key address of the newly stored node
// (key ! = null && key.equals(k)) The newly stored node is not null and has the same value as the original node
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
// The key of the newly stored node exists in the map
e = p;
else if (p instanceof TreeNode)
// Check whether it is a tree node
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//
for (int binCount = 0; ; ++binCount) {
// Find the free location to save the node
if ((e = p.next) == null) {
// Create a node
p.next = newNode(hash, key, value, null);
// Check whether the list length is 8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// Lists are converted to red-black trees
treeifyBin(tab, hash);
break;
}
// If the key value of the node is the same as that of the current node, the loop is broken
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break;
// Move the pointer backp = e; }}// Existing nodes in map are not empty
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
If onlyIfAbsent is false or the value of an existing node is null, update the value of the current key
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
returnoldValue; }}// Change the number of changes
++modCount;
// Determine whether the current length needs to be expanded
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeCapacity: the resize ()
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// Get the node array length
int oldCap = (oldTab == null)?0 : oldTab.length;
// Capacity expansion threshold
int oldThr = threshold;
int newCap, newThr = 0;
// Check whether it is the first initialization
if (oldCap > 0) {
// Whether the length of the original node array reaches the maximum length
if (oldCap >= MAXIMUM_CAPACITY) {
// If the length is greater than the maximum, no operation is performed
threshold = Integer.MAX_VALUE;
return oldTab;
}
// Expanded length = original length x 2
// Verify that the new length reaches the maximum length
// Whether the original length is greater than or equal to the default initial length (16)
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// Threshold after expansion = Original threshold x 2
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// The original array length is 0. If the expansion threshold is greater than 0, the threshold is assigned to the initialization length of the node array
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// Map with no arguments, initialized for the first time
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// If the new threshold is 0, the threshold is recalculated
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// The threshold is reassigned
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// Create a new node array
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if(oldTab ! =null) {
// Migrate the original array data, traverse the original node array
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if((e = oldTab[j]) ! =null) {
// Fetch the data from the original array and set the data at the corresponding index position of the original array to NULL
oldTab[j] = null;
if (e.next == null)
// The current node is a separate node, and the pointer to the next node is null
// Recalculate the hash value and store it in the new node array
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// Fetch the tree node
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// The hash value of the node is ampersand to the original length, 0 is the low value, not 0 is the high value
// Divide the new array into two parts according to the original length. The greater part is the high part and the less part is the low part
// Recalculate the linked list in the original array
// Low level list head node, low level list end node
Node<K,V> loHead = null, loTail = null;
// High list head node, high list tail node
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// Low node data processing
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// High node data processing
if (hiTail == null)
hiHead = e;
elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
// Data is migrated to the new node array
if(loTail ! =null) {
loTail.next = null;
newTab[j] = loHead;
}
if(hiTail ! =null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
// Tree node conversion
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
// Low level node
TreeNode<K,V> loHead = null, loTail = null;
// High level node
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// Walk through the tree node, convert the original tree node structure into a linked list structure
for(TreeNode<K,V> e = b, next; e ! =null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
elsehiTail.next = e; hiTail = e; ++hc; }}// Low list nodes are converted to tree nodes
if(loHead ! =null) {
if (lc <= UNTREEIFY_THRESHOLD)
// The TreeNode Node list is converted to the Node list
tab[index] = loHead.untreeify(map);
else {
// List tree operation
tab[index] = loHead;
if(hiHead ! =null) // (else is already treeified)loHead.treeify(tab); }}if(hiHead ! =null) {
if (hc <= UNTREEIFY_THRESHOLD)
// The TreeNode Node list is converted to the Node list
tab[index + bit] = hiHead.untreeify(map);
else {
// List tree operation
tab[index + bit] = hiHead;
if(loHead ! =null) hiHead.treeify(tab); }}}Copy the codeNew tree node: putTreeVal
/ * * * *@paramMap Collection object *@paramTAB node array object *@paramH Hash value of the key *@paramThe key star of the k key-value pair@paramV key value pair value */
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { Class<? > kc =null;
boolean searched = false;
// Get the root node of the treeTreeNode<K,V> root = (parent ! =null)? root() :this;
// Walk through the red black tree
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk;
// Compares the hash value of the newly stored node with the hash value of the current tree node
if ((ph = p.hash) > h)
/ / the left subtree
dir = -1;
else if (ph < h)
/ / right subtree
dir = 1;
else
// If the newly stored node is the same as the current tree node, return the node
if((pk = p.key) == k || (k ! =null && k.equals(pk)))
return p;
else
(kc == null && (kc = comparableClassFor(k)) == null)
// kc is of type k
if ((kc == null && (kc = comparableClassFor(k)) == null)
// Compare the type of pk with the type of k, and then compare k with pk
|| (dir = compareComparables(kc, k, pk)) == 0) {
// The current node is a new node
if(! searched) { TreeNode<K,V> q, ch; searched =true;
if(((ch = p.left) ! =null&& (q = ch.find(h, k, kc)) ! =null) || ((ch = p.right) ! =null&& (q = ch.find(h, k, kc)) ! =null))
return q;
}
// Determine whether the new key is in the left or right subtree
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
// Determine whether to traverse the left or right subtree according to dir
if ((p = (dir <= 0)? p.left : p.right) ==null) {
// The current p node is a leaf node
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if(xpn ! =null)
((TreeNode<K,V>)xpn).prev = x;
// Save the new node to TAB and insert the tree node in balance
moveRootToFront(tab, balanceInsertion(root, x));
return null; }}}// Get the root node
final TreeNode<K,V> root(a) {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
returnr; r = p; }}// Compare k with x
// If x is null or the type of x is different from that of k, 0 is returned; Otherwise return the value of k compared to x
static int compareComparables(Class
kc, Object k, Object x) {
return (x == null|| x.getClass() ! = kc ?0 : ((Comparable)k).compareTo(x));
}
Copy the codeTreeization: treeifyBin
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// The node array is null and the node array length is less than 64; Perform capacity expansion.
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// Get node e from node array
else if ((e = tab[index = (n - 1) & hash]) ! =null) {
// first node of the hd tree
TreeNode<K,V> hd = null, tl = null;
// Loop through the list to convert it to a tree node
// The hd is not a tree. It is still a linked list, but each node type in the list is TreeNode
do {
// Convert list E node to tree P node
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
// Record the first node of the tree
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
// Move the pointer back
} while((e = e.next) ! =null);
// Replace the existing list nodes in the node array with tree nodes
if((tab[index] = hd) ! =null)
// Convert to a red black treehd.treeify(tab); }}TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
// Convert to a red-black tree
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x ! =null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
inth = x.hash; Class<? > kc =null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0)? p.left : p.right) ==null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// Insert a new node and rotate it left or right to make sure the tree is red-black
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
Copy the codeThe remove method
Delete by key: remove(Object key)
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null.false.true)) = =null ?
null : e.value;
}
Copy the codeRemove (Object key, Object value)
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true.true) != null;
}
Copy the coderemoveNode(int hash, Object key, Object value,boolean matchValue, boolean movable)
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// Node array exists, corresponding key is not null
if((tab = table) ! =null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) ! =null) {
Node<K,V> node = null, e; K k; V v;
// Obtain information about the node to be deleted
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
node = p;
else if((e = p.next) ! =null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while((e = e.next) ! =null); }}// Delete the node
if(node ! =null&& (! matchValue || (v = node.value) == value || (value ! =null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
returnnode; }}return null;
}
Copy the codeRemoveTreeNode method
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null)
tab[index] = first = succ;
else
pred.next = succ;
if(succ ! =null)
succ.prev = pred;
if (first == null)
return;
if(root.parent ! =null)
root = root.root();
// The root is null
// movable is true and (root right node is empty or left node is empty or left node is left node is empty)
if (root == null
|| (movable && (root.right == null || (rl = root.left) == null || rl.left == null))) {
// Remove the tree operation
tab[index] = first.untreeify(map); // too small
return;
}
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if(pl ! =null&& pr ! =null) {
TreeNode<K,V> s = pr, sl;
while((sl = s.left) ! =null) // find successor
s = sl;
boolean c = s.red;
s.red = p.red;
p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
if((p.parent = sp) ! =null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if((s.right = pr) ! =null)
pr.parent = s;
}
p.left = null;
if((p.right = sr) ! =null)
sr.parent = p;
if((s.left = pl) ! =null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if(sr ! =null)
replacement = sr;
else
replacement = p;
}
else if(pl ! =null)
replacement = pl;
else if(pr ! =null)
replacement = pr;
else
replacement = p;
if(replacement ! = p) { TreeNode<K,V> pp = replacement.parent = p.parent;if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
TreeNode<K,V> pp = p.parent;
p.parent = null;
if(pp ! =null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null; }}if (movable)
moveRootToFront(tab, r);
}
Copy the codeDisturbance function: tableSizeFor
// Compute a value greater than the current value to the lowest power of 2
// graphic: perturbation function.png
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Copy the codeLinkedHashMap
attribute
// Two-way list header
transient LinkedHashMap.Entry<K,V> head;
// The end of the bidirectional list
transient LinkedHashMap.Entry<K,V> tail;
// The hash map of this link is iteratively sorted:
// true for access order,
// false is used for insertion order.
final boolean accessOrder;
Copy the codeDefined data structures
Entry
// A custom structure type that inherits the Node type in HashM
static class Entry<K.V> extends HashMap.Node<K.V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next); }}Copy the codeInitialize the
// No arguments
public LinkedHashMap(a) {
super(a); accessOrder =false;
}
// Initialize the length
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
// Initialize the length and load factor
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
// Initialize the length, load factor, and type of iteration sort
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
// The parameter is the initialization method of the collection
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(a); accessOrder =false;
putMapEntries(m, false);
}
Copy the codePut method and remove method
The same as the put and remove (Object key) methods of HashMap
// Inherit the HashMap put method and remove (Object key) method,
// Override the newNode method,
// the newTreeNode method
// afterNodeAccess,
// afterNodeInsertion method
// visting deremoval,
/ / replacementTreeNode method
Copy the codeNewNode and newTreeNode
// Create a node
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
// newTreeNode in putTreeVal
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
linkNodeLast(p);
return p;
}
// Save the new node to the bidirectional linked list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else{ p.before = last; last.after = p; }}Copy the codeafterNodeAccess
// Move the current node to the end of the list
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if(accessOrder && (last = tail) ! = e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.after =null;
if (b == null)
head = a;
else
b.after = a;
if(a ! =null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else{ p.before = last; last.after = p; } tail = p; ++modCount; }}Copy the codeafterNodeInsertion
// Delete the header
// This should be an extended operation
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// Evict is false when initialized; True is called when new
// Determine whether to remove the header
if(evict && (first = head) ! =null && removeEldestEntry(first)) {
K key = first.key;
// Delete a node
removeNode(hash(key), key, null.false.true); }}protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
Copy the codeafterNodeRemoval
// Delete a node from the bidirectional list
// Delete the deleted nodes in the extra maintained linked list
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
Copy the codereplacementTreeNode
// Replace with a tree node
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
}
// Replace SRC with DST
private void transferLinks(LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst) {
LinkedHashMap.Entry<K,V> b = dst.before = src.before;
LinkedHashMap.Entry<K,V> a = dst.after = src.after;
if (b == null)
head = dst;
else
b.after = dst;
if (a == null)
tail = dst;
else
a.before = dst;
}
Copy the codetraverse
LinkedHashMap maintains an additional two-way linked list to retrieve stored element data in an orderly fashion as it traverses.
Set
HashSet
attribute
// Set set holds the structural type of data
private transient HashMap<E,Object> map;
// The value of key-value in the map object
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
Copy the codeInitialize the
// No arguments
public HashSet(a) {
map = new HashMap<>();
}
// Specify the initialization length
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
// Specify the initialization length and load factor
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
// specify the initialization length and loadFactor and Boolean values to distinguish the HashSet(int initialCapacity, float loadFactor) constructor
// (This package private constructor is only used by LinkedHashSet.)
// The sequence method creates a LinkedHashMap object to ensure orderliness
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
// The argument is a collection constructor
public HashSet(Collection<? extends E> c) {
// Determine the maximum length of initialization according to the length of the collection
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1.16));
// Save the collection to map
addAll(c);
}
Copy the codeThe add method
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
Copy the codeThe remove method
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
Copy the codeLinkedHashSet
Initialize the
Int initialCapacity (int initialCapacity, float loadFactor, Boolean dummy);
// Create a LinkedHashMap object to ensure orderliness
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f.true);
}
public LinkedHashSet(a) {
super(16..75f.true);
}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f.true);
addAll(c);
}
Copy the code