Introduction to HashMap

This is the first article I participated in beginners’ introduction

The data structure
An array of

A HashMap is a data structure composed of arrays and linked lists

Each space in the array stores an instance of the k-v structure, called Entry in previous JAVA7 versions and Node in today’s widely used JAVA8

The list

Why do you use linked lists?

Because the put operation needs to hash the subscript value based on the key value. But using the hash, you get the same value. So we use the linked list structure.

So the indices that compute the same value are all on the same linked list.

The Node structure

​

Insert the way
The first interpolation

Prior to Java8, header interpolation was used, and the newly inserted value replaced the original value, which was pushed to the linked list. In this way, the data inserted later can be found more quickly, indicating the efficiency of the search.

But the problem is that when you do the same map with different threads and the elements are expanded and inserted from the head you get circular lists. It’s going to loop forever.

The tail interpolation

Tail insertion in java8 uses red-black trees to avoid circular lists because they start at the tail and retain the original order when expanding.

capacity

Capacity expansion refers to the resize operation when the capacity of an index group reaches a certain number.

Two more key parameters

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

Alternative interpretation of load factors:

The current capacity is 100. When the storage capacity reaches 76, you need to resize the storage capacity.

How to increase
  • Capacity expansion: Create an empty array of entries. Capacity expansion is twice the original length
  • ReHash: Iterates through the original Entry array to ReHash all the entries into the new array
The cause of the ReHash

The rules of the hash change as the length changes

HashCode(key) & (len -1) = index

Thread safety

HashMap is thread-unsafe and ConcurrentHashMap is used in thread-safe cases.

ConcurrentHashMap uses the concept of segmented locking for security and improved performance.