preface
HashMap is one of the most frequently used mapping classes in development, providing many convenient operations. Why is it so popular? The following article will answer for you.
The principle of
HashMap is encapsulated based on a hash table of data structures. The underlying implementation is data + linked list/red-black tree. The k-V pair is stored. According to a specified hash function, the key is hashed to determine the storage location of the value, and then the corresponding value can be quickly found according to the key.
Advantages and Disadvantages
Advantage:
- Quick lookup by key, time O(1)
- Automatic expansion
Disadvantage:
- Thread insecurity, data loss in high concurrency scenarios, and circular linked lists (JDK1.7)
Applicable scenario
- Thread-safe case as a cache container.
- As a judgment container for the existence of data.
The key way to
Put method
The Put method in JDK1.8 is as follows:
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// If the list is null, or the length of the list is now 0
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// If the Hash slot is null, create a list node object.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
/ / Hash conflict
Node<K,V> e; K k;
// If the keys in the Hash slots are the same, replace the values.
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
// The Key value is not the same and is a tree node object, tree insertion operation.
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// Insert a new node into the list.
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// Check whether the current list length is greater than or equal to 8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
If the Hash bucket size is smaller than 64, expand the Hash bucket
treeifyBin(tab, hash);
break;
}
// Find the corresponding key value and replace it
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}// Overwrite the old value and return the new value
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 current Hash bucket size is greater than the capacity expansion threshold. Then expand the capacity.
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeParameter analysis:
- Hash is the hash value of the key. The key and hashCode() are internally rehash in the HashMap to ensure uniform hash values and reduce hash collisions.
- Key Indicates the key value saved
- Value Value saved
Put procedure: described in source code
The resize function
The resize method in JDK1.8 is as follows:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null)?0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
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
newCap = oldThr;
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;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if(oldTab ! =null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if((e = oldTab[j]) ! =null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((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;
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 codeThe key steps are as follows: 1. Determine the length of the new Hash bucket. 2. After determining the length, create a Hash bucket to transfer data.
The GET method
/**
* 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 &&
// Use the hash function to locate the hash bucket.
(first = tab[(n - 1) & hash]) ! =null) {
// Determine if the first element on the Hash bucket is the desired element
if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
// Hash subsequent element lookups
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))))
// Find the corresponding element, return
return e;
} while((e = e.next) ! =null); }}// No corresponding element is found, return null.
return null;
}
Copy the codeThe remove method
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
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;
if((tab = table) ! =null && (n = tab.length) > 0 &&
// Determine the position according to the hash function
(p = tab[index = (n - 1) & hash]) ! =null) {
Node<K,V> node = null, e; K k; V v;
// Find the corresponding node object
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); }}// Execute the delete method
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 codeThe hash function
The source code is as follows:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the code1. Since the Hash table internally uses a power of 2 as the capacity and a lower mask when reduced by 1, if the Hash code of the object changes only at the higher level, the conflict will always occur. A typical example is a Float set that holds consecutive integers in a table. Examples are as follows:
Public class hashMaplowBithcollide {public static void main(String[] args) {Float a = new Float(0.0f); for (int i=0; i<10; ++ I) {a += 1.0f; System.out.println(Integer.toBinaryString(a.hashCode())); }}}Copy the codeThe print result is as follows:
111111100000000000000000000000
1000000000000000000000000000000
1000000010000000000000000000000
1000000100000000000000000000000
1000000101000000000000000000000
1000000110000000000000000000000
1000000111000000000000000000000
1000001000000000000000000000000
1000001000100000000000000000000
1000001001000000000000000000000
Copy the codeThe impact of propagating high to low is therefore a trade-off between speed, practicality, and the quality of bit-spreading. 2. Because key.hashcode () calls the hash function of the key type, it returns an int hash value. Int values range from **-2147483648 to 2147483647**, which adds up to about 4 billion mapping space. Due to the limited scope of the table, it is impossible to store an array with a length of 4 billion in memory. If hash code is simply used for ampersand operation with the low-order mask, the high-order effect will never be used
Existing implementations
HashTable: HashTable is a legacy class of the JDK. HashMap implements almost the same functionality as HashTable, but it has performance problems, so it is recommended to use HashMap.
ConcurrentHashMap: The HashMap thread is not safe, so if you want to use a Map in concurrent conditions, use ConcurrentHashMap.