structure

  • A data structure consisting of arrays and linked lists. 1.8 Linked lists may be upgraded to red-black trees.
  • Each place in the array holds an instance of key-value. Java7 is called Entry, and Java8 is called Node.
  • Put calculates the array position of an index based on the hashcode of the key.
  • When you put it, if you compute the same index, it will form a linked list at the index position.

How do I insert a new Node?

To calculate the index

  • Calculate inedex: index = HashCode (Key) & (length-1).
  • The capacity of hashMap is the power of 2, because then all bits of the binary representation of Length-1 are 1, and the calculated index is equivalent to the value of the next few bits of HashCode, so as long as the input HashCode is evenly distributed, the index is evenly distributed.

JDK1.7 head

  • The new value replaces the original value, and the original value is pushed into the list.
  • Multi-threaded concurrent operations have an infinite loop.

JDK1.8 tail plug

  • Avoid multi-threaded loops in linked list cases. The reason is that after expansion and transfer, the order of the linked list remains unchanged and the reference relationship of the previous node remains.
  • Red black tree case.

When is a red black tree

The list length is greater than 8

Expansion process

Increase the timing

  • Capacity: indicates the current length of the HashMap.
  • LoadFactor: LoadFactor. The default value is 0.75f.

For example, if the current capacity is 100, it needs to be expanded when it is 76

Expansion process

  • Capacity expansion: Create a new Node array that is twice as long.
  • ReHash: Iterates through the original Node array, ReHash all nodes into the new array.

Why does overriding equals() require overriding the hashCode() method

In a HashMap, the index position is determined using hashCode. So identical objects must return the same hashCode(), and different objects return different hashCode();

Thread-safe Map

Even though 1.8HashMap does not have an infinite loop, it is not thread-safe because its GET/PUT methods do not have synchronization locks.

HasHtable

Synchronized all fields, now generally not used.

Collections.SynchronizedMap

Taking a HashMap parameter wraps all methods as synchronized, which has the same performance as Hashtable. The advantage, however, is that you can transform a non-thread-safe Map into a thread-safe Map.

ConcurrentHashMap

JDK1.7 implements Segment + HashEntry + ReentrantLoc using segmentlock. ConcurrentHashMap is an array of segments (default length: 16). Each Segment contains a HashEntry array, so it can be considered a HashMap. A Segment is locked by inheritingreentrantLock, so every Segment that needs to be locked is locked. Thus, as long as each Segment is thread-safe, we can achieve global thread-safe.

JDK1.8 uses Node arrays + synchronized + volatile CAS

Why did JDK1.8 upgrade to red-black tree

To be updated