Reference content:
Snailclimb. Gitee. IO/javaguide / #…
Blog.csdn.net/zhouxcwork/…
HashMap
HashMap is mainly used to store key-value pairs. Based on hash table, HashMap interface implementation is one of the commonly used Java collections.
Note:
Before JDK1.8, HashMap consists of array + linked list, that is, linked list Hash, array as the main body, linked list is mainly used to solve Hash conflicts.
After JDK1.8, a red-black tree is added to the composition of HashMap. If the following two conditions are met, the linked list structure will be transformed into a red-black tree to speed up the search.
There are two conditions for the linked list to become a red-black tree:
- List length greater than threshold (default 8)
- The length of the HashMap array exceeds 64
Analyze data structure with source code
HashMap uses a hash table to store key-value pairs. It creates a static inner class that inherits Map.Entry. Each Node (Entry) object represents a key-value pair stored in the hash table.
The HashMap data structure is as follows:
static class Node<K.V> implements Map.Entry<K.V> {
// Hash value of key
final int hash;
/ / the key object
final K key;
/ / value object
V value;
Null indicates that the current object is at the bottom of the listNode<K,V> next; . }Copy the codeHashMap perturbation function (hash method) :
static final int hash(Object key) {
int h;
// key.hashcode () is the hash value of key
// ^ Bitwise xor >>> unsigned right shift
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the codeHashMap 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;
// The table is not initialized or has a length of 0
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// Determine the size of the array where the element is stored.
if ((p = tab[i = (n - 1) & hash]) == null)
// There is no element in the current position
// Insert into array (bucket)!!
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
// The insert element has the same hash key as the element at the target position
e = p;
else if (p instanceof TreeNode)
// If the key is not inserted as a tree node (red-black tree), the node is directly inserted
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// Iterate over inserts for linked list nodes
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// Insert a new node at the end of the list
p.next = newNode(hash, key, value, null);
// The length is greater than the threshold to call the list to red black tree
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// Check whether the key value of the node in the list is equal to the key value of the inserted element
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}// Overwrite the node where the key and hash values are equal to those of the inserted element
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
// Callback after access
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// Determine whether to expand the capacity
if (++size > threshold)
resize();
// Callback after insertion
afterNodeInsertion(evict);
return null;
}
Copy the codeLinked list to red black tree:
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
The length of the HashMap array exceeds 64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) ! =null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while((e = e.next) ! =null);
if((tab[index] = hd) ! =null) hd.treeify(tab); }}Copy the codeRead more about HashMap
Attributes of a HashMap:
public class HashMap<K.V> extends AbstractMap<K.V> implements Map<K.V>, Cloneable.Serializable {
/ / serial number
private static final long serialVersionUID = 362498820763181265L;
// The default initial capacity is 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// Maximum capacity is 2 ^ 30 (capacity size must be 2 ^ n)
static final int MAXIMUM_CAPACITY = 1 << 30;
// The default fill factor
static final float DEFAULT_LOAD_FACTOR = 0.75 f;
// When the number of nodes on the bucket is greater than this value, it becomes a red-black tree
static final int TREEIFY_THRESHOLD = 8;
// When the number of nodes on the bucket is less than this value, the tree lists the links
static final int UNTREEIFY_THRESHOLD = 6;
// The minimum size of the table corresponding to the red-black tree in the bucket
static final int MIN_TREEIFY_CAPACITY = 64;
// An array that stores elements, always a power of 2
transient Node<k,v>[] table;
// Store a set of specific elements
transient Set<map.entry<k,v>> entrySet;
// The number of elements to store. Note that this does not equal the length of the array.
transient int size;
// Expand and change the map counter each time
transient int modCount;
// Threshold When the actual size (capacity x fill factor) exceeds the threshold, the system expands the capacity
int threshold;
// Load factor
final float loadFactor;
}
Copy the codeLoadFactor loadFactor
LoadFactor is a loadFactor that controls how much data an array stores. As the loadFactor approaches 1, the more dense the array is, and as the loadFactor approaches 1, the more sparse the array is. Too large a loadFactor will result in inefficient element search, while too small will result in low array utilization and scattered data storage. The default value of loadFactor is 0.75F, which is officially a good threshold.
When will HashMap be expanded?
When Size>=threshold is used for capacity expansion, threshold = capacity * loadFactor indicates that the critical value is array length * loadFactor. For example, the default HashMap array length is 16 and the load factor is 0.75. If the array length is greater than or equal to 12, you need to expand the array size.
Differences between HashTable and HashMap
- In a HashMap, both K and V are allowed to be null, but the key is not required to be null repeatedly. In the HashTable, k-v cannot be null.
- HashMap uses array + linked list (red-black tree) data structure, HashTable uses array + linked list data structure;
- When a Hash conflict occurs, if the number of linked list nodes is less than 8, HashMap adds the new element to the end of the list, and HashTable adds it to the top.
- The maximum capacity of a HashMap must be 2 to the power of n. The capacity of a HashTable can be any positive integer.
- The addressing mode of HashMap is bitwise operation and bitwise and, and HashTable adopts remainder calculation.
- HashMap cannot guarantee thread safety. The get/ PUT method of HashTable adopts synchronized keyword for method synchronization.
- The default capacity of HashMap and HashTable is 16 and 11 respectively.
ConcurrentHashMap
ConcurrentHashMap data structure is array + linked list (red-black tree), lock granularity is each array element (Node) lock.
Differences between HashTable and ConcurrentHashMap
-
Any operation on the **Hashtable locks the entire table and is blocked. ** The advantage is that it can always get the most real-time update. For example, thread A calls putAll to write A large amount of data, during which thread B calls GET, thread B will be blocked until thread A completes putAll, so thread B must get the complete data written by thread A. The downside is that all calls are queued, which is inefficient.
-
ConcurrentHashMap is designed to be non-blocking. Partial data is partially locked during updates, but not the entire table is locked. Synchronous read operations are completely non-blocking. The advantages are high efficiency under the premise of ensuring reasonable synchronization. The downside is that the read operation is not strictly guaranteed to reflect the most recent update. For example, thread A calls putAll to write A large amount of data, while thread B calls GET, so only part of the data that has been successfully inserted so far can be gotten.
Conclusion: ConcurrentHashMap cannot completely replace HashTable. HashTable is a strong consistency and ConcurrentHashTable is a weak consistency. ConcurrentHashMap is suitable for performance-oriented scenarios where most threads only perform INSERT/DELETE operations and require less consistency in reading data.
Note: It is recommended to add the flow chart of HashMap put method to deepen the impression