preface

For the record, this article uses JDK1.8

List sets, hash sets, Map sets, red black trees, etc.

  • The Collection overview
  • List collection is as simple as that.
  • Map sets, hash tables, and red-black trees

This article focuses on hashMaps and covers some comparisons to HashTables

It is best to have a little data structure foundation before reading this article:

  • Java implements one-way linked lists
  • Stacks and queues are that simple
  • Binary trees are that simple

Of course, if there is something wrong, please bear with me and correct me in the comments

First, HashMap analysis

First look at what the comment at the top of the HashMap says:

Let’s look at the class inheritance diagram for HashMap:

Let’s look at the attributes of the HashMap:

There are several member attributes:

Take a look at one of the inner nodes of hashMap:

We know that the underlying Hash is a Hash table, and in Java Hash tables are implemented via arrays + linked lists

A simple look at the put method proves this: array + linked list -> hash

We can summarize the HashMap briefly:

  • Unordered, null allowed, asynchronous
  • The bottom layer is implemented by hash tables (hash tables)
  • The initial capacity and load factor have a big effect on the HashMap. Setting it too small is bad, and setting it too large is bad

1.1HashMap constructor

There are four constructors of a HashMap:

In the last line of the constructor above, we’ll see that tableSizeFor() is called.

This is the bit operation algorithm, the specific process can be referred to:

  • www.cnblogs.com/loading4/p/…
  • Blog.csdn.net/fan2012huan…

Why is the integer power of 2 assigned to threshold?

  • The threshold member variable is the threshold that determines whether the hash table should be rehashed. Its value should be:capacity * load factorJust right.

In fact, this is just an initialization, when the hash table is created, it will be reassigned:

As for the other construction methods are similar, I won’t go into details here:

1.2 put method

The put method is at the heart of a HashMap.

Let’s see how it evaluates the hash:

Why do you do that? We usually just hash key as a value, what does xor do?

Let’s see:

We store it in the hash table according to the hash value of the key. The default initial capacity of our table is 16, and we put it in the hash table, which is 0 to 15. So TAB [I = (n-1) hash]. It can be found that only the last 4 bits of the key are valid ~ if the hash value of our key changes a lot and the hash value of our key changes a little. Just go ahead and do the ampersand, which will result in a lot of the same Hash values.

The designer also calculated the high part of the hash value of key (xOR operation with the high 16 bits, so that when doing the & operation, the low part is actually the combination of the high part and the low part), which increases the randomness and reduces the possibility of collision and conflict!

Let’s see how the process works:

New value overwrites old value, returns old value test:

Next we look at the resize() method, which is called at initialization and also when the hash element is greater than the capacity * load factor.

1.3 the get method

Let’s see how getNode() is implemented:

1.4 the remove method

Let’s look at the implementation of removeNode() :

Compare HashMap with Hashtable

The storage structure and implementation are basically the same. The biggest difference from HashMap is that it is thread-safe, and it does not allow keys and values to be null. Hashtable is an obsolete collection class and is not recommended for use in new code. It can be replaced with HashMap for non-thread-safe applications and ConcurrentHashMap for thread-safe applications

Hashtable = Hashtable = Hashtable

  • Blog.csdn.net/panweiwei19…
  • Blog.csdn.net/panweiwei19…

Four,

The underlying HashMap in JDK8 is an array + a hash list + a red-black tree

The hash table has a load factor property, when the load factor * initial capacity is less than the hash table element, the hash table will be doubled!

The default value of the load factor is 0.75, which is not good for the performance of our HashMap whether it is initially large or small

  • A large initial load factor reduces the number of hash rehashes, but it also increases the possibility of hash collisions (hash collisions are also a performance-costly operation, requiring operation linked lists (red-black trees)!
  • A smaller initial load factor reduces the possibility of hash collisions, but at the same time, the number of expansions may increase!

The default initial size is 16, which also has an effect on our HashMap whether the initial size is large or small:

  • If the initial capacity is too large, our speed will be affected throughout
  • If the initial capacity is too small, the number of hash rehash (expansion times) may become too large, and expansion is also a very costly matter

From the source code, we can find that: HashMap does not directly take the hash value of the key. It will xOR the high 16 bits of the key hash value, which increases the randomness of the elements when we put them into the hash table.

It is also worth noting that the bucket does not turn into a red-black tree with 8-bit elements, it also has to have our hash table capacity greater than 64

Tomorrow, if nothing goes wrong, we’ll probably write TreeMap, so stay tuned to ~~~~

Open source project (6 K STAR) :Github.com/ZhongFuChen…

If you want to follow my updated articles and shared dry goods in real time, you can search Java3y on wechat.

The content of the PDF document is typed by hand. If you don’t understand anything, you can ask me directly (the official account has my contact information).