A, a HashMap
A Map is an unordered collection of elements stored in key-value pairs. The keys cannot be repeated and the values are not required. The values of duplicate keys overwrite the previous values.
1. What is the data structure
In jdk1.7, arrays + linked lists
In JDk1.8, array + linked list + red-black tree
2. Core attributes
- Basic attributes
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // Initial capacity, default is 16
static final int MAXIMUM_CAPACITY = 1 << 30; // Maximum capacity
static final float DEFAULT_LOAD_FACTOR = 0.75 f; // Load factor 0.75, capacity expansion trigger
static final int TREEIFY_THRESHOLD = 8; // The list is converted into a red-black tree
static final int UNTREEIFY_THRESHOLD = 6; // one of the conditions for a red-black tree to become a linked list
static final int MIN_TREEIFY_CAPACITY = 64; // Become a red-black tree with a minimum capacity of 64
transient Node<K,V>[] table; // An array of nodes to store data
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
Copy the code- A constructor
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);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(a) {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
Copy the code- The inner class
// Node inner class
static class Node<K.V> implements Map.Entry<K.V> {
final int hash; / / hash value
final K key;
V value;
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;
}
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;
}
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/ / EntrySet inner classes
final class EntrySet extends AbstractSet<Map.Entry<K.V>> {
public final int size(a) { return size; }
public final void clear(a) { HashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
if(! (oinstanceof Map.Entry))
return false; Map.Entry<? ,? > e = (Map.Entry<? ,? >) o; Object key = e.getKey(); Node<K,V> candidate = getNode(hash(key), key);returncandidate ! =null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceofMap.Entry) { Map.Entry<? ,? > e = (Map.Entry<? ,? >) o; Object key = e.getKey(); Object value = e.getValue();return removeNode(hash(key), key, value, true.true) != null;
}
return false;
}
public final Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(HashMap.this.0, -1.0.0);
}
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0&& (tab = table) ! =null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for(Node<K,V> e = tab[i]; e ! =null; e = e.next)
action.accept(e);
}
if(modCount ! = mc)throw newConcurrentModificationException(); }}}Copy the code3. Core methods
// Use the object hashCode method to generate the hash value when the key is not null and shift it 16 bits right
static final int hash(Object key) {
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
// Pass in the given capacity value and change it to the adjacent 2 to the n
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;
}
public int size(a) {
return size;
}
public boolean isEmpty(a) {
return size == 0;
}
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if((tab = table) ! =null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) ! =null) {
if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
if((e = first.next) ! =null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
return e;
} while((e = e.next) ! =null); }}return null;
}
public boolean containsKey(Object key) {
returngetNode(hash(key), key) ! =null;
}
Copy the codeThe put method:
public V put(K key, V value) {
return putVal(hash(key), key, value, false.true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//1. Determine whether the array needs to be initialized
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2. Check whether the node at the hash location of the passed key is empty. If so, create a node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//3. There is already a node at the location of the passed key
else {
//4. If the passed key is equal to the current node key, overwrite it.
Node<K,V> e; K k;
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
// 5. If p is a tree node, call the related method to add
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//6. Node P is the node in the linked list
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}// The same key exists, then the value needs to be overwritten
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// If the capacity exceeds the threshold, expand the capacity
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
// Get a reference to the old array
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null)?0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// When the key capacity has reached the maximum
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;// Return the maximum value of the array directly
}
// It does not exceed the maximum value
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// Initialize the capacity assignment threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; // Initialize the default value
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// New threshold ==0 resize
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// Reassign the threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// Create a new array
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if(oldTab ! =null) {
// Transfer the data from each bucket to the new bucket
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// Assign e
if((e = oldTab[j]) ! =null) {
oldTab[j] = null;// Clear the index of the old array
if (e.next == null)
// regenerate the subscript and put the data into the corresponding array of subscripts
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)// Assign a value to the red-black tree
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
/ / the original indexes
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
// Put the original index into the bucket
if(loTail ! =null) {
loTail.next = null;
newTab[j] = loHead;
}
// Add index + oldCap to bucket
if(hiTail ! =null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Copy the codeThe get method:
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if((tab = table) ! =null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) ! =null) {
if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
if((e = first.next) ! =null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
return e;
} while((e = e.next) ! =null); }}return null;
}
Copy the code4. Why is the capacity 2 to the n?
Hash %length==hash&(leng-1) if length is 2 to the n; .” And ** uses the binary bit operation &, which is more efficient than %, which explains why the length of a HashMap is a power of 2.
5. Why are the thresholds for treification and linkage different?
First of all, red-black tree advantages: increase, delete, modify and check efficiency. High linked list data volume will improve the row performance if it is operated by red-black tree.
However, linked list conversion to red-black tree is a time-consuming operation that requires the traversal of linked list and insertion of red-black tree. It is reasonable that the performance after conversion should be greater than the cost. The threshold setting of 8 should be the value obtained by the development project after balancing the time and space complexity through strict system testing.