Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

HashMap data structures and features

We have been using HashMap for a long time and know that it is thread-unsafe. So why is it thread-unsafe? This article starts with the data structure and features of HashMap.

A hashMap principle

Using a HashMap is also easy, just put key-values in.

public static void main(String[] args) throws InterruptedException { HashMap map = new HashMap(); Map. Put (1, "zhang SAN "); Map. Put (2, "lI Si "); Map. Put (3, "king five "); Map. Put (4, "zhao 6 "); System.out.println("size:" + map.size()); }Copy the code

This is a common approach, and we don’t have to worry too much about the internal operations of a HashMap, just a simple call.

So what’s going on in the HashMap?

To open the HashMap class, we use new HashMap() as the entry point.

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75). // Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75) Construct an empty hash map with a default initial capacity (16) and a default load factor (0.75). public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }Copy the code

The load factor

There is a load factor, which sounds complicated, but it is a variable that represents the start of expansion when (capacity * load factor) is reached.

As for why the default load factor is 0.75, it’s probably a compromise. See an article on JDK1.7 that describes the load factor:

As a general rule, the default load factor (0.75) provides a good trade-off between time and space costs. Higher values reduce the space overhead but increase the cost of lookups (shown in most HashMap class operations, including GET and PUT). When setting the initial size, you should consider the expected number of entries in the map and its load factor, and minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, the rehash operation will not occur.Copy the code

The default volume

Looking at the source code, the default size of a HashMap is 1 << 4, which is 16.

When the threshold reaches (16 x 0.75), the capacity expansion starts

Expansion mechanism

static final int MAXIMUM_CAPACITY = 1 << 30;

Copy the code

The capacity of a HashMap is limited and must be less than 1<<30 (1073741824). If the capacity exceeds this number, it does not grow and the threshold is set to integer.max_value

Expansion mechanism in JDK1.7

Except that the constructor and default constructor specify some default values, if the capacity is not expanded for the first time, new capacity = old capacity * 2; New threshold = New capacity x load factor

Expansion mechanism in JDK1.8

Except that the constructor and default constructor specify some default values, if it is not the first expansion, the capacity is doubled and the threshold is doubled. (Load factor remains the same when capacity and threshold are doubled.)

The data structure

static class Node<K,V> implements Map.Entry<K,V> {

final int hash;

final K key;

V value;

Node<K,V> next;

}

Copy the code

Hash: Hash value of the key.

Key: the key to insert a value;

Value: the value;

Next: The next object.

From this code structure, you can see that HashMap uses a linked list data structure, also known as the zipper method.

Its most obvious feature is: the storage unit on the non-continuous, non-sequential storage structure, but in each node to the next node in the pointer field.

Is the put operation added to the top or bottom of the list

JDK 1.7 uses header insertion to add linked list elements. There is a problem with the looped list. In 1.8, we optimized the header insertion method to add linked list elements.