Hash table structure
The hash table structure is an array + linked list structure
This article is shared with friends who need to brush the questions in the interview, I have specially arranged it. The technology inside is not clear by a few words. The answers to many questions are actually very simple, but the thinking and logic behind them are not simple. If you want to learn Java engineering, high performance and distributed, simple. Performance tuning, Spring, MyBatis, Netty source code, data structure, JVM, multithreading and so on, due to the space is limited, the following only show a small part of the interview questions, there is a need for a complete version of the friend can click a link jump to get,Link: Stamp here free download, get code: nuggets
What is a hash?
The basic principle of Hash, also known as Hash, is to convert input of arbitrary length into output of fixed length through the Hash algorithm
The rules of this mapping are the corresponding hash algorithm, and the binary of the original data is the hash value
Different data it corresponds to the hash code value is not the same
The hashing algorithm is very efficient
3. Explain the principle of HashMap
3.1 Inheritance System Diagram
3.2Node data structure analysis
static class Node<K.V> implements Map.Entry<K.V> {
final inthash; Compute the hash valuefinal K key;
V value;
Node<K,V> next;
}
interface Entry<K.V> {
K getKey(a);
V getValue(a);
V setValue(V value);
Copy the code3.3 Underlying Storage Structure
When the list length reaches 8, upgrade to red-black tree structure
3.4 Put Data Principle Analysis
First, a key—-value will be put in and a hash value will be calculated according to the key value. After the perturbation, the data will be more hashed to construct a Node object. Finally, a corresponding index will be obtained through the routing algorithm
3.5 What is a Hash collision?
When the last four digits of the hash value corresponding to the data key passed in are the same as the previous one, the calculated index will be the same, and collisions will occur, causing data to become linked lists
- Such as:
(16-1) — — — — — — — > 0000 0000 0000 1111 “zhang SAN” — — — — — — — > 0100 1101 0001 1011 “bill” — — — — — — — — > 1011, 1010, 0010, 1011
At this point, it will be found that the hash values calculated by John and John are converted to the last four digits of binary, resulting in the calculation of the same index
3.6 Why red-black trees are introduced in JDK8?
Hash collisions, you’re going to chain, you’re going to be less efficient
The introduction of red-black tree will improve the search efficiency
3.7 Capacity Expansion Mechanism Each capacity expansion is twice the initial capacity
Eg: 16 — — — — — — — > 32
To prevent excessive data from leading to linear query and low efficiency, capacity expansion increases the number of buckets and reduces the data on each chain, resulting in faster query
Four, hand tear source code
1. Analysis of core attributes of HashMap
Tree thresholds —–8 and 64
Load factor 0.75
Threshold Capacity expansion threshold. When the number of hash table elements exceeds the threshold, capacity expansion is triggered
LoadFactory Load factor 0.75, to calculate the threshold eg: 16*0.75
Size ——- Number of elements in the current hash table
ModCount ——– Number of current hash table structure changes
2. Analysis of construction methods
public HashMap(int initialCapacity, float loadFactor) {
// An error occurs when the check is less than 0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// Capacity is greater than the maximum value
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// Load factor cannot be less than or equal to 0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
/ / tableSizeFor method
this.threshold = tableSizeFor(initialCapacity); } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --// Pass in an initial capacity with a default load factor of 0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR); } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --// No parameter, default load factor 0.75
public HashMap(a) {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --// Pass in a map object
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
Copy the code3. Put method analysis
public V put(K key, V value) {
// Returns the putVal method to rehash the key
return putVal(hash(key), key, value, false.true); } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --static final int hash(Object key) {
// Add the hash value of the key to the hash
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16); } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)
{
// TAB: references the hash table of the current HashMap
//p: represents the element of the current hash table
//n: indicates the length of the hash array
// I: indicates the result of route addressing
Node<K,V>[] tab; Node<K,V> p; int n, i;
---------------------------------------------------------- // Delay initialization logic to initialize the hash table size of a HashMap object when putVal is called for the first time
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
----------------------------------------------------------
// Find the bucket bit and it happens to be null, then encapsulate k-v as node object and put it in
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
----------------------------------------------------------
else {
//e: if not null, find a key object that is the same as the key-val to be inserted
//k: temporary key
Node<K,V> e; K k;
// Represents the element in the bucket, which is the same as the element key you are currently inserting, and will be replaced later
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
----------------------------------------------------------
/ / tree
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
----------------------------------------------------------
else {
// The first element of the list is not the same as the key we want to insert
for (int binCount = 0; ; ++binCount) {
// If the key is inserted in the list, the node object is not found
// add to the end of the list
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// Indicates that the current list length reaches the tree standard
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// Replace the key with break
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --// if e does not equal null, it is found that the element you inserted is exactly the same
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
returnoldValue; }} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --//modCount: indicates the number of times the hash table structure has been modified. Replacing elements does not count
++modCount;
// Insert a new element, and the size increases automatically. If the size increases to the threshold, the capacity expansion is triggered
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the code4. Resize () method analysis
// In order to solve the hash conflict, affect the hash efficiency, so there is a capacity expansion mechanism
----------------------------------------------------------
final Node<K,V>[] resize() {
//oldTab: references the hash table before capacity expansion
//oldCap: indicates the array length of the table before capacity expansion
//oldThr: indicates the threshold before capacity expansion
//newCap, newThr: specifies the size of the array after the expansion and the threshold for the next expansion
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null)?0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
----------------------------------------------------------
// If the condition is true, the hashMap hash table has been initialized
if (oldCap > 0) {
// The size of the table array before capacity expansion reaches the maximum threshold
// Set the capacity expansion condition to the maximum value int
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
returnoldTab; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --//oldCAP moves one bit to the left to double the value, and assigns the value to newcap, which is less than the maximum value limit and the threshold before expansion >=16
// In this case, the next capacity expansion threshold is twice the current threshold
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --//oldCap == 0, indicating that the hashMap hash table is null
/ / 1. New HashMap (inttCap loadFactor);
//2.new HashMap(inttCap);
//3.new HashMap(map); The map data
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;// Must be a power of 2
----------------------------------------------------------
/ / oldCap = = 0, oldThr = = 0
//new HashMap();
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
----------------------------------------------------------
---------------------------------------------------------- // Create a longer and larger array
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
Before the expansion of hashMap, the table is not null
if(oldTab ! =null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;// The current node
// Indicates that there is data in the bucket, but whether it is a linked list, a red-black tree, or a single data is uncertain
if((e = oldTab[j]) ! =null) {
// Facilitate collection by JVM GC
oldTab[j] = null;
// The element is a single element, and the current element should be stored in the new array
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// Determine if there is a red-black tree
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// The bucket bit has formed a linked list
else { // preserve order
// List of positions -- the subscript position of the expanded array is the same as that of the current array
Node<K,V> loHead = null, loTail=null;
// The index of the expanded array is the index of the current array + the length of the array before the expansion
Node<K,V> hiHead = null, hiTail=null;
----------------------------------------------------------
Node<K,V> next;
do {
next = e.next;
/ / hash -... 1, 1111
/ / hash -... 0 1111
//0b 10000
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);
//
if(loTail ! =null) {
loTail.next = null;
newTab[j] = loHead;
}
//
if(hiTail ! =null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Copy the code5. The get method
public V get(Object key) {
Node<K,V> e;
return (e = getNode(key)) == null ? null: e.value; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --final Node<K,V> getNode(Object key) {
Node<K,V>[] tab; // TAB: references the hash table of the current hashMap
Node<K,V> first, e;//first: head element in bucket, e: temporary node element
int n, hash; //n: table array length
K k;
---------------------------------------------------------
if((tab = table) ! =null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & (hash = hash(key))]) ! =null) {
// The positioned bucket element is the element we want to get
if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
---------------------------------------------------------- // Indicates that the current bucket level has more than one element, which may be a tree or linked list
if((e = first.next) ! =null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
---------------------------------------------------------- // List
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 code6. Remove method analysis
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null.false.true)) = =null ?
null: e.value; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {
// TAB: references the hash table of the current HashMap
//p: represents the element of the current hash table
//n: indicates the length of the hash array
//index: indicates the result of route addressing
Node<K,V>[] tab; Node<K,V> p; int n, index;
----------------------------------------------------------
if((tab = table) ! =null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) ! =null) {
// The bucket bit of the route contains data. You need to search for and delete the bucket
---------------------------------------------------------- E: the next element of the current node
Node<K,V> node = null, e; K k; V v;
// The element in the current bucket is the element to be deleted
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
node = p;
---------------------------------------------------------- // The current bucket element is a red-black tree
else if((e = p.next) ! =null) {
if (p instanceof TreeNode)
node=((TreeNode<K,V>)p).getTreeNode(hash, key);
---------------------------------------------------------- // The bucket bit is a linked list
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); }} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --// If node is not empty, the data to be deleted is found according to the key
if(node ! =null&& (! matchValue || (v = node.value) == value ||(value ! =null&&value.equals(v)))) {
// The result is a red-black tree
if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// Result is a single element
else if (node == p)
tab[index] = node.next;
// The result is a linked list
else
p.next = node.next;
++modCount;// The number of modifications increases
--size;// The length is reduced
afterNodeRemoval(node);
returnnode; }}return null;
}
Copy the code7. Replace method analysis
@Override
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
if((e = getNode(key)) ! =null&& ((v = e.value) == oldValue || (v ! =null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --@Override
public V replace(K key, V value) {
Node<K,V> e;
if((e = getNode(key)) ! =null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
ll && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --@Override
public V replace(K key, V value) {
Node<K,V> e;
if((e = getNode(key)) ! =null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
Copy the codeThis article is shared with friends who need to brush the questions in the interview, I have specially arranged it. The technology inside is not clear by a few words. The answers to many questions are actually very simple, but the thinking and logic behind them are not simple. If you want to learn Java engineering, high performance and distributed, simple. Performance tuning, Spring, MyBatis, Netty source code, data structure, JVM, multithreading and so on, due to the space is limited, the following only show a small part of the interview questions, there is a need for a complete version of the friend can click a link jump to get,Link: Stamp here free download, get code: nuggets