What is the difference between hashMap in JDK8 and hashMap in JDK7?
In JDK8, the bottom layer of hashMap is implemented by array + linked list + red-black tree.
2, jdK7 linked list insert method is head insert method, jdK8 changed to tail insert method.
3. The hash algorithm in JDK8 is actually less complex because red-black trees are used to ensure efficient insertion and query.
In jdK8, the condition of array expansion has also been changed. Only if the current number of elements exceeds the threshold, it will not determine if the array subscript position of the current element has an element.
The flow of the put method in HashMap?
1. Calculate a hashCode using the key.
2. Calculate the array subscript using hashCode and the and operation.
3. Encapsulate the key and value as an entry object.
4. Check whether the subscript position of the array is empty. If it is empty, the entry object is stored in the subscript position
5. If the array subscript position is not empty, insert the entry into the list
6. Check whether the linked list has the same key, if so, update the value
7, if jdK7, use the head plug method, if jdK8, use the tail plug method
If it is JDK8, the list will be traversed, and in the process of traversing the list, count the number of elements in the current list, if more than 8, the list will be converted to a red-black tree, and the element is inserted into the red-black tree
Why does a HashMap form a circular list in multiple threads
HashMap is composed of a one-dimensional array and a linked list, so it can be learned that HashMap chooses the chained address method when solving conflicts. The answer given at the time to why a HashMap consists of a linked list of arrays is inferred from several algorithms for resolving conflicts, and here is a positive reason:
1. Why one-dimensional array is used: The storage range of array is continuous and occupies a large amount of memory, so the space is very complex. But the binary search time complexity of array is O(1). Arrays are easy to address and difficult to insert and delete
2. Why the linked list is used: The storage interval of linked list is discrete and occupies relatively loose memory, so the space complexity is small, but the time complexity is large, up to O (N). Linked lists are difficult to address and easy to insert and delete
A HashMap is a combination of the two, storing hash addresses in one-dimensional arrays for faster traversal. Store address values in linked lists for faster insertion and deletion!
Formation analysis of ring linked list
So how do you form a circular list in a HashMap? This problem starts with the resize of HashMap.
Expansion principle of HashMap:
-
/ * *
-
* The default initial capacity – MUST be a power of two.
-
* /
-
static final int DEFAULT_INITIAL_CAPACITY = 16;
-
/ * *
-
* The maximum capacity, used if a higher value is implicitly specified
-
* by either of the constructors with arguments.
-
* MUST be a power of two <= 1<<30.
-
* /
-
static final int MAXIMUM_CAPACITY = 1 << 30;
-
/ * *
-
* The load factor used when none specified in constructor.
-
* /
-
Static final float DEFAULT_LOAD_FACTOR = 0.75f;
Array expansion occurs when the number of elements in a HashMap exceeds the array size (length, not size)*loadFactor. The default value of loadFactor is 0.75, which is a compromise. When the number of elements in the HashMap exceeds 16*0.75=12 (threshold), the size of the array is doubled to 2*16=32. If the number of elements in the HashMap exceeds 16*0.75=12 (threshold), the size of the array is doubled to 32. Then recalculate the position of each element in the array, which is a very performance consuming operation, so if we already know how many elements are in the HashMap, the preset number of elements can effectively improve the performance of the HashMap.
Resize () resize()
-
/ * *
-
* Rehashes the contents of this map into a new array with a
-
* larger capacity. This method is called automatically when the
-
* number of keys in this map reaches its threshold.
-
*
-
* If current capacity is MAXIMUM_CAPACITY, this method does not
-
* resize the map, but sets threshold to Integer.MAX_VALUE.
-
* This has the effect of preventing future calls.
-
*
-
* @param newCapacity the new capacity, MUST be a power of two;
-
* must be greater than current capacity unless current
-
* capacity is MAXIMUM_CAPACITY (in which case value
-
* is irrelevant).
-
* /
-
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];
-
boolean oldAltHashing = useAltHashing;
-
useAltHashing |= sun.misc.VM.isBooted() &&
-
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
-
boolean rehash = oldAltHashing ^ useAltHashing;
-
transfer(newTable, rehash);
-
table = newTable;
-
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
-
}
NewCapacity the new capacity, MUST be a power of two; must be greater than current capacity unless current capacity is MAXIMUM_CAPACITY (in which case value is irrelevant)
Inside this, another function transfer function is called:
[java] view plain copy
- / * *
- * Transfers all entries from current table to newTable.
- * /
- 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;
- }
- }
- }
Basically, copy the old data elements, create a new space with a larger capacity, and then copy the data!
So the formation of the circular linked list is mainly in the process of expansion. When multiple threads simultaneously perform the put operation on the HashMap and perceive that the memory capacity is insufficient, multiple threads will perform the resize operation at the same time, which causes the problem as follows:
First, when the HashMap expands, it changes the order of the elements in the list, inserting them from the head of the list. PS: In order to avoid tail traversal, this part is not the main introduction of this blog.
The circular list occurs at this moment, and the following simulation simulates the simultaneous expansion of two threads. For example, the current hashmap space is 2 (critical value is 1), hashCode is 0 and 1 respectively, and there are elements A and B at hash address 0. At this time, element C needs to be added. After hash operation, THE hash address of C is 1. So in multi-threaded conditions, there will be conditional competition, the simulation process is as follows:
Thread 1: Reads the current HashMap, and in preparation for capacity expansion, thread 2 intervenes
Thread 2: Reads the HashMap for capacity expansion
Thread 1: Continue execution
Copy A to the new hash table, and then copy B to the header. Select * from thread B where a. next=A; select * from thread B where a. next=A; A.next=B
Differences between HashMap and HashTable
1. Thread safety
The main difference is that Hashtable is thread-safe, while HashMap is not.
The implementation methods of Hashtable all add the synchronized keyword to ensure thread synchronization, so the performance of HashMap is relatively higher. If there is no special requirement, we recommend using HashMap. In a multithreaded environment using HashMap need to use the Collections, synchronizedMap () method to get a thread-safe Collections.
Note:
Collections.synchronizedmap () implementation principle is the Collections defines a synchronizedMap inner classes, the class implements the Map interface, Synchronized is used to keep the thread synchronized when calling the method, actually using the HashMap instance we passed in, Simple said is the Collections. SynchronizedMap () method to help us in the operation of the HashMap added automatically synchronized to the realization of thread synchronization, similar to other Collections. SynchronizedXX method is also a similar principle.
2. Different for NULL
A HashMap can use NULL as a key, whereas a Hashtable does not allow NULL as a key
Although HashMap supports null values as keys, it is recommended to avoid using them as they can be very difficult to troubleshoot if they are accidentally used.
Note: A HashMap with a null key is always stored on the first node of the table array.
3. Inheritance structure
HashMap is an implementation of the Map interface. HashTable implements both the Map interface and the Dictionary abstract class.
4. Initial capacity and expansion
The initial size of a HashMap is 16, and the initial size of a Hashtable is 11, and the default fill factor for both is 0.75.
Capacity x 2 for HashMap capacity expansion. Capacity x 2+1 for Hashtable capacity expansion.
5. The two hash methods are different
Hashtable Computates a hash by modulating the length of the table array using the key’s Hashcode
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
The hashcode of the key is hashed twice to get a better hash value, and then the length of the table array is computed.
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}