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

HashMap, Hashtable, ConcurrentHashMap what is the difference between the three, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain in detail for you, people with this need can come to learn, I hope you can gain something.

HashTable

The underlying array + linked list implementation, neither key nor value can be null, thread-safe, the way to achieve thread-safety is to lock the whole HashTable when modifying data, which is inefficient, and ConcurrentHashMap has made relevant optimizations.

Initial size is 11, capacity expansion: newsize = olesize*2+1

The method for calculating index: index = (hash & 0x7FFFFFFF)% tab.length

HashMap

Underlying array + linked list implementation, can store null keys and null values, thread is not safe

Initial size is 16, capacity expansion: newsize = oldsize*2,size must be n power of 2

The expansion is aimed at the entire Map. With each expansion, the elements in the original array are recalculated in turn and re-inserted.

It is possible to determine whether or not to expand the capacity after inserting the element. If the capacity is expanded after insertion, if it is not inserted again, invalid expansion will occur.

When the total number of elements in Map exceeds 75% of the Entry array, the expansion operation is triggered. In order to reduce the length of the linked list, the elements are allocated more evenly.

Index calculation method: index = hash & (tab.length-1)

The initial value of HashMap also takes into account the loading factor:

Hash conflict: after several Key hash values are modeled according to the size of the array, if they fall on the same array subscript, they will form an Entry chain, and the search for Key needs to traverse each element on the Entry chain to perform equals () comparison.

Loading factor: to reduce the probability of hash conflicts, expansion is triggered by default when the key-value pair in HashMap reaches 75% of the array size. Therefore, if the estimated capacity is 100, you need to set the array size of 100 Universe 0.75 to 134.

Space for time: if you want to speed up the Key lookup time, you can further reduce the load factor and increase the initial size to reduce the probability of hash conflicts.

Both HashMap and Hashtable use the hash algorithm to determine the storage of their elements, so the hash table for HashMap and Hashtable contains the following attributes:

Capacity: the number of buckets in the hash table

Initialization capacity (initial capacity): the number of buckets when the hash table is created. HashMap allows initialization capacity to be specified in the constructor.

Size (size): number of records in the current hash table

Load factor (load factor): load factor equals "size/capacity". The load factor is 0, which represents an empty hash table, 0.5 represents a half-full hash table, and so on. The light-loaded hash table has the characteristics of fewer conflicts and suitable for insertion and query (but it is slow to use Iterator iterative elements)

In addition, there is a "load limit" in the hash table. The "load limit" is a value of 0: 1, and the "load limit" determines the maximum filling degree of the hash table. When the load factor in the hash table reaches the specified "load limit", the hash table automatically multiplies the capacity (the number of buckets) and redistributes the original objects into the new bucket, which is called rehashing.

The constructors for HashMap and Hashtable allow you to specify a load limit, and the default "load limit" for HashMap and Hashtable is 0.75, which indicates that rehashing occurs in the hash table when the hash table's 3x4 table has been filled.

The default value of load limit (0.75) is a compromise between time and space costs:

A higher "load limit" can reduce the memory space occupied by hash tables, but increase the time cost of querying data, and queries are the most frequent operations (queries are used by both the get () and put () methods of HashMap)

A lower "load limit" improves the performance of querying data, but increases the memory overhead occupied by hash tables.

Programmers can adjust the "load limit" value according to the actual situation.

ConcurrentHashMap

The bottom layer is realized by segmented array + linked list, which is thread safe.

By dividing the entire Map into N Segment, you can provide the same thread safety, but the efficiency is increased N times, and the default is 16 times higher. (read operations are unlocked, and since the value variable of HashEntry is volatile, the latest value is guaranteed to be read.)

The synchronized of Hashtable is for the whole Hash table, that is, each time the whole table is locked and the thread is exclusive, and ConcurrentHashMap allows multiple modification operations to be carried out concurrently. The key lies in the use of lock separation technology.

Some methods need to span segments, such as size () and containsValue (). They may need to lock the entire table instead of just one segment, which requires locking all segments sequentially, and then releasing locks for all segments sequentially after the operation is completed.

Capacity expansion: intra-segment capacity expansion (the elements in the segment are triggered by more than 75% of the corresponding Entry array length, and the entire Map will not be expanded). Check whether capacity expansion is needed before insertion to effectively avoid invalid capacity expansion.

Both Hashtable and HashMap implement the Map interface, but the implementation of Hashtable is based on Dictionary abstract classes. Java5 provides ConcurrentHashMap, which is an alternative to HashTable and is more extensible than HashTable.

Based on the hash idea, HashMap realizes the reading and writing of data. When we pass the key-value pair to the put () method, it invokes the hashCode () method of the key object to calculate the hashcode, and then finds the bucket location to store the value object. When you get an object, you find the correct key-value pair through the equals () method of the key object, and then return the value object. HashMap uses a linked list to solve the collision problem, and when a collision occurs, the object is stored in the next node of the linked list. HashMap stores key-value pairs in each linked list node. When two different key objects have the same hashcode, they are stored in a linked list at the same bucket location, and the key-value pair can be found through the equals () method of the key object. If the size of the linked list exceeds the threshold (TREEIFY_THRESHOLD,8), the linked list is transformed into a tree structure.

In HashMap, null can be used as a key. There is only one such key, but one or more keys can have a value of null. When the get () method returns a null value, it can either indicate that there is no key in the HashMap, or that the value corresponding to the key is null. Therefore, in HashMap, the get () method cannot be used to determine whether a certain key exists in the HashMap, but should be determined by the containsKey () method. In Hashtable, neither key nor value can be null.

Hashtable is thread-safe, its methods are synchronous, and can be directly used in multithreaded environments. While HashMap is not thread-safe, in a multithreaded environment, the synchronization mechanism needs to be implemented manually.

Another difference between Hashtable and HashMap is that HashMap's Iterator is a fail-fast iterator, while Hashtable's enumerator iterator is not fail-fast 's. So when another thread changes the structure of the HashMap (adding or removing elements), the ConcurrentModificationException will be thrown, but the iterator's own remove () method removing the element will not throw a ConcurrentModificationException exception. But this is not a certain behavior, it depends on JVM.

First take a look at the simple class diagram:

You can see from the class diagram that ConcurrentHashMap has one more class Segment than HashMap in the storage structure, while Segment is a reentrant lock.

ConcurrentHashMap uses lock segmentation technology to ensure thread safety.

Lock segmentation technology: first divide the data into segments of storage, and then assign a lock to each piece of data. When a thread occupies the lock to access one segment of data, the data of other segments can also be accessed by other threads.

ConcurrentHashMap provides a different locking mechanism than Hashtable and SynchronizedMap. The locking mechanism used in Hashtable locks the entire hash table at a time so that only one thread can operate on it at a time, while in ConcurrentHashMap it locks one bucket at a time.

By default, ConcurrentHashMap divides the hash table into 16 buckets, and common operations such as get, put, remove, and so on, lock only the buckets currently needed. In this way, there used to be only one thread to enter, but now 16 write threads can execute at the same time, and the improvement in concurrent performance is obvious.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

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.