Shulou(Shulou.com)06/01 Report--

This article shows you the similarities and differences of ConcurrentHashMap in Java7 and. The content is concise and easy to understand. It will definitely brighten your eyes. I hope you can gain something through the detailed introduction of this article.

In Java 8, ConcurrentHashMap, a commonly used tool class, has been greatly upgraded, and the previous version of Java 7 has been adjusted and changed in many ways.

One: Java 7 version of ConcurrentHashMap

From the figure, we can see that Segment segmentation is carried out within the ConcurrentHashMap, and Segment inherits ReentrantLock, which can be understood as a lock. Each Segment is locked independently of each other and does not affect each other. Compared with the previous Hashtable, which needs to lock the whole object for each operation, it greatly improves the concurrency efficiency. Because its lock and lock are independent, rather than the whole object has only one lock.

The underlying data structure of each Segment is similar to that of HashMap, still a zipper structure consisting of arrays and linked lists. By default, there are 16 Segment in all, so you can support up to 16 concurrent operations of threads at the same time (operations are distributed on different Segment). The default value of 16 can be set to other values during initialization, but once initialization is confirmed, it cannot be expanded.

Two: Java 8 version of ConcurrentHashMap

In java 8, ConcurrentHashMap is almost completely rewritten, and the amount of code has changed from more than 1000 lines in Java 7 to more than 6000 lines now, which greatly improves the difficulty of reading the source code.

There are three types of nodes in the figure.

The first is the simplest, and the empty position represents that there are currently no elements to fill.

The second is the zipper structure which is very similar to HashMap, in which the first node is filled in each slot, but if the same Hash-value is calculated later, it will be extended in the form of a linked list.

The third structure is the red-black tree structure, which is not found in the ConcurrentHashMap of Java 7.

When the length of the linked list in the second case is greater than a certain threshold (the default is 8) and meets a certain capacity requirement, ConcurrentHashMap will convert the linked list from the form of linked list to the form of red-black tree in order to further improve its search performance.

Because of the characteristic of self-balance, that is, the height of the left and right subtrees is almost the same, its search performance is similar to that of binary search, and the time complexity is O (log (n)). In contrast, the time complexity of the linked list is different. If the worst happens, you may need to traverse the entire linked list to find the target element. The time complexity is O (n), which is much larger than the O (log (n)) of the red-black tree. Especially when there are more and more nodes, the advantage of O (log (n)) will be more obvious.

ConcurrentHashMap introduces the red-black tree, the advantage is to avoid conflicts in extreme cases the linked list becomes very long, in the query, the efficiency will be very slow. The red-black tree has the characteristic of self-balance, so even in extreme cases, the query efficiency can be guaranteed at O (log (n)).

2.2 important source code for Java 8 version of ConcurrentHashMap

Let's go deep into the source code analysis. Since the Java 7 version is out of date, we focus on the source code analysis of the Java 8 version.

2.1.1 Node node static class Node implements Map.Entry {final int hash; final K key; V value; Node next; / /.}

Each Node is in the form of key-value, and the value is decorated with volatile to ensure visibility, while there is an internal next pointer to the next node to facilitate the generation of linked list structures.

2.1.2 Source Code Analysis of put method

The core of the put method is the putVal method:

Final V putVal (K key, V value, boolean onlyIfAbsent) {if (key = = null | | value = = null) {throw new NullPointerException ();} / / calculate the hash value int hash = spread (key.hashCode ()); int binCount = 0; for (Node [] tab = table;;) {Node f; int n, I, fh / / if the array is empty, initialize if (tab = = null | | (n = tab.length) = = 0) {tab = initTable () } / / find the array subscript else if ((f = tabAt (tab, I = (n-1) & hash)) = null) {/ / if the location is empty, put the new value if (casTabAt (tab, I, null, new Node (hash, key, value, null)) {break in the way of CAS. }} / / the hash value equals MOVED represents the case that else {V oldVal = null has a value at the expansion else if ((fh = f.hash) = = MOVED) {tab = helpTransfer (tab, f);} / / slot point / / lock the current slot point with synchronized to ensure concurrency security synchronized (f) {if (tabAt (tab, I) = = f) {/ / if it is in the form of a linked list if (fh > = 0) {binCount = 1 / / traversing the linked list for (Node e = f;; + + binCount) {K ek / / if the key is found to exist, determine whether it needs to be overwritten. Then return if (e.hash = = hash & & ((ek = e.key) = = key | | (ek! = null & & key.equals (ek) {oldVal = e.val If (! onlyIfAbsent) {e.val = value;} break;} Node pred = e / / the key was not found at the end of the linked list, indicating that it did not exist before, so the new value was added to the last if ((e = e.next) = = null) {pred.next = new Node (hash, key, value, null) of the linked list. Break;} / / if it is in the form of a red-black tree else if (f instanceof TreeBin) {Node p; binCount = 2 / call the putTreeVal method to add data if to the red-black tree ((p = (TreeBin) f) .putTreeVal (hash, key, value)! = null) {oldVal = p.val If (! onlyIfAbsent) {p.val = value }} if (binCount! = 0) {/ / check whether the condition is met and convert the linked list to the form of a red-black tree The default TREEIFY_THRESHOLD threshold is 8 if (binCount > = TREEIFY_THRESHOLD) {treeifyBin (tab, I) The return of} / / putVal is the old value before it was added, so return oldVal if (oldVal! = null) {return oldVal;} break;} addCount (1L, binCount); return null;}

It can be seen that the method will gradually make different treatments according to whether the current slot point is initialized, empty, capacity expansion, linked list, red-black tree and so on.

2.1.3 get source code analysis public V get (Object key) {Node [] tab; Node e, p; int n, eh; K ek; / / calculate hash value int h = spread (key.hashCode ()) / / if the whole array is empty or the current slot data is empty, the value corresponding to key does not exist. Return null if ((tab = table)! = null & & (n = tab.length) > 0 & (e = tabAt (tab, (n-1) & h)! = null) {/ / determine whether the header node is the node we need. If so, return if ((eh = e.hash) = = h) {if ((ek = e.key) = = key | | (ek! = null & & key.equals (ek) return e.val } / / if the hash value of the header node is less than 0, which means it is a red-black tree or is expanding, use the corresponding find method to find else if (eh

< 0) return (p = e.find(h, key)) != null ? p.val : null; //遍历链表来查找 while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null;} 计算 Hash 值，并由此值找到对应的槽点； 如果数组是空的或者该位置为 null，那么直接返回 null 就可以了； 如果该位置处的节点刚好就是我们需要的，直接返回该节点的值； 如果该位置节点是红黑树或者正在扩容，就用 find 方法继续查找； 否则那就是链表，就进行遍历链表查找。 三：对比Java7 和Java8 的异同和优缺点3.1 数据结构 Java 7 采用 Segment 分段锁来实现，而 Java 8 中的 ConcurrentHashMap 使用数组 + 链表 + 红黑树。

3.2 degree of concurrency

In Java 7, each Segment is locked independently, and the maximum number of concurrency is the number of Segment. The default is 16.

But in Java 8, the lock granularity is finer, and ideally the number of table array elements (that is, the array length) is the maximum number of concurrency it supports, and the degree of concurrency is higher than before.

3.3 principles for ensuring concurrency security

Java 7 uses Segment segmented locks for security, while Segment inherits from ReentrantLock.

Java 8 abandoned the design of Segment and adopted Node + CAS + synchronized to ensure thread safety.

3.4 encounter Hash collision

Java 7 uses the zipper method, which is in the form of a linked list, when it comes to Hash conflicts.

Java 8 first uses the zipper method to convert the linked list into a red-black tree when the length of the linked list exceeds a certain threshold, so as to improve the search efficiency.

3.5 query time complexity

The time complexity of Java 7 traversing the linked list is O (n), where n is the length of the linked list.

If Java 8 becomes traversing a red-black tree, the time complexity is reduced to O (log (n)), where n is the number of nodes in the tree.

The above is what the similarities and differences between ConcurrentHashMap and Java7 are. Have you learned any knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.