HashTable
HashTable fails fast, and values in the container are not allowed to be changed while Iterator is iterating.
However, HashTable is thread-safe because, inside HashTable, each method is locked with a Synchronized (pessimistic) lock. Only one thread can perform operations on HashTable at a time, and all other threads need to queue. Its concurrency is insufficient and can easily cause massive blocking.
So what’s his data structure like? Its data structure is the same as that of HashMap in JDk1.7, using arrays plus lists. All nodes are entities, and the architecture is as follows
When the capacity of a HashTable is insufficient, the capacity of a HashMap is multiplied by two times. This is different from the capacity of a HashMap, which is doubled
int newCapacity = (oldCapacity << 1) + 1;
Copy the codeWhy does he not allow null keys? Inside the HashTable, he makes a special judgment that inserting null keys raises an exception
Null.hashcode () also throws an NPE when key is empty
Now, that’s not the final reason, but the reason is that in a multithreaded environment, if you use get and you get null, you don’t know if it doesn’t exist or if it’s already null, so you can’t use containsKey to tell if it exists, why can’t you tell if it exists? During that time, the HashTable could be accessed by as many threads as possible, the thread could delete the key, or it could simply not exist. Therefore, an empty key-value cannot be inserted.
And what is its default capacity? As can be seen from the source code, its default capacity size is 11. The load factor is 0.75 again
The other thing I’m interested in is how PUT works, so let’s look at how PUT works.
The principle of PUT is to locate an Entry node based on the key. If the node has a chain structure, the system traverses the list to determine whether the key is equal to the key. If no key is equal, the node to be inserted is inserted into the head of the list. If the capacity is insufficient, expand the capacity.
Get is actually simpler than PUT. It is used to locate the linked list by key, and then traverse the list looking for data. If no data is found, return null
Collections.synchronizedMap
If we pass mutex in the constructor, we use the mutex we passed in. If we pass no mutex, we use the current object lock.
Then add synchronized to all the methods, similar to HashTable
ConCurrentHashMap
This is a big deal, a very common interview question, involving high concurrency. Compare his differences between JDK1.7 and JDK1.8
jdk1.7
The differences between the two versions are mainly in data structure and lock. In JDK1.7, the data structure is designed by segment array + HashEntry array + linked list, and hash conflicts are handled by zipper method.
Next look at the constructor to see what the default capacity and load factor are. In jdk1.7, the load factor is 0.75 and the default capacity is also 16.
So how does PUT work, and how does it ensure high concurrency? Insert into the segment array [insert into the segment array] [insert into the segment array] [insert into the segment array] [insert into the segment array] If the HashEntry is empty, insert it directly. If it is not empty, loop the list and insert the node into the head of the list. Likewise, ConCurrentHashMap does not support null-valued key-values.
The principle of GET is relatively simple. Based on the hash value of the key, locate the HashEntry in the specific Segmen node and then find the node from the linked list. The Get method of ConCurrentHashMap is very efficient and does not need to be locked at all times
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
// Compute the hash based on the key
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
// Locate the HashEntry node in the specific segment node
if((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) ! =null &&
(tab = s.table) ! =null) {
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)))
return e.value;
}
}
return null;
}
Copy the codejdk1.8
ConCurrentHashMap is an array, a list, and a red-black tree, which is used in jdk1.8. In addition, the original segmentalized lock was replaced by CAS + Synchronized lock, and other parts remained unchanged.
CAS can be found at juejin.cn/post/684490…
So what is the expansion method and the initial capacity? The default initial capacity is still 16
In the transfer method, there is a sentence like this
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n <<1];
Copy the codeIt can be seen that the expansion method has also become twice the original. However, if multiple threads need to expand capacity at the same time, these threads help each other to expand capacity.
The underlying implementation of PUT is a bit more complicated. First, the Node is located according to the hash of the key. If the Node is null, the spin is inserted; if it is not null, Synchronized is used to lock the Node. If it is a linked list, it is inserted in the way of a linked list, and the tail is inserted. If it is a linked list insert, then after the insert is completed, check whether the number of nodes is greater than or equal to 8. If the number is greater than or equal to 8, you need to turn the linked list into a red-black tree. Then check whether the number of nodes in the container exceeds the threshold. If yes, expand the capacity.
If the key and hash of a Node are equal to the key and hash to be searched, the Node will be returned directly. Otherwise, the binary tree or the linked list will be traversed, and null will be returned.
Compared to THE ConCurrentHashMap in JDK1.7, the lookups in JDK1.8 are much more efficient because red-black trees are introduced