Summary of knowledge points of HashMap in JDK7

Several important variables in HashMap

The default initial capacity must be the nth power of 2

The maximum capacity is used when the capacity passed in through the construction method is greater than it. It must be to the nth power of 2

Default load factor

It is used to store key value pairs. You can see that key value pairs are stored in the entry

The elements in the HashMap are saved with an entry array named table. The default size is 16

In JDK7, the key is treated differently when it is a string. There will be alternative hashing, but this has been deleted in jdk8

storage structure

Entry is a linked list structure, which not only contains key and value, but also points to the next

Put method

Firstly, the hashcode is processed through the hash method:

You can see that only some processing has been done on the hashcode value of the key. The value calculated through the hash will use the indexfor method to find the table subscript where it should be located:

This method is actually equivalent to table Length take mold.

When the key to be inserted is null, call putfornullkey method to process:

The putfornullkey method only starts traversal from the position of table [0], because the key is null and is only placed in the first position in the table with the subscript 0. If it is found that a key is null during traversal, it will replace the new value and return the old value to end; If no key is null, call the addentry method to add an entry:

You can see that the condition of resize in JDK7 has changed. Resize occurs only when size > = threshold and there is an entry in the slot in the table. That is, it is possible that although size > = threshold, the capacity will not be expanded until each slot has at least one entry. Also note that each resize will double the capacity

Finally, look at createentry, which saves the first entry in the bucket, creates a new entry and puts it in the first position, followed by the original entry. Here, the header insertion method is used to insert elements.

Get method

In fact, the get method is the same as the put method, how to put it and how to take it

When the key is null, go to table [0] to get it:

Otherwise, call the getentry method:

This method also calculates the subscript of the key through its hashcode, and then traverses the entry chain of the subscript. If the memory addresses of the key are equal (i.e. the same reference) or equals are equal, it indicates that it has been found

Hash principle

A. Equipower. No matter how many operations to obtain the hash value are performed, the hash value is fixed as long as the object remains unchanged. If the first fetch is different from the nth fetch, it will be very troublesome to use

B. Equivalence. If the equal method of two objects returns true, the hash value should also be the same. For example: if you store obja as a key in HashMap, and then create a new objb. In your opinion, objb and obja are the same thing (because they are equal), but you can't get anything from using objb to HashMap.

C. Mutual anisotropy. If the equal method of two objects returns false, the hash value may be the same, but it is better to be different. This is not necessary, but it will improve the performance of hash class operations (low collision probability).

Methods to solve hash collision:

HashMap adopts the chain address method, which has the advantage of no stacking, but the next pointer will occupy additional space

The difference between and HashMap in jdk8

In jdk8, it will still be based on the key Hashcode () calculates the hash value and uses the hash value to locate the key, but the difference is that when a conflict occurs, it will be handled by linked list and red black tree, When the number of nodes is small, use the linked list (stored with node), and when the number is large, use the red black tree (stored with treenode). At the same time, the nodes are not called entries, but are divided into nodes and treenodes. In the worst case, the time complexity of linked list lookup is O (n), while the red black tree is always o (log n), which will improve the efficiency of HashMap. A variable treeify is defined in the HashMap in jdk8_ Threshold, when the number of nodes > = tree_ When threshold - 1, HashMap will be stored in red black tree

summary

The above is the whole content of this article. I hope the content of this article can bring some help to your study or work. If you have any questions, you can leave a message.