Author: Zhang Fengzhe links: www.jianshu.com/p/b638f19ae… Source: Jane Book

preface

HashMap is a commonly used collection in Java, and some ideas of HashMap are helpful for us to solve some problems in business at ordinary times. Based on this, this blog will analyze the underlying design ideas of HashMap, and write a mini version of HashMap!

Thoughts on HashMap

HashMap underlying data structure

First, as the figure shows, a HashMap has three elements: a hash function + an array + a singlelinked list

Second, what do I need to think about for hash functions?

Be fast, for a given Key, be able to quickly compute the index in the array. So what is fast enough? Bit operations, obviously!

It has to be evenly distributed, it has to have fewer collisions. To put it bluntly, we want the hash function to distribute the data evenly across the array, and we don’t want a large number of data collisions to make the list too long. So how do we do that? It also uses bit operation to hash the data obtained by the hash function by moving the binary bits of the data, thus reducing the probability of collision.

What if there’s a collision? The figure above illustrates how the JDK’s HashMap handles hash collisions through singly linked lists. So is there another way to do this? So, for example, if there’s a conflict, let’s write down the position of the conflict as index, and then add a fixed step, index+step, find that position, and see if there’s still a conflict, and if there’s still a conflict, keep adding the fixed step along the same lines. This is called linear probing to resolve Hash collisions!

Write a mini-version of HashMap to understand this

Defines the interface

interface

Define an interface that exposes fast access methods.

Notice that the MyMap interface defines an internal interface Entry.

Interface implementation

MyHashMap definition

One of the elements of a HashMap is an array, and of course here we have to define the array, the initial size of the array, and the threshold for expansion.

Look at the construction of MyHashMap

A constructor

What’s there to say about constructors?

If you look closely, you will see that the “facade mode” is used here. The two constructors here actually point to the same object, but they expose two faces!

Entry

Entry

One of the elements of HashMap, single linked lists, is here!

How do you implement put

put

First, to consider whether to expand?

Does the number of entries in the HashMap (arrays and all entries in a single linked list) reach the threshold?

Second, if the expansion means that a new Entry[] is generated, it must be hashed again.

Third, calculate the position in Entry[] based on the Key. After positioning, if the element in Entry[] is null, it can be put into the list. If it is not empty, then the single list must be traversed, either updating the value or forming a new Entry to “squeeze” the single list!

The hash function

Hash function provided by MyHashMap

Hash function provided by the JDK’s HashMap

In order to hash evenly, you need to perform binary bit operations.

Resize and rehash

resize/rehash

As you can see, for HashMap, frequent resize/rehash operations will affect performance.

The resize/rehash process is a process in which the array becomes larger and the entry elements in the original array are put into the new array one by one. Note that some state variables are changed.

Get to realize

get

Get is simple, just use == or equals to check if the list is traversed.

The Test Test

Access using MyHashMap

The results

result

OK, a mini-version of HashMap is written. Did you learn?

The Path to Advanced JAVA Architecture