Shulou(Shulou.com)06/01 Report--

This article mainly introduces "how to analyze HashMap source code". In daily operation, I believe many people have doubts about how to analyze HashMap source code. Xiaobian consulted all kinds of data and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the doubts of "how to analyze HashMap source code". Next, please follow the editor to study!

Introduction to HashMap

HashMap is mainly used to store key-value pairs. It is based on the Map interface implementation of the hash table and is one of the commonly used Java collections.

Before JDK1.8, HashMap consists of an array + linked list, which is the main body of HashMap, and the linked list exists mainly to solve hash conflicts ("zipper method" to solve conflicts). JDK1.8 has changed greatly in resolving hash conflicts later, when the length of the linked list is greater than the threshold (default is 8), the linked list will be converted into a red-black tree to reduce search time.

Before the underlying data structure analysis of JDK1.8

Before JDK1.8, the underlying HashMap was a combination of arrays and linked lists, that is, linked list hashes. HashMap gets the hash value through the hashCode of key after being processed by the disturbance function, and then uses (n-1) & hash to determine the current location of the element (where n refers to the length of the array). If there is an element in the current position, determine whether the hash value and key of the element and the element to be stored are the same. If the same, cover directly, and resolve the conflict through the zipper method.

The so-called perturbation function refers to HashMap's hash method. The hash method, the disturbance function, is used to prevent some poorly implemented hashCode () methods, in other words, to reduce collisions after using the disturbance function.

JDK 1.8 HashMap hash method source code:

The hash method of JDK 1.8 is more simplified than the JDK 1.7 hash method, but the principle remains the same.

one

two

three

four

five

six

seven

Static final int hash (Object key) {

Int h

/ / key.hashCode (): returns a hash value that is hashcode

/ / ^: XOR by bit

/ / >: move unsigned to the right, ignore the symbol bit, and fill the vacancy with 0

Return (key = = null)?: (h = key.hashCode ()) ^ (h > 16)

}

Compare the hash method source code of JDK1.7 's HashMap.

one

two

three

four

five

six

seven

eight

Static int hash (int h) {

/ / This function ensures that hashCodes that differ only by

/ / constant multiples at each bit position have a bounded

/ / number of collisions (approximately 8 at default load factor).

H ^ = (h > 20) ^ (h > 12)

Return h ^ (h > 7) ^ (h > 4)

}

Compared to JDK1.8 's hash method, JDK 1.7's hash method performs a little worse because it is disturbed four times after all.

The so-called "zipper method" is the combination of linked lists and arrays. In other words, create a linked list array, each grid in the array is a linked list. If you encounter a hash conflict, you can add the conflicting value to the linked list.

After JDK1.8

Compared with the previous version, jdk1.8 has made a big change in resolving hash conflicts. When the length of the linked list is greater than the threshold (default is 8), it converts the linked list to a red-black tree to reduce search time.

Properties of the class:

one

two

three

four

five

six

seven

eight

nine

ten

eleven

twelve

thirteen

fourteen

fifteen

sixteen

seventeen

eighteen

nineteen

twenty

twenty-one

twenty-two

twenty-three

twenty-four

twenty-five

twenty-six

twenty-seven

twenty-eight

Public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {

/ / Serial number

Private static final long serialVersionUID = 362498820763181265L

/ / the default initial capacity is 16

Static final int DEFAULT_INITIAL_CAPACITY = 1

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.