Hashtables
8 min readNov 21, 2020
Java’s Strength :
Collections
Multithreading
Intent for today’s session
Concepts
Interview Q
Variations of Hashtable:
- Hashmap
- Hashtable
- Linkedhashmap
- ConcurrentHashMap
General contract associated with hashCode() method
- The hashCode() method should return the same integer value for the same object for each calling of this method unless the value stored in the object is modified.
- If two objects are equal(according to equals() method) then the hashCode() method should return the same integer value for both the objects.
- But, it is not necessary that the hashCode() method will return the distinct result for the objects that are not equal (according to equals() method).
Hashmap
Why we need to resize the HashMap?
Its because if the size is fixed and as more and more elements are added to the hashmap, then there will be more and more collisions and hence longer linkedlists maintained, hence iterating over them will not be with constant time anymore but may go upto O(n). So to spread the Nodes more evenly, resize the hashmap once the total number of nodes in it exceeds some threshold value.
So to resize:
new Hashmap with new capacity (= double the previous capacity) is created, the table now points to it, and the new threshold is created.
Finally, the old elements are transferred to this new Hashmap as:
We iterate over every table index, at every index we iterate over all the elements of the LinkedList there.
At every array index, the element found let be “e”.
Second, the method analysis
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //The array of all current elements, called the old element array
Int oldCap = (oldTab == null) ? 0 : oldTab.length; // old element array length
Int oldThr = threshold; // old expansion threshold setting
Int newCap, newThr = 0; // The capacity of the new array, the expansion threshold of the new array is initialized to 0
If (oldCap > 0) { // If the old array length is greater than 0, the element already exists
// PS1
If (oldCap >= MAXIMUM_CAPACITY) { // If the number of array elements is greater than or equal to the defined maximum capacity (2 to the 30th power)
// The expansion threshold is set to the int maximum (2 to the power of 31 -1 ), because oldCap multiplies by 2 and overflows.
threshold = Integer.MAX_VALUE;
Return oldTab; // return the old array of elements
}
/*
* If the number of array elements is within the normal range, then the new array capacity is twice the capacity of the old array (1 bit shifted to the left by 2)
* If the new capacity after expansion is less than the maximum capacity and the old array capacity is greater than or equal to the default initialization capacity (16), then the expansion threshold of the new array is set to twice the old threshold. (The old array size greater than 16 means: either the constructor specifies an initial value greater than 16 or has experienced at least one expansion)
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// PS2
// Run to this else if the old array has no elements
// If the expansion threshold of the old array is greater than 0, then set the capacity of the new array to the threshold
// This step also means that the initialization capacity is specified when the map is constructed.
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// If you can run here, it means that the map created by calling the no-argument constructor is called, and the element is added for the first time.
newCap = DEFAULT_INITIAL_CAPACITY; // Set the new array size to 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // Set the new array expansion threshold to 16*0.75 = 12. 0.75 is the load factor (when the number of elements reaches the capacity of 3/4, then expand)
}
// If the expansion threshold is 0 (in the case of PS2)
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE); // See also: PS2
}
Threshold = newThr; // Set the map's expansion threshold to the new threshold
@SuppressWarnings({"rawtypes","unchecked"})
/ / Create a new array (for the first time to add an element, then this array is the first array; for the existence of oldTab, then this array is the new array to be expanded)
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
Table = newTab; // point the map's table property to the new array
If (oldTab != null) { // If the old array is not empty, it means that it is a capacity expansion operation, then the transfer operation involving the element
For (int j = 0; j < oldCap; ++j) { // traverse the old array
Node<K,V> e;
If ((e = oldTab[j]) != null) { // If the current position element is not empty, then you need to transfer the element to the new array
oldTab[j] = null; // Release the old array's reference to the element to be moved (mainly to make the array recyclable)
If (e.next == null) // If the element does not have a next node, there is no hash conflict for the element
// PS3
/ / Store the element in a new array, where to store the array needs to be modulo according to the hash value and the length of the array
// [hash value % array length] = [hash value & (array length -1)]
// This way of calculating the modulo with the operation requires that the length of the array must be 2 to the power of N, but the initialization capacity can be arbitrarily specified by the constructor. If you specify 17,15, is this not a problem? It doesn't matter, the user-specified one will eventually be converted to a N-th power greater than its nearest 2 by the tableSizeFor method. 15 -> 16, 17-> 32
newTab[e.hash & (newCap - 1)] = e;
// If the element has the next node, then there is a linked list at the location (the same multiple elements of the hash are stored in the list of the old array in a linked list)
// For example: the length of the array is 16, then the two values with a hash value of 1 (1% 16=1) and a hash value of 17 (17% 16=1) are stored in the second position of the array. (The corresponding array subscript is 1). When the array is expanded to 32 (1%32=1), the hash value of 1 should also be stored in the second position of the new array, but the hash value is 17 (17%32). =17) should be stored in the 18th position of the new array.
// So, after the array is expanded, all elements need to be recalculated in the new array.
Else if (e instanceof TreeNode) // if the node is of type TreeNode
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // Discuss it separately here
else { // preserve order
Node<K,V> loHead = null, loTail = null; // If you translate by naming, it should be called the low end node
Node<K,V> hiHead = null, hiTail = null; // If you translate by naming, you should call the high end node
// The lower bits above refer to 0 to oldCap-1 of the new array, and the upper bits specify oldCap to newCap - 1
Node<K,V> next;
// traversing the linked list
do {
next = e.next;
// This step is good, take the hash value of the element and the length of the old array.
// PS3 said that the length of the array must be 2 to the Nth power (for example, 16). If the hash value and the length are ANDed, the result is 0, indicating the value of the hash value and the length of the array. Must be less than the length of the array (for example, the mod value is 1),
// Then the mod value will not change if the hash value is compared with the length of the new array, so the position of the element in the new array is the same as the position of the old array, so the element can be placed in the lower list. in.
if ((e.hash & oldCap) == 0) {
// PS4
If (loTail == null) // If there is no tail, the list is empty
loHead = e; // When the linked list is empty, the head node points to the element
else
loTail.next = e; // If there is a tail, then the list is not empty, and the element is hung to the end of the list.
loTail = e; // Set the tail node to the current element
}
// If the result of the AND operation is not 0, the hash value is greater than the length of the old array (for example, the hash value is 17)
// The element should now be placed in the high position of the new array
// Example: the length of the old array is 16, then the length of the new array is 32, and the hash of 17 should be placed in the 17th position of the array, that is, the subscript is 16, then the subscript is 16 and already belongs to the high position. The lower position is [0-15], the high position is [16-31]
Else { // The following logic is the same as PS4
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
If (loTail != null) { // The linked list of low-level elements is still placed in its original location
loTail.next = null;
newTab[j] = loHead;
}
If (hiTail != null) { // The position of the linked list of high-order elements is only offset from the original position by the length of the old array.
hiTail.next = null;
newTab[j + oldCap] = hiHead; // Example: hash is 17 in the old array placed in the 0 subscript, in the new array placed in the 16 subscript; hash is 18 in the old array placed in the 1 subscript, placed in the new array Subscript at 17;
}
}
}
}
}
Return newTab; // return a new array
}
LinkedHashMap
LinkedHashMap in Java
- It’s part of Java Collections Framework.
- LinkedHashMap is the hash table and linked list implementation of the Map interface.
- LinkedHashMap extends HashMap class.
- LinkedHashMap maintains the order of insertion. So while iterating over its keys, the elements are returned in the order they were inserted.
- LinkedHashMap uses a doubly-linked list to maintain the order of insertion.
- If a key is reinserted, its insertion order is not affected.
- It’s useful when you want a Map where we can iterate over the entries in the order of insertion but don’t want to deal with the additional overhead associated with the TreeMap.
- LinkedHashMap allows null entries for key and value. There can be a single null key and multiple null values.
- LinkedHashMap is not thread-safe. If you want to use it in a multi-threaded environment, you can create a synchronized wrapper over it using the Collections.synchronizedMap() method.