preface
Reading Suggestions: Java7 HashMap > Java7 ConcurrentHashMap > Java8 HashMap > Java8 ConcurrentHashMap The reading threshold can be lowered appropriately.
Prerequisite: This article is looking at source code, so you should at least be familiar with its interfaces. For concurrency, you should also know the CAS, ReentrantLock, and UNSAFE operations, which are not covered here. Java8 uses red-black trees, but this article will not expand on them, so please find out for yourself.
1. Java7 HashMap
HashMap is the simplest, both because it is familiar and because it does not support concurrent operations, so the source code is very simple.
First, let’s use the following diagram to illustrate the structure of a HashMap.
This is just a schematic diagram, because it does not take into account the expansion of the array. More on this later.
In general, the inside of a HashMap is an array, and each element in the array is a one-way list.
In the figure above, each green entity is an instance of the nested class Entry, which contains four attributes: key, Value, Hash value, and Next for a one-way linked list.
Capacity: Indicates the current array capacity. The capacity is always 2^n and can be expanded. After the array capacity is expanded, the array size is twice that of the current one.
LoadFactor: loadFactor. The default value is 0.75.
Threshold: capacity expansion threshold, equal to capacity x loadFactor
1.1 PUT Process Analysis
Or relatively simple, follow the code to go through.
public V put(K key, V value) {
// When inserting the first element, initialize the array size
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// If the key is null, interested parties can look inside and eventually place the entry in table[0]
if (key == null)
return putForNullKey(value);
// 1. Hash the key
int hash = hash(key);
// 2. Find the corresponding array subscript
int i = indexFor(hash, table.length);
// 3. Run the list at the corresponding index to see if duplicate keys already exist.
// If so, override it, and the put method returns the old value
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++;
// 4. There is no duplicate key. Add this entry to the linked list
addEntry(hash, key, value, i);
return null;
}
Copy the code1.1.1 Array Initialization
Initialize the array when the first element is inserted into the HashMap. Determine the initial array size and calculate the threshold for array expansion.
private void inflateTable(int toSize) {
// Make sure the array size is 2 ^ n.
New HashMap(20), then the initial array size is 32
int capacity = roundUpToPowerOf2(toSize);
// Calculate the capacity expansion threshold: capacity x loadFactor
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// Initialize the array
table = new Entry[capacity];
initHashSeedAsNeeded(capacity); //ignore
}
Copy the codeThere is a way to keep the array size to the power of 2. Java7 and Java8 require HashMap and ConcurrentHashMap, but the implementation code is slightly different, as you’ll see later.
1.1.2 Calculate the specific array location
This is easy enough to imagine ourselves: modulo the array length using the hash value of the key.
static int indexFor(int hash, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return hash & (length-1);
}
Copy the codeThis method is very simple, simply take the lowest n bits of the hash value. For example, if the array length is 32, the lower 5 bits of the hash value of the key are used as its subscript position in the array.
1.1.3 Adding a Node to a Linked List
Once the array subscript is found, the key is evaluated first, and if there are no duplicates, the new value is ready to be placed in the head of the list.
void addEntry(int hash, K key, V value, int bucketIndex) {
// If the current HashMap size has reached the threshold and there are already elements in the array where the new value will be inserted, expand it
if ((size >= threshold) && (null! = table[bucketIndex])) {// Expand capacity, which will be explained later
resize(2 * table.length);
// Recalculate the hash value after capacity expansion
hash = (null! = key) ? hash(key) :0;
// Recalculate the new index after expansion
bucketIndex = indexFor(hash, table.length);
}
/ / to look down
createEntry(hash, key, value, bucketIndex);
}
// put the new value in the head of the list and size++
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
Copy the codeThe main logic of this method is to determine whether to expand, expand if necessary, and then insert the new data into the head of the linked list at the corresponding location of the expanded array.
1.1.4 Array Expansion
If the size of the array to be inserted has reached the threshold and there are already elements in the array to be inserted, then the array size will be doubled.
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// A new array
Entry[] newTable = new Entry[newCapacity];
// Migrate the values from the original array to the new, larger array
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
Copy the codeExpansion is replacing the original small array with a new large array and moving the values from the original array to the new array.
Due to the double expansion, all the nodes of the linked list in the original table[I] will be split into newTable[I] and newTable[I + oldLength] of the new array during the migration. If the original array length is 16, all elements in the linked list at table[0] will be allocated to newTable[0] or newTable[16] in the new array after expansion. The code is a little bit simpler, so I won’t expand it here.
1.2 GET process analysis
In contrast to the PUT process, the GET process is very simple.
- Computes the hash value based on the key.
- Find the corresponding array subscript: hash & (length — 1).
- Iterate through the list at the array location until you find keys that are equal (== or equals).
public V get(Object key) {
// If the key is null, it will be placed in table[0]
if (key == null)
return getForNullKey();
//
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
Copy the codegetEntry(key):
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null)?0 : hash(key);
// Determine the array subscript, and then iterate through the list from the beginning until it is found
for(Entry<K,V> e = table[indexFor(hash, table.length)]; e ! =null;
e = e.next) {
Object k;
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
return e;
}
return null;
}
Copy the code2. Java7 ConcurrentHashMap
ConcurrentHashMap has the same idea as HashMap, but is more complex because it supports concurrent operations.
The entire ConcurrentHashMap consists of segments that stand for “part” or “Segment”, and are often described as segmented locks. Notice how many places I used “slots” to represent a segment.
ConcurrentHashMap is an array of segments. A Segment is locked by inheritingReentrantLock. As long as each Segment is thread-safe, global thread-safe is achieved.
ConcurrencyLevel: concurrencyLevel, number of concurrent sessions, number of segments. The default value is 16, which means that ConcurrentHashMap has 16 Segments, so in theory up to 16 concurrent writes can be supported at this point, as long as their operations are distributed over different Segments. This value can be set to another value at initialization, but it cannot be expanded once initialized.
Each Segment looks like a HashMap, but it’s thread safe, so it’s a bit more difficult to handle.
2.1 the initialization
InitialCapacity: indicates the initialCapacity of the entire ConcurrentHashMap. This value should be evenly allocated to each Segment.
The Segment array cannot be expanded, so the loadFactor is for internal use within each Segment.
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if(! (loadFactor >0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// Find power-of-two sizes best matching arguments
int sshift = 0;
int ssize = 1;
// Calculate the parallelism level ssize, because keep the parallelism level 2 ^ n
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
ConcurrencyLevel is 16 and sshift is 4
// Then calculate the segmentShift to 28 and the segmentMask to 15, which will be used later
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
InitialCapacity is the initial size of the entire map.
// Calculate the size of each Segment based on initialCapacity
// If initialCapacity is 64, then each Segment or "slots" can be divided into 4 segments
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
// MIN_SEGMENT_TABLE_CAPACITY is 2 by default. This value is also important because then, for specific slots,
// Insert one element and it will not expand. Insert a second element and it will expand
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;
// Create Segment array,
// Create the first element of the array segment[0]
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
// Write segment[0] to array
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
Copy the codeAfter initialization, we have an array of segments.
The new ConcurrentHashMap() constructor does not take any arguments.
- The Segment array is 16 in length and cannot be expanded
- Segment[I] default size = 2; load factor = 0.75; initial threshold = 1.5
- Initialize segment[0]; null segment[0]
- The current Value of segmentShift is 32 — 4 = 28, and segmentMask is 16 — 1 = 15. Let’s simply translate these into shift numbers and masks, which will be needed soon
2.2 PUT Process analysis
Let’s take a look at the main process of PUT, with some key details described later.
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
// 1. Compute the hash value of the key
int hash = hash(key);
// 2. Locate position J in Segment array according to hash value
// Hash is 32 bits, unsigned right segmentShift(28) bits, leaving 4 bits lower,
// Then do an and with the segmentMask(15), which means j is the last four bits of the hash value, which is the array subscript of the slot
int j = (hash >>> segmentShift) & segmentMask;
Int segment[0]; // Initialize segment[0];
// ensureSegment(j) initializes segment[j]
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
// 3. Insert the new value into slot S
return s.put(key, hash, value, false);
}
Copy the codeThe first layer is very simple: you can quickly find the Segment based on the hash value, and then put operations inside the Segment.
The Segment consists of an array and a linked list.
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// Obtain the exclusive lock on this segment before writing to it
// Take a look at the main process
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
// This is an array inside the segment
HashEntry<K,V>[] tab = table;
// Use the hash value to find the array index that should be placed
int index = (tab.length - 1) & hash;
// First is the head of the list at that position in the array
HashEntry<K,V> first = entryAt(tab, index);
// This is a long for loop, but it's easy to understand if there are no elements at all and if there is already a list
for (HashEntry<K,V> e = first;;) {
if(e ! =null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if(! onlyIfAbsent) {// Overwrite the old value
e.value = value;
++modCount;
}
break;
}
// Continue to follow the list
e = e.next;
}
else {
// Whether node is null depends on how the lock is acquired, but it doesn't matter here.
// If not null, set it directly to the linked list header; If null, initialize and set to the linked list header.
if(node ! =null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
// If the segment exceeds the threshold, the segment needs to be expanded
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node); // This will be discussed later
else
// If the threshold is not reached, place node at the index position of the array TAB,
// Set the new node to the head of the original list
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break; }}}finally {
/ / unlock
unlock();
}
return oldValue;
}
Copy the codeThe overall process is relatively simple, because the segment is protected by an exclusive lock, so the operation inside the segment is not complicated. We’ll cover the concurrency problem later.
That’s the end of the PUT operation, and let’s talk about a few of the key operations.
2.2.1 Initializing slots: ensureSegment
The ConcurrentHashMap initializes the first slot segment[0]. For other slots, the ConcurrentHashMap initializes the first slot segment when the first value is inserted.
Concurrency needs to be considered here because it is possible for multiple threads to initialize the same segment[k] at the same time, but only one of them succeeds.
private Segment<K,V> ensureSegment(int k) {
final Segment<K,V>[] ss = this.segments;
long u = (k << SSHIFT) + SBASE; // raw offset
Segment<K,V> seg;
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
// Initialize segment[0]
// Initialize segment[k] with array length and load factor at segment[0]
// Segment [0] may have already been expanded
Segment<K,V> proto = ss[0];
int cap = proto.table.length;
float lf = proto.loadFactor;
int threshold = (int)(cap * lf);
// Initialize the array inside segment[k]
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) { // Check again if the slot is initialized by another thread.
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
// Use the while loop, internal CAS, the current thread successfully set the value or another thread successfully set the value, exit
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break; }}}return seg;
}
Copy the codeIn general, ensureSegment(int k) is simple, and CAS is used to control concurrent operations.
2.2.2 Obtaining a write lock: scanAndLockForPut
As we saw earlier, when putting to a segment, node = tryLock() is called first. Null: scanAndLockForPut(key, hash, value), which means that a tryLock() is performed to quickly acquire the exclusive lock on the segment. If that fails, go to scanAndLockForPut to obtain the lock.
Now let’s analyze how to control locking in this method.
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
HashEntry<K,V> first = entryForHash(this, hash);
HashEntry<K,V> e = first;
HashEntry<K,V> node = null;
int retries = -1; // negative while locating node
// Loop to get the lock
while(! tryLock()) { HashEntry<K,V> f;// to recheck first below
if (retries < 0) {
if (e == null) {
if (node == null) // speculatively create node
// The list at that position in the array is empty without any elements
// Of course, another reason to enter here is that tryLock() failed, so there is concurrency in the slot, not necessarily in that position
node = new HashEntry<K,V>(hash, key, value, null);
retries = 0;
}
else if (key.equals(e.key))
retries = 0;
else
// Go down the list
e = e.next;
}
// If the number of retries exceeds MAX_SCAN_RETRIES (single-core, multi-core, 64), the lock is stopped and the queue is blocked
// lock() is a blocking method until it returns after acquiring the lock
else if (++retries > MAX_SCAN_RETRIES) {
lock();
break;
}
else if ((retries & 1) = =0 &&
// A new element is added to the list as a new header
// So the strategy here is to iterate over the scanAndLockForPut method
(f = entryForHash(this, hash)) ! = first) { e = first = f;// re-traverse if entry changed
retries = -1; }}return node;
}
Copy the codeThe method has two exits, either when tryLock() succeeds and the loop terminates, or when MAX_SCAN_RETRIES exceeds its attempts to enter the lock() method, which blocks and waits until the exclusive lock succeeds.
This method may seem complicated, but it actually does one thing: get the exclusive lock on the segment and instantiate Node if necessary.
2.2.3 Capacity Expansion: Rehash
The size of the segment array is doubled by the size of the HashEntry[] array inside the segment array.
Insert the segment in a way that will cause the number of elements in the segment to exceed the threshold. Insert the segment in a way that will cause the number of elements in the segment to exceed the threshold.
This method doesn’t need to worry about concurrency because at this point, the exclusive lock on the segment is held.
// Node is the data that needs to be added to the new array after the expansion.
private void rehash(HashEntry<K,V> node) {
HashEntry<K,V>[] oldTable = table;
int oldCapacity = oldTable.length;
/ / 2 times
int newCapacity = oldCapacity << 1;
threshold = (int)(newCapacity * loadFactor);
// Create a new array
HashEntry<K,V>[] newTable =
(HashEntry<K,V>[]) new HashEntry[newCapacity];
// If the new mask is expanded from 16 to 32, then the size of the mask is 31, corresponding to binary '000... 00011111 '
int sizeMask = newCapacity - 1;
// Split the list at position I into position I and I +oldCap
for (int i = 0; i < oldCapacity ; i++) {
// e is the first element in the list
HashEntry<K,V> e = oldTable[i];
if(e ! =null) {
HashEntry<K,V> next = e.next;
// Calculate the position to be placed in the new array,
// If the array length is 16 and e is at oldTable[3], then idx can only be 3 or 3 + 16 = 19
int idx = e.hash & sizeMask;
if (next == null) // There is only one element in this position, which is easier to handle
newTable[idx] = e;
else { // Reuse consecutive sequence at same slot
// e is the list header
HashEntry<K,V> lastRun = e;
// idx is the new position of the current list header e
int lastIdx = idx;
// The following for loop finds a lastRun node, after which all elements are to be grouped together
for(HashEntry<K,V> last = next; last ! =null;
last = last.next) {
int k = last.hash & sizeMask;
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
// Place the list of lastRun and all subsequent nodes at lastIdx
newTable[lastIdx] = lastRun;
// Handle the node before lastRun,
// These nodes may be assigned to another list, or to the list above
for(HashEntry<K,V> p = e; p ! = lastRun; p = p.next) { V v = p.value;int h = p.hash;
int k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = newHashEntry<K,V>(h, p.key, v, n); }}}}// Place the new node at the head of one of the two lists in the new array
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
Copy the codeThe expansion here is a bit more complicated than the previous HashMap, and the code is a bit more difficult to understand. There are two for loops right next to each other, so what’s the use of the first for?
A closer look shows that it would have worked without the first for loop, but if there were more nodes after the lastRun, it would have been worth it. Because we only need to clone the nodes in front of lastRun, the following string of nodes will follow lastRun without doing anything.
I think Doug Lea’s idea is also interesting, but the worst case scenario is that every lastRun is the last or very last element in the list, and the loop is a bit wasted. However, Doug Lea also stated that according to the statistics, if the default threshold is used, only about 1/6 nodes need to be cloned.
2.3 GET process analysis
Compared to put, get is really not that easy.
- Compute the hash value to find the exact location in the Segment array, or the “slot” we used earlier.
- Slot is also an array, using the hash to find the specific location in the array
- So here’s the list, and you can just follow the list
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
/ / 1. Hash value
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
// 2. Find the corresponding segment based on the hash
if((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) ! =null&& (tab = s.table) ! =null) {
// 3. Select * from the list where the segment resides
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE); e ! =null; e = e.next) {
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
returne.value; }}return null;
}
Copy the code2.4 Analysis of concurrency problems
Now that we’ve talked about put and GET, we can see that there is no lock in get, so naturally we need to worry about concurrency.
The operation put to add nodes and the operation remove to remove nodes both need to add exclusive locks on the segment, so there is no problem between them naturally. What we need to consider is that put or remove operations occur in the same segment when we get.
-
Thread safety of put operations.
- The initialization slot, which we talked about earlier, uses CAS to initialize the array in the Segment.
- Adding a node to the list is inserted into the header, so it doesn’t matter if the GET operation is already in the middle of the list traversal. Another concurrency problem, of course, is that after put, the get operation needs to ensure that the node just inserted into the header is read, depending on the unsafe. putOrderedObject used in the setEntryAt method.
- Expansion. Expansion creates a new array, migrates the data, and finally sets newTable to the property table. So, if the get operation is also running, then it doesn’t matter. If the get operation is running first, then the query will be performed on the old table. If put comes first, the visibility guarantee for put is that the table uses volatile.
-
Thread-safety of the remove operation.
Remove operation we did not analyze the source code, so here said readers interested in the source code or need to check.
The get operation traverses the list, but the remove operation “breaks” the list.
If the node get operation broken by remove has already passed, then there is no problem.
If remove destroys a node first, consider two cases. If the node is a header, you need to set the next of the header to the element at that position in the array. Even though table is volatile, volatile does not guarantee the visibility of operations inside the array. Therefore, the source code uses UNSAFE to manipulate arrays. Look at the method setEntryAt. 2. If the node to be deleted is not a header, it will connect the successor node of the deleted node to the precursor node. The concurrency guarantee here is that the next attribute is volatile.
3. Java8 HashMap
Java8 makes some changes to HashMap, but the big difference is that it leverages red-black trees, so it consists of arrays, linked lists, and red-black trees.
Java7 HashMap can quickly locate the index of the array based on the hash value, but then we need to go down the list to find the index. The time complexity depends on the length of the list, O(n).
To reduce this overhead, in Java8, when the list has more than eight elements, the list is converted to a red-black tree, reducing the time complexity of lookups at these locations to O(logN).
Here’s a simple illustration:
Note that the diagram above is a schematic, mainly describing the structure, which will not reach this state, because so much data has already been expanded.
Below, we still use the code to introduce it, personal feeling, Java8 source code is less readable, but a little more concise.
Java7 uses Entry to represent each data Node in a HashMap. Java8 uses Node, which is basically the same, with key, Value, Hash, and next attributes. However, Node can only be used for linked lists. The red-black tree case requires TreeNode.
We can determine whether it is a linked list or a red-black tree based on whether the first Node in the array element is a Node or a TreeNode.
3.1 PUT Process Analysis
public V put(K key, V value) {
return putVal(hash(key), key, value, false.true);
}
// If the third argument onlyIfAbsent is true, the put operation is performed only when the key does not exist
// The fourth parameter evict we don't care about here
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 first time a value is put, the following resize() is triggered. Java7-like first put also initializes the array length
// The first resize is a bit different from the subsequent expansion, because this time the array is initialized from null to the default 16 or custom initial capacity
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// Find the array index. If there is no value, initialize Node and place it there
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {// There is data at this position in the array
Node<K,V> e; K k;
// First, determine whether the first data in the position is "equal" to the data we want to insert, if so, fetch the node
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
// If the node represents a red-black tree, call the red-black tree interpolation method. This article does not expand the red-black tree
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// The array is a linked list at this position
for (int binCount = 0; ; ++binCount) {
// Insert to the back of the list (Java7 inserts to the front of the list)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD is 8, so if the newly inserted value is the ninth in the list
// Triggers the following treeifyBin, which converts the list to a red-black tree
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// If you find "equal" keys in the list (== or equals)
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
// break, then e is the node "equal" to the key of the new value to be inserted
break; p = e; }}// e! =null indicates that the old key is "equal" to the inserted key.
// For the put we are analyzing, the following if is simply "overwriting" the value and then returning the old value
if(e ! =null) {
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// If the HashMap has exceeded the threshold due to the insertion of this value, it needs to be expanded
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeA slight difference from Java7, where values are interpolated before values are inserted, is that Java8 interpolates before values are interpolated, but this is not important.
3.1.1 Expanding array Capacity
The resize() method is used to initialize an array or expand the array. After each expansion, the array capacity is doubled and data is migrated.
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) { // Expand the array
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// Double the array size
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// Double the threshold
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // It corresponds to the first put after initialization using new HashMap(int initialCapacity)
newCap = oldThr;
else {// corresponding to the first put after initialization with new HashMap()
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;
// Initialize the new array with the new array size
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // If you're initializing an array, you're done here, return newTab
if(oldTab ! =null) {
// Start traversing the array for data migration.
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if((e = oldTab[j]) ! =null) {
oldTab[j] = null;
// If there is only one element in the array position, it is easy to simply migrate the element
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// If it is a red-black tree, we will not expand it
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// This is the case with the linked list,
// We need to split this list into two lists and put them in a new array, keeping the original order
// loHead and loTail correspond to one list, hiHead and hiTail correspond to another list
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;
// The first list
newTab[j] = loHead;
}
if(hiTail ! =null) {
hiTail.next = null;
// The new position of the second list is j + oldCap
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Copy the code3.2 GET process analysis
Get is really easy compared to put.
- Hash & (length-1) hash & (length-1)
- Determine if the element at that position in the array is exactly what we are looking for. If not, go to step 3
- Determine if the element type is TreeNode. If so, fetch the data using the red-black tree method. If not, go to step 4
- Iterate through the list until you find keys that are equal (== or equals)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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 &&
(first = tab[(n - 1) & hash]) ! =null) {
// Determine if the first node is needed
if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
if((e = first.next) ! =null) {
// Check if it is a red black tree
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// list traversal
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 code4. Java8 ConcurrentHashMap
The ConcurrentHashMap implemented in Java7 is quite complex to be honest, and Java8 has made major changes to the ConcurrentHashMap. You are advised to refer to the changes of The HashMap in Java8 compared to the HashMap in Java7. For ConcurrentHashMap, Java8 also introduces a red-black tree.
To tell the truth, Java8 ConcurrentHashMap source code is really not simple, the most difficult is expansion, data migration operation is not easy to understand.
Let’s first describe its structure with a schematic diagram:
The structure is basically the same as Java8’s HashMap, but it is a bit more complex in source code because it is thread-safe.
4.1 the initialization
// Do nothing in this constructor
public ConcurrentHashMap(a) {}public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1))? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>>1) + 1));
this.sizeCtl = cap;
}
Copy the codeSizeCtl = (1.5 * initialCapacity + 1) and then take the nearest 2 to the NTH power. If initialCapacity is 10, sizeCtl is 16; if initialCapacity is 11, sizeCtl is 32.
The sizeCtl attribute is used in many different scenarios, but it will not confuse you if you follow the sizeCtl thread.
If you want to mess around, you can also look at another constructor that takes three arguments, which I won’t mention here. Most of the time, we’ll instantiate using the no-argument constructor, and we’ll do our source code analysis along the same lines.
4.2 PUT Process Analysis
Go through the code line by line carefully:
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// Get the hash value
int hash = spread(key.hashCode());
// Record the length of the corresponding list
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// If the array is empty, initialize the array
if (tab == null || (n = tab.length) == 0)
// Initialize the array, more on that later
tab = initTable();
// find the array index corresponding to the hash value to get the first node f
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// If the position in the array is empty,
// Add the new value with a CAS operation. The put operation is almost done, and can be pulled to the end
// If the CAS fails, there is a concurrent operation, and the next loop is ready
if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// Hash = 'MOVED' // Hash = 'MOVED
else if ((fh = f.hash) == MOVED)
// Help with data migration. This is easy to understand after reading the section on data migration
tab = helpTransfer(tab, f);
else { // This means that f is the head of this position and is not null
V oldVal = null;
// Get the monitor lock on the header at that position in the array
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) { // If the hash value of the header is greater than 0, it is a linked list
// Add the length of the list
binCount = 1;
// Iterate over the list
for (Node<K,V> e = f;; ++binCount) {
K ek;
// If the "equal" key is found, determine whether to override the value, and then break the value
if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
oldVal = e.val;
if(! onlyIfAbsent) e.val = value;break;
}
// At the end of the list, place the new value at the end of the list
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break; }}}else if (f instanceof TreeBin) { / / the red-black tree
Node<K,V> p;
binCount = 2;
// Call the red-black tree interpolation method to insert a new node
if((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! =null) {
oldVal = p.val;
if(! onlyIfAbsent) p.val = value; }}}}// binCount ! = 0 indicates that linked list operations are being performed
if(binCount ! =0) {
// Determine whether to convert the list to a red-black tree, the threshold is the same as for HashMap, also 8
if (binCount >= TREEIFY_THRESHOLD)
// This method is slightly different from the HashMap method in that it does not necessarily perform a red-black tree conversion,
// If the current array length is less than 64, array expansion is selected instead of red-black tree conversion
// Add the following information to the file
treeifyBin(tab, i);
if(oldVal ! =null)
return oldVal;
break; }}}//
addCount(1L, binCount);
return null;
}
Copy the codeThe main process of PUT is finished, but there are at least a few problems left. The first one is initialization, the second one is capacity expansion, and the third one is data migration assistance, which will be covered in the following sections.
4.2.1 Initializing an Array: initTable
So this is a little bit simpler, just initialize an array of the right size, and then set it to sizeCtl.
Concurrency issues in the initialization method are controlled by performing a CAS operation on sizeCtl.
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// The credit for initialization was taken by another thread
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// Set sizeCtl to -1, indicating lock capture
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
// DEFAULT_CAPACITY The default initial capacity is 16
int n = (sc > 0)? sc : DEFAULT_CAPACITY;// Initialize the array with a length of 16 or the length provided at initialization
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n];// Assign this array to table, which is volatile
table = tab = nt;
// sc = 12 if n is 16
// This is 0.75 * n
sc = n - (n >>> 2); }}finally {
// set sizeCtl to sc and let's call it 12
sizeCtl = sc;
}
break; }}return tab;
}
Copy the code4.2.2 Converting linked lists to red-black trees: treeifyBin
As mentioned in the put source code analysis, treeifyBin does not necessarily perform red-black tree conversions, but may only perform array expansion. Let’s do the source code analysis.
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if(tab ! =null) {
/ / MIN_TREEIFY_CAPACITY for 64
So, if the array size is less than 64, which is 32 or 16 or less, the array size will be expanded
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
// We'll look at this method in more detail later
tryPresize(n << 1);
// b is the header
else if((b = tabAt(tab, index)) ! =null && b.hash >= 0) {
/ / lock
synchronized (b) {
if (tabAt(tab, index) == b) {
// Create a red-black tree by iterating through the list
TreeNode<K,V> hd = null, tl = null;
for(Node<K,V> e = b; e ! =null; e = e.next) {
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null.null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
// Set the red-black tree to the appropriate location in the array
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
Copy the code4.3 Capacity Expansion: tryPresize
If the source code for Java8 ConcurrentHashMap is not simple, then it is the expansion operations and migration operations.
To fully understand this method, we also need to look at the subsequent transfer method, which readers should know in advance.
The capacity here is also doubled, the capacity of the array is doubled.
// The method parameter size is already doubled when passed in
private final void tryPresize(int size) {
// c: size 1.5 times, then add 1, then take the nearest 2 to the n power.
int c = (size >= (MAXIMUM_CAPACITY >>> 1))? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>>1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
// The if branch is basically the same as the code we used to initialize the array, so we can leave it alone
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n]; table = nt; sc = n - (n >>>2); / / 0.75 * n}}finally{ sizeCtl = sc; }}}else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
// I don't understand what rs really means, but it doesn't matter
int rs = resizeStamp(n);
if (sc < 0) {
Node<K,V>[] nt;
if((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs +1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 2. Add 1 to sizeCtl with CAS and transfer
// nextTab is not null
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// set sizeCtl to (rs << RESIZE_STAMP_SHIFT) + 2)
// What is the real meaning of this value? But what you can calculate is that it's going to be a big negative number
// Transfer is called with the nextTab parameter null
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null); }}}Copy the codeThe core of this method is the sizeCtl operation, first set it to a negative value, then transfer(TAB, NULL), then the next loop will add 1 to sizeCtl and transfer(TAB, nt), This may be followed by continuing with sizeCtl plus 1 and transferring (TAB, NT).
Therefore, the possible operation is to perform a transfer(TAB, NULL) + multiple transfer(TAB, NT), here how to end the loop need to read the transfer source code before it is clear.
4.3.1 Data Migration: Transfer
The following method, rather long, migrates elements from the original TAB array to the new nextTab array.
Although multiple calls to transfer in the tryPresize method don’t involve multithreading, the transfer method can be called elsewhere, typically, as we said before when we talked about put. Look up at put, Is there a place where helpTransfer is called? HelpTransfer will call Transfer.
This method supports multi-thread execution. When the peripheral calls this method, the nextTab parameter is guaranteed to be null for the first thread that initiates the data migration. When the peripheral calls this method, the nextTab parameter will not be null.
Before reading the source code, understand the mechanics of concurrent operations. The original array length is N, so we have n migration tasks. It is easiest for each thread to take charge of one small task at a time. After each task is completed, we can check whether there are other tasks that are not completed to help migration. Each thread is responsible for migrating one part at a time, for example, migrating 16 small tasks at a time. Therefore, we need a global scheduler to assign which threads to perform which tasks, which is what the property transferIndex does.
The first thread that initiates the data migration will point the transferIndex to the last position of the original array, then the backward stride task belongs to the first thread, then the forward stride task belongs to the new position, and the next stride task belongs to the second thread, and so on. Of course, the second thread here does not necessarily refer to the second thread, but could also be the same thread, the reader should understand. This is essentially breaking up a large migration task into task packages.
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// The stride is directly equal to n in single-core mode, (n>>>3)/NCPU in multi-core mode, and the minimum value is 16
// Stride can be understood as "step length", there are n positions that need to be transferred,
// Divide the n tasks into multiple task packages, and each task package has stride tasks
if ((stride = (NCPU > 1)? (n >>>3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// If nextTab is null, initialize it first
NextTab is null when this method is called by the first thread that initiates the migration
NextTab will not be null when this method is called later by the participating thread
if (nextTab == null) {
try {
// Double the capacity
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n <<1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
// nextTable is an attribute in ConcurrentHashMap
nextTable = nextTab;
// transferIndex is also an attribute of ConcurrentHashMap, which controls the location of the migration
transferIndex = n;
}
int nextn = nextTab.length;
// ForwardingNode translates to Node being migrated
// This constructor will generate a Node with null key, value, and next. The key is that the hash is MOVED
// After the node at position I is migrated,
// Position I is set to this ForwardingNode, which tells other threads that position has already been handled
// So it's kind of a sign.
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// Advance refers to having completed the migration of a location and being ready for the next location
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
/* */ * */ * */ * */ * */ * */ * */
// I is the position index, and bound is the boundary
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// The following while is really confusing
// Advance is true to indicate that the next location can be migrated
// I points to transferIndex, bound points to transferIndex-stride
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
// Assign transferIndex to nextIndex
// If transferIndex is less than or equal to 0, all positions in the original array are processed by the corresponding thread
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
// Look at the code in parentheses. NextBound is the boundary of the migration task, from back to front
bound = nextBound;
i = nextIndex - 1;
advance = false; }}if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
// All migration operations have been completed
nextTable = null;
// Assign the new nextTab to the table property to complete the migration
table = nextTab;
// recalculate sizeCtl: n is the size of the original array, so the sizeCtl value will be 0.75 times the size of the new array
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// As we said before, sizeCtl will be set to (RS << RESIZE_STAMP_SHIFT) + 2 before migration
// Then add 1 to the sizeCtl for each thread participating in the migration,
SizeCtl = 1; // The CAS operation is used to subtract 1 from sizeCtl
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// The task ends, and the method exits
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
(sc-2) == resizeStamp(n) << stamp_shift,
// That is, all the migration tasks are done and the if(finishing){} branch is up
finishing = advance = true;
i = n; // recheck before commit}}// If position I is empty and there are no nodes, then place the ForwardingNode "empty node" that was just initialized.
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// The location is a ForwardingNode, indicating that the location has been migrated
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
// Lock the node at the location of the array and start processing the migration of the array
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
// If the hash of the header is greater than 0, it is a linked Node
if (fh >= 0) {
// This is similar to the ConcurrentHashMap migration in Java7,
// We need to split the list in two,
// Find lastRun in the original list, then lastRun and its subsequent nodes are migrated together
// The nodes before lastRun need to be cloned and divided into two linked lists
int runBit = fh & n;
Node<K,V> lastRun = f;
for(Node<K,V> p = f.next; p ! =null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for(Node<K,V> p = f; p ! = lastRun; p = p.next) {int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
// One of the lists is placed at position I of the new array
setTabAt(nextTab, i, ln);
// Put another list at position I +n of the new array
setTabAt(nextTab, i + n, hn);
// Set the position of the original array to FWD, indicating that the position has been processed,
// Other threads will not migrate once they see that the hash value at this location is MOVED
setTabAt(tab, i, fwd);
// Advance is set to true to indicate that the location has been migrated
advance = true;
}
else if (f instanceof TreeBin) {
// Red black tree migration
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for(Node<K,V> e = t.first; e ! =null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null.null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
elsehiTail.next = p; hiTail = p; ++hc; }}// If the number of nodes is less than 8, then the red-black tree is converted back to the linked listln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc ! =0)?newTreeBin<K,V>(lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc ! =0)?new TreeBin<K,V>(hi) : t;
// place ln at position I of the new array
setTabAt(nextTab, i, ln);
// Place hn at position I +n of the new array
setTabAt(nextTab, i + n, hn);
// Set the position of the original array to FWD, indicating that the position has been processed,
// Other threads will not migrate once they see that the hash value at this location is MOVED
setTabAt(tab, i, fwd);
// Advance is set to true to indicate that the location has been migrated
advance = true;
}
}
}
}
}
}
Copy the codeIn the final analysis, the transfer method does not realize all migration tasks. Each call of this method only realizes the migration of the first step of the transferIndex, and the rest needs to be controlled by the periphery.
At this point, go back and look at the tryPresize method a little more clearly.
4.4 GET Process analysis
The get method is always the simplest, and this is no exception:
- Calculate the hash value
- Locate (n – 1) &h based on the hash value
- Search according to the properties of the junction point at this position
- If the location is NULL, then simply return NULL
- If the node at that location is exactly what we want, we simply return the value of that node
- If the hash value of this node is less than 0, it indicates expansion or a red-black tree. We will describe the find method later
- If none of the above three items are met, it is a linked list and can be traversed
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if((tab = table) ! =null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) ! =null) {
// Determine if the header is the desired node
if ((eh = e.hash) == h) {
if((ek = e.key) == key || (ek ! =null && key.equals(ek)))
return e.val;
}
// If the hash of the header is less than 0, expansion is under way, or the location is a red-black tree
else if (eh < 0)
Forwardingnode. find(int h, Object k) and treebin. find(int h, Object k)
return(p = e.find(h, key)) ! =null ? p.val : null;
// Iterate over the list
while((e = e.next) ! =null) {
if(e.hash == h && ((ek = e.key) == key || (ek ! =null && key.equals(ek))))
returne.val; }}return null;
}
Copy the codeForwardingnode. find(int h, Object k) forwardingNode. find(int h, Object k) forwardingNode. find(int h, Object k)