Comparison of the Java8 and Java7 HashMap source implementations
- 2020-06-01 09:38:10
- OfStack
1. Introduction to the principle of HashMap
This is too old a story to be explained in detail.
1 sentence summary: HashMap is a hash table that stores a key-value pair (key-value) mapping.
2. Source code analysis of HashMap in Java 7
The first is
HashMap
The constructor code block 1, according to the initialization
Capacity
with
loadFactor
(load factor) initialization
HashMap
.
// The code block 1
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;
threshold = initialCapacity;
init();
}
For in the Java7
<key1,value1>
the
put
Method implementation is relatively simple, according to the first
key1
the
key
Value calculation
hash
Value, and then according to this
hash
Values and
Capacity
0
the
Capacity
1
Determine if the
key
Where the
Capacity
3
, if the current location
Capacity
4
Don't for
Capacity
5
In this
Capacity
4
Traverse the chain, if found
hash
Values and
key
If all values are the same, the value will be
Capacity
9
Overwrite, return
loadFactor
0
; If the current location
Capacity
4
for
Capacity
5
The direct
loadFactor
3
.
The code block 2
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
//addEntry The current is checked in the method table If you need resize
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); // The current map In the size If more than threshole Is the threshold value of resize will table the length expand 2 Times.
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
In the Java7
loadFactor
4
Method implementation is relatively simple, will
loadFactor
5
The length of the extension and will
loadFactor
6
In the
Capacity
4
According to the
loadFactor
8
Marks are recalculated
hash
Values and
Capacity
3
Move to the
HashMap
1
.
The code is shown in code block 3,
// The code block 3 --JDK7 In the HashMap.resize() methods
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* The current table the Entry Transfer to the new table In the
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
HashMap performance has two parameters: initial capacity (
HashMap
2
) and load factor (
loadFactor
). The capacity is the number of buckets in the hash table, and the initial capacity is just the capacity of the hash table when it was created. The load factor is a scale that the hash table can reach before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is performed
rehash
Operation (that is, rebuilding the internal data structure) so that the hash table will have about twice the number of buckets.
According to the source code analysis can be seen: HashMap in Java7
entry
Is in accordance with the
Capacity
3
Index store, when encountering hash conflict, use zipper method to resolve the conflict, will conflict
key
and
Capacity
9
Insert into a linked list
list
In the.
However, there is one drawback to this solution, if
key
If all the values are in conflict, HashMap will degenerate into a linked list,
get
The complexity is going to be zero
O(n)
.
In Java8, to optimize the performance in this worst-case scenario, a balance tree is used to store these hash conflicted key-value pairs, so that the performance can be improved to
O(logn)
.
The code block 4 -- JDK8 In the HashMap Middle constant definition
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int TREEIFY_THRESHOLD = 8; // Whether or not to list Converted to tree The threshold
static final int UNTREEIFY_THRESHOLD = 6; // in resize During operation, decide whether or not untreeify The threshold
static final int MIN_TREEIFY_CAPACITY = 64; // Decide whether to convert to tree Minimum capacity
static final float DEFAULT_LOAD_FACTOR = 0.75f; // default Load factor of
At Java 8 HashMap
put
The method implementation is shown in code block 5,
The code block 5 --JDK8 HashMap.put methods
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;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //table When it's empty, n for table The length of the
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); // (n - 1) & hash with Java7 In the indexFor The implementation of the method is the same if i If the value at the location is empty, new is created 1 a Node . table[i] Points to the Node .
else {
// if i The value at the position is not empty, and it determines the value at the current position Node p Whether to be inserted with key the hash and key The same
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;// The same covers it
else if (p instanceof TreeNode)
// Different, and of the current position node p Is already TreeNode , and insert a new one into the tree node .
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// in i Location found in the linked list p.next for null The location of the, binCount Calculate the length of the current list, and if you continue to insert the conflicting nodes into the list, the length of the list will be greater than tree To convert the list to tree .
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;
}
Look at the
resize
Method, because it needs to be considered when hash conflict resolution may be adopted
list
May also be
balance tree
The way, therefore
resize
The method is a little more complicated than JDK7,
The code block 6 -- JDK8 the resize methods
inal 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;// If the maximum capacity is exceeded, it cannot be expanded table
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // threshold Threshold expanded to 2 times
}
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];// Create capacity as newCap the newTab And will oldTab In the Node So let's move over here, so we need to think about linked lists and tree Two cases.
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);
// split The method splits the tree into lower and upper tree Two trees,
If the number of nodes in the subtree is less than 1 UNTREEIFY_THRESHOLD Threshold, then the tree untreeify , and store all the nodes newTab In the.
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;
else
hiTail.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;
}
Let's take another look at tree
treeifyBin
Methods and
put
0
Method implementation, the bottom layer adopts the red-black tree method.
// The code block 7
//MIN_TREEIFY_CAPACITY The value of 64 If the current table the length Is not enough, resize (a)
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
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);
}
}
// putVal the tree version
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
After looking at the source code, and 11 did a comparison, marvel at the source code, a lot of benefits.
conclusion
The above is the whole content of this article, I hope the content of this article to your study or work can bring 1 definite help, if you have questions you can leave a message to communicate.