Hashmap is an array of nodes. The array size is a power of 2, starting with 16:
/** * The default initial capacity - MUST be a power of two. */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
Copy the codeIf the construction argument passed is not a power of 2, the following method takes the next power of 2 of that number. Making every binary bit a 1 by unsigned right sum or operation,
/** * Returns a power of two size for the given target capacity. */
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 codeAdvantages of array powers of length 2:
- 1. Hash is efficient. In the put phase, the method to determine which bucket the node is placed in the array is table[(n-1) &hash(key)], where n is a power of 2 and all binary bits of n-1 are 1. In this way, the array index corresponding to the hash value can be obtained more efficiently by the hash value bit and operation.
- 2. High efficiency in resize. Resize (hashmap.resize (),) in the resize phase, the array size is increased by 1, the hash value is 0, so the node does not need to move. The rehash value changes only when the highest hash bit is 1, and it increases by 2 to the n-1 power. This makes capacity expansion more efficient.
/** * Computes key.hashCode() and spreads (XORs) higher bits of hash * to lower. Because the table uses power-of-two masking, sets of * hashes that vary only in bits above the current mask will * always collide. (Among known examples are sets of Float keys * holding consecutive whole numbers in small tables.) So we * apply a transform that spreads the impact of higher bits * downward. There is a tradeoff between speed, utility, and * quality of bit-spreading. Because many common sets of hashes * are already reasonably distributed (so don't benefit from * spreading), and because we use trees to handle large sets of * collisions in bins, we just XOR some shifted bits in the * cheapest possible way to reduce systematic lossage, as well as * to incorporate impact of the highest bits that would otherwise * never be used in index calculations because of table bounds. */
static final int hash(Object key) {
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the codeThe hash(Object key) method is to hash the key, which is better than using hashcode directly, because h is unsigned 16 bits to the right to get high,
V Get (Object key) method
Obtain the value by using getNode(hash(key), key). Code logic:
final Node<K,V> getNode(int hash, Object key) {
// array TAB, first node, array size n,
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// There are three conditions: && has short circuit function, pay attention to the order.
//1. Array is not empty, 2. Array length is greater than zero, 3, node is not empty.
if((tab = table) ! =null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) ! =null) {
// Check whether the hash value is the same &&key reference is the same or equals.(k)
if(first.hash == hash && ((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
if((e = first.next) ! =null) {
// Determine a red-black tree or linked list
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 codeThe map key can be NULL
If the key is null, hash(null)=0 is fixed at the 0 subscript of the array. Null = = null a true.
put(key,value)
Use the following method:
/**
* 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 array is empty, initialize the array with resize ().
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// If there is no node object in the array, create a new one; Otherwise, the new Node object inserts the Node.
// Insert the bucket into two cases, one is red black tree. One is linked lists.
if ((p = tab[i = (n - 1) & hash]) == null)
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))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
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; }}if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeThe important methods used in the above code are resize, treeifyBin. Here is the source code:
/**
* 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() {
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 codeThere is also a treeifyBin method that converts the single-necklace list inside the bucket to a bidirectional list, and then to a red-black tree. On the concrete implementation of red black tree, this article will not be analyzed.
The remove method
RemoveNode: final Node<K,V> removeNode: final Node<K,V> removeNode: final Node<K,V> removeNode: final Node<K,V> RemoveNode source code mainly considers single node, linked list and tree three cases, the main logic is (each step should consider three cases) :
- 1, find the node key,
- 2, and then delete this node.
Keys () values () and entrySet () both provide a window for the hashMap.
computeIfAbsent
Java8 before. Getting a value from a map based on a key might have the following operation: Object key = map.get(“key”); if (key == null) { key = new Object(); map.put(“key”, key); }
After java8. The above operation can be simplified to a single line. If the value corresponding to key is empty, the return value of the second parameter is saved and returned
Object key2 = map.computeIfAbsent("key", k -> new Object());
Copy the code