Low level implementation in jdk1.7 (low level based on array + linked list)
When we new HashMap(), we underneath create a one-dimensional array Entry[] table with a default length of 16. When we call map.put(key1,value1) to add data to a HashMap:
First, call the class hashCode() of key1 to calculate the hash value of key1. After bit operation with the hash value of key1 and the maximum index of array, obtain the position in the Entry array:
If the data in this position is empty, key1-value1 is added successfully.
If the data at this location is not empty (meaning that one or more data already exists at this location), compare the hash value of key1 with that of one or more data that already exists:
If the hash value of key1 is different from that of existing data, key1-value1 is added successfully.
If the hash of key1 is the same as the hash of one of the existing data, the comparison continues: call equals() of the class where key1 is located:
If equals() returns false, key1-value1 is added successfully;
If equals() returns true, replace value2 with value1.
Note that if the original location has data, key1-Value1 and the original data are stored in a linked list.
Is constantly in the process of adding to capacity problems, when the array size is greater than the array length times existing load factor (such as 16 * 0.75, the default load factor of 0.75), will be for array capacity, in order to reduce the hash conflict (hash conflict refers to the hash function to calculate out the address of the occupied by other elements), improve the query efficiency. By default, the capacity is expanded twice and the original data is copied.
The underlying implementation process of JDK1.8 (base on array + linked list + red-black tree)
New HashMap() does not create an array of length 16. When we call put(), we check whether the array exists. If not, we create a Node[] array of length 16. The next steps are similar to JDK1.7. Finally, when the number of linked list elements in an index position is greater than 8 and the current array length is greater than 64, all data in the index position is stored in a red-black tree instead.
In JDK1.7, hash collisions will inevitably occur even if the array capacity is greater than the existing length of the array multiplied by the load factor. Therefore, red-black trees are introduced in JDK1.8 to further reduce hash collisions and improve query efficiency.
Red-black tree is a self-balanced binary search tree and a data structure, which is typically used to implement associative arrays. The root node must be black, and every other node must be either red or black.
If the key is of its own object type, you must override hashCode and equals. Otherwise, duplicate keys cannot be removed.
left
