After explaining the underlying principles of hashmap to the interviewer, he said he was optimistic about me

As a programmer, you must have been asked about HashMap during the interview, and the basic implementation principle is that every interviewer should master it, when we master the internal implementation principles of HashMap In the face of the interviewer's inquiry, you can answer freely, and the next editor will take you to understand the JDK7 version of HashMap foundation and how to implement it.

First, HashMap introduction

Introduction to HashMap: HashMap is a hashmap that stores key-value pair mapping. HashMap is inherited from AbstractMap and implements Map Cloneable java.io.Serializable interfaces. HashMap implementation is not synchronous, which means it is not thread-safe. I ts key value can be null I n addition, the mapping in HashMap is not ordered. A n instance of HashMap has two parameters that affect its performance: "initial capacity" and "load factor." C apacity is the number of buckets in the hash table, and the initial capacity is just the capacity of the hash table at the time it was created. T he load factor is a measure of how full a hash table can reach before its capacity increases automatically. W hen the number of entries in the hash table exceeds the product of the load factor to the current capacity, the hash table is rehash (that is, the internal data structure is rebuilt), so that the hash table will have about twice the number of barrels. T ypically, the default load factor is 0.75, which is a trade-off in time and space costs. T oo high a load factor reduces space overhead, but it also increases query costs (as reflected in most HashMap operations, including get and put operations). W hen setting the initial capacity, you should take into account the number of entries required in the map and its loading factors in order to 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 does not occur.

The inheritance relationship of HashMap :

HashMap's relationship with Map is illustrated below:

HashMap's constructor

HashMap has four constructors, as follows:

// 默认构造函数。
HashMap()
// 指定“容量大小”的构造函数
HashMap(int capacity)
// 指定“容量大小”和“加载因子”的构造函数
HashMap(int capacity, float loadFactor)
// 包含“子Map”的构造函数
HashMap(Map<? extends K, ? extends V> map)

Second, the underlying principle of HashMap in JDK7

The basic storage structure used by HashMap in JDK7 or JDK8 is in the form of arrays and linked lists. This section focuses on the underlying implementation of HashMap in JDK7 and its basic structure is shown below:

The orange area on the left in the image above is the hash table, the blue area on the right is the list, and the element type in the list is Entry which contains four properties:

• K key
• V value
• int hash
• Entry next

So why is there a storage structure in the form of arrays and lists? H ere's a brief introduction, followed by a detailed description in the form of a source code. W hen we store data using HashMap.put("Key", "Value") method, the underlying is actually storing key and value as Entry in the hash table, which is an array, so how does it store an Entry object in an array? H ow do you determine where the Entry of the current key and value consists of the array, in other words, how do you determine the index of the Entry object in the array? T ypically, when we determine an array, we store the data one by one in the array until the array is full, and then consider the expansion of the array, which is not the case with HashMap In Java and most object-oriented programming languages, each object has an integer variable hashcode which is an important identity that identifies different objects, and with this hashcode it is easy to determine the subscript index of Entry objects, in Java language, it is understood that hashcode is converted into an array subscript based on array length mold operation, the basic formula is as follows: hashcode

int index = HashCode(key) % Array.length

In fact, in JDK the hash function does not take the die operation directly, but uses the bit operation to improve performance, which we understand here as a simple die-taking operation. W e know that by hashing Key and then molding the array length to get the current Entry object's subscript in the array, we can keep calling HashMap put method to continuously store data into the array. B But there is a phenomenon that the results calculated from different Key are likely to be identical, a phenomenon known as hash conflict. N ow that there is a hash conflict, how does this data that conflicts store? H ash conflict is actually an unavoidable fact, since it can not be avoided, then we should find a way to solve this problem, the current commonly used methods are mainly two, one is open addressing method, the other is the linked list method. O pen addressing is a simple principle, that is, in the array "to find another high", trying to find the next neutral position. I nstead of looking for the next neutral location, the list law continues to be stored in the current conflict, forming a list of existing data and storing it as a list. HashMap is stored in the form of an array-linked list, which is used to resolve hash conflicts. F or specific details, please continue to look down. In daily development, developers use HashMap most of its construction methods, put methods, and get methods, and let's start with a detailed understanding of HashMap works.

Third, HashMap put, get method flowchart

Here is a flowchart of HashMap put method to store data for the reader's reference:

Here is a flowchart of HashMap get method to get data for readers to refer to:

The get flowchart above is slightly more complex than normal, just to describe the process more clearly.

Fourth, the common HashMap iterative approach

During the actual development process, we also have a common operation for HashMap iterative traversal, HashMap is commonly used in several ways:

• Mode 1: Iterator mode

Map<String, String> map = new HashMap<>(16);
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, String> next = iterator.next();
    System.out.println(next.getKey() + ":" + next.getValue());
}

• Mode 2: Traverse set > way

Map<String, String> map = new HashMap<>(16);
for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

• Mode 3: ForEach Method (JDK8 Features, Lambda)

Map<String, String> map = new HashMap<>(16);
map.forEach((key, value) -> System.out.println(key + ":" + value));

• Mode 4: KeySet mode

Map<String, String> map = new HashMap<>(16);
Iterator<String> keyIterator = map.keySet().iterator();
while (keyIterator.hasNext()) {
    String key = keyIterator.next();
    System.out.println(key + ":" + map.get(key));
}

(Recommended micro-class: Java micro-class)

Comparing these four methods, the first three are actually the same, are iterator traversal, if you want to use key and value recommend the first three methods, if only to key then recommend the use of the fourth.

Source: www.toutiao.com/a6862688709423137294/

The above is W3Cschool编程狮 about hashmap underlying principles of the relevant introduction, I hope to help you.