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

What is the internal structure of HashMap and TreeMap? I believe many inexperienced people don't know what to do about it. Therefore, this paper summarizes the causes and solutions of the problem. Through this article, I hope you can solve this problem.

1. HashMap

1. The implementation of Map interface based on hash table. This implementation provides all optional mapping operations and allows the use of null values and null keys. The HashMap class is roughly the same as Hashtable except that it is out of sync and allows the use of null. This class does not guarantee the order of mappings, especially since it does not guarantee that the order is permanent

2. An instance of HashMap has two parameters that affect its performance: initial capacity and loading factor. Capacity is the number of buckets in the hash table, and the initial capacity is only the capacity of the hash table when it was created. The loading factor is a measure of how full a hash table can be before its capacity increases automatically. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehash (that is, the internal data structure is rebuilt), so that the hash table will have about twice the number of barrels.

Find the location of the bucket according to the hash value of the key keyword and the length of the buckets array. If the hash value of key is the same, the Hash conflict (that is, pointing to the same bucket) is added as the header node each time, and the first one is added at the end of the table.

The number of buckets in HashMap is the length of the array of 0-n in the following figure. The location where the first entry is stored is' bucket', and only one value can be stored in the bucket, that is, the head node of the linked list. Each node of the linked list is an added value (which attributes of the instance Entry of the HashMap internal class Entry will be described in detail later). It can also be understood in this way that an array of linked lists is stored in an entry type. The index location of the array is the index address of each bucket.

From the figure above, we can see that the hash table is composed of an array and a linked list. In an array with a length of 16, each element stores the head node of a linked list. So what are the rules for storing these elements in the array? In general, it is obtained through hash (key)% len, that is, the hash value of the element's key is obtained by modulating the length of the array. For example, in the above hash table, "1214012" is 28" 12108 ". So 12, 28, 108, and 140 are stored in the location of the array subscript 12.

Simple summary of HashMap:

1. HashMap is a linked array (an array that stores linked lists) to achieve query speed, and can quickly get the value corresponding to key.

2. The influencing factors of query speed are capacity and load factor, large capacity, small load factor, fast query speed and waste of space, and vice versa.

3. The index value of the array is (key keyword, hashcode is the hash value of key, the size of the len array): the value of hashcode%len determines that if the capacity is large and the load factor is small, the probability that the index is the same (the same index points to the same bucket) is small, and the query speed is fast if the linked list length is small, while the query speed is slower when the index is the same probability large linked list.

4. For HashMap and its subclasses, they use the hash algorithm to determine the storage location of the elements in the collection. When initializing HashMap, the system will create an Entry array of length capacity. The location where elements can be stored in this array is called bucket, and each bucket has its own specified index. The system can quickly access the elements stored in the bucket according to the index.

5. Each bucket in HashMap stores only one element (Entry object) at any time. Because the Entry object can contain a reference variable to point to the next Entry, it is possible that there is only one Entry in the bucket of the HashMap, but this Entry points to another Entry, thus forming a chain of Entry.

6. Through the above source code, it is found that HashMap treats key_value pairs as a whole (Entry object) at the bottom, which is an Entry object. When the system decides to store key_value pairs in HashMap, it does not consider the value in Entry at all, but only determines the storage location of each Entry according to the hash value of key.

A Node array is used in JDK1.8 to store data, but this Node may be a linked list structure or a red-black tree structure. if the hashcode of the inserted key is the same, then the key will also be located in the same cell of the Node array.

If there are no more than 8 key in the same grid, use the linked list structure to store. If there are more than eight, the treeifyBin function is called to convert the linked list to a red-black tree. So even if the hashcode is exactly the same, because of the characteristics of the red-black tree, it only takes O (log n) to find a particular element.

In other words, the worst time complexity of put/get operation is O (log n).

It should be noted that the object of key must correctly implement the Compare interface

II. TreeMap

The red-black tree is a nearly balanced binary search tree that ensures that the height difference between the left and right subtrees of any node does not exceed the lower of the two. Specifically, a red-black tree is a binary search tree (binary search tree) that satisfies the following conditions:

Each node is either red or black.

The root node must be black

The red node cannot be continuous (that is, neither the child nor the father of the red node can be red).

For each node, any path from that point to the null (end of the tree) contains the same number of black nodes.

When the structure of the tree changes (insert or delete operation), it often destroys the above condition 3 or condition 4, and needs to be adjusted to make the search tree meet the conditions of the red-black tree again.

2. The underlying layer of TreeMap is implemented using a red-black tree. For example, when a key-value key-value pair is placed in a TreeMap object, an Entry object is generated, which is a node of the red-black tree. In fact, this is the same as HashMap. An Entry object is a node, but these nodes are stored in different ways.

3, each Entry object will be stored according to the size of the key key according to the binary tree specification, so the data in TreeMap is sorted according to key from smallest to largest.

When the program adds a new node, it always starts with the root node of the tree and treats the root node as the current node. If the new node is larger than the current node and the right node of the current node exists, the right node is taken as the current node, and if the new node is smaller than the current node and the left child node of the current node exists, the left child node is used as the current node. If the new node is equal to the current node, the current node is overwritten with the new node, and the cycle ends until the left and right child nodes of a node do not exist, and the new node is added as a child of that node. If the new node is larger than that node, it is added as a right child node. If the new node is smaller than that node, it is added as a left child node.

After reading the above, have you mastered the internal structure of HashMap and TreeMap? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

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.