The approximate data structure of a HashMap:

Put () and get() in HashMap

Map. put(k,v) implementation principle

  1. First encapsulate k and V into Node objects.
  2. Its underlayer then calls K’s hashCode() method to get the hash value.
  3. The hash function/hash algorithm converts the hash value to the index of the array. If there are no elements at the index position, Node is added to that position. If there is a linked list (hash collision) at the corresponding position of the subscript. At this point, I’m going to take k and equal for each node on the list. If all equals methods return false, the new node is added to the end of the linked list. If one of equals returns true, the value of that object will be overwritten.

Map.get (k) implementation principle

  1. K’s hashCode() method is called to derive the hash value, which is converted to the array’s subscript by the hash algorithm.
  2. After the hash algorithm is converted to the subscript of the array, it can quickly locate to a certain location by the array subscript. If there is nothing at this location, null is returned. If there is a uni-linked list at this location, it equals K and K for each node on the uni-linked list. If all equals methods return false, get returns null. If K equals to K returns true, then the value of the node is the value we are looking for, and the get method eventually returns the value.

Why random add and delete, query efficiency are very high reason is?

Reason: Add and delete is completed in the linked list, and the query only scan part, then high efficiency.

Note: The key of the HashMap collection calls two methods, hashCode and equals, which need to be overridden.

Why do elements placed in the key part of the hashMap collection need to override equals?

By default, equals compares the memory addresses of two objects

Overview of hashing collisions

  • In calling the HashMapput(key k,value v)Method, if the hash values of keys are equal, then a hash collision (collision) occurs.
  • At this point, ifequals()If the values are equal, the keys are the same. If the elements are the same, the overwrite operation is performed. ifequals()If not, a linked list is formed and appended to the end of the list.
  • When the length of the linked list is equal to 8, the structure is optimized as red-black tree (Jdk1.8 is starting to optimize for red-black trees), when the remove(key k) method is called to delete the element, when there are six remaining elements, the linked list structure is returned;

How do I avoid hash collisions

To avoid hash collisions, try to make the hash values of keys different. The hash values of keys are closely related to the map capacity. A larger capacity is less likely to cause collisions.

Therefore, an effective way to avoid hash collisions is to expand the map. When the map size changes, all the hash values of keys are recalculated using reHash