JDK1. Implementation of HashMap in 8

JDK1. The implementation of HashMap in 8 is similar to jdk1 The implementation in 7 is very different. Jdk1 is analyzed below The implementation in 8 mainly depends on the put and get methods.

The method is not initialized when it is constructed, but is initialized when it is put for the first time

The main logic of the putval method is as follows:

1. If the array has not been initialized (the array length is 0), initialize it first

2. Calculate the hash value of the key through the hash method, and then calculate the position that should be placed in the array

3. If the location is empty, place it here directly

4. If the location is not empty and the element is a red black tree, insert it

5. If it is a linked list, it will traverse the linked list. If an equal element is found, it will be replaced. Otherwise, it will be inserted at the end of the linked list

6. If the length of the linked list is greater than or equal to 8, the linked list will be turned into a red black tree

1. Calculate hash position

2. See if the first element is to be found. If it is, it will be returned. Otherwise, it will be traversed

Capacity expansion is to move the elements of the old array to the new array

Summary:

1. The bottom layer of HashMap is realized by array + bidirectional linked list + red black tree

2. When inserting elements, first calculate the hash value of the key through a hash method, and then calculate the position to be inserted

3. If the location is empty, it will be inserted directly (packaged as node)

4. If the position has a value, it is traversed in turn. The comparison rule is that if the hash value is the same and the key value is the same, the old value is replaced with the new value and the old value is returned.

5. If the element at this position is a red black tree structure, the same is true. Search, replace if found, and insert if not found.

Key points:

JDK1. HashMap and jdk1 in 8 There are many differences in 7

1. Red black tree is introduced in 1.8, but not in 1.7

2. The element in 1.8 is inserted at the end of the linked list, while the new element in 1.7 is inserted at the head of the linked list

3. During capacity expansion, there will be no dead cycle in 1.8, but it is easy to occur in 1.7, and the linked list will not be inverted