# JDK1.7 HashMap

How to add your own comments to the source code

open jdk Download location

decompression src Folder , open idea,`ctrl+shift+alt+s`

Open project configuration

choice jdk edition 1.7, And then click Sourcepath

Choose the one you just unzipped src File directory , And then choose src.zip Click `-`

Number , Only the decompressed one is left in the project src File can

Open source , A prompt box will appear when you type , Just click ok that will do , Then you can enter your own comments

Let's get to know before we start JDK1.7 Of HashMap Data structure of , Even if I haven't studied the source code, I've heard of it JDK1.7 in HashMap It's an array and a linked list ,1.8 Array plus linked list plus red black tree , Today we mainly study 1.7, First of all, arrays must know , Linked list is a very difficult thing , It's not hard at all

What is a linked list , With java Code form

Suppose there's a node now , There are specific values and references to the next node

`public class Node{`

private int number;

private Node next;

}

When a node's next The reference points to the next Node node , Many nodes connected together are called linked lists

JDK1.7 The data structure of is as shown in the figure below

Before you start, I suggest you open the corresponding class , Methods to take a look at their own source code , Otherwise it's easy not to know where it is

## HashMap Global variable in

```
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final Entry<?, ?>[] EMPTY_TABLE = {};
transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;
```

Let's look at global variables , Briefly describe what they do

**DEFAULT_INITIAL_CAPACITY**

Default initial capacity , And size uses a shift left operator , How to see its value ?java All bit operations in are performed in the binary case

First 1 The binary of is 0000 0001 and << 4 The sign means to move all the numbers to the left 4 position , Move out of position with 0 Replace

That is to say 0001 0000 Convert to 10 Hexadecimal is 16, That is to say HashMap Default capacity of

**MAXIMUM_CAPACITY**

The maximum capacity , Also use bitwise operators ,1<<30 Convert to 10 Hexadecimal is 1073741824

**DEFAULT_LOAD_FACTOR**

Default load factor , The default is 0.75f, Now maybe it's not clear. Just have an impression

**Entry[] EMPTY_TABLE**

Initialize an empty array

**Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE**

Arrays that actually store data

**size**

Number of storage elements ,map.size() The method is to return the variable directly

`public int size() {`

return size;

}

**threshold**

critical value , When the capacity reaches this capacity, judge whether to expand the capacity , And the formula for calculating the critical value is , Capacity multiplied by load factor , If initialization is not set map The size and load factor of , The default is 16*0.75=12

**loadFactor**

If you create HashMap The load factor is set when , Then it will be assigned to this variable , If there is no special requirement, it is not necessary to set this value , Too large causes the list to be too long , influence get Method , Too small will lead to frequent capacity expansion and waste performance

**modCount**

HashMap The number of times the structure of is modified , For iterators

## Construction method

Let's start with the nonparametric construction

`public HashMap() {`

this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);

}

Overloaded construction called , The default size is passed in (16) And the default load factor size (0.75f)

So let's look at parametric construction

`public HashMap(int initialCapacity, float loadFactor) {`

// The initial capacity cannot be less than 0

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal initial capacity: " +

initialCapacity);

// Whether the initial capacity is greater than the maximum capacity

if (initialCapacity > MAXIMUM_CAPACITY)

// If it is greater than the maximum capacity , Then set the capacity to the maximum capacity

initialCapacity = MAXIMUM_CAPACITY;

// If the load factor is less than 0 Or it's not a number that throws an exception

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException("Illegal load factor: " +

loadFactor);

// Set load factor , The critical value is the capacity , For the first time in the future put When by inflateTable(int toSize) Method calculation settings

this.loadFactor = loadFactor;

threshold = initialCapacity;

// Empty method , Implemented by other implementation classes

init();

}

## put Method

Expansion is just put Method , Look at code

`public V put(K key, V value) {`

// If table References point to member variables EMPTY_TABLE, Then initialize HashMap（ Set capacity 、 critical value , new Entry An array reference ）

if (table == EMPTY_TABLE) {

inflateTable(threshold);

}

// HashMap Support key by null

if (key == null)

//key by null Call alone to store null key Methods

return putForNullKey(value);

// Calculation key Of hash value

int hash = hash(key);

// according to hash Values and the current length of the table , Get a subscript in the array , Focus on indexFor Method implementation .

// The algorithm mainly returns an index ,0 To table.length-1 Array subscript of .

int i = indexFor(hash, table.length);

// Next , find table[i] It's about , And the linked list of data there , See if there are the same key; Judge key identical ,

// First judgement hash Whether the values are equal , And then again Judge key Of equals Whether the methods are equal

for (Entry<K, V> e = table[i]; e != null; e = e.next) {

Object k;

// First judgement hash, If the object's hashCode Method is not overridden , that hash Two objects must be equal when their values are equal

// And judge if key Equal or key If the values of are equal to each other, then the old value

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

V oldValue = e.value;

e.value = value;

e.recordAccess(this);

return oldValue;

}

}
modCount++;

// Add operation

addEntry(hash, key, value, i);

return null;

}

Let's take a step-by-step look , Let's start with the first judgment

`// If table References point to member variables EMPTY_TABLE, Then initialize HashMap（ Set capacity 、 critical value , new Entry An array reference ）`

if (table == EMPTY_TABLE) {

inflateTable(threshold);

}

If that's true , That is to say, the array has not been initialized yet , Call `inflateTable(threshold);`

Method to initialize , The parameter passed in is the critical value , Let's see inflateTable Method

`private void inflateTable(int toSize) {`

// Find a power of 2 >= toSize

// First calculate the capacity , toSize Capacity of threshold, In the constructor ,threshold The default is equal to the initial capacity , That is to say 16

int capacity = roundUpToPowerOf2(toSize);

// Then recalculate threshold Value , The default is capacity * loadFactor

//Math.min Method is used to return the minimum of two parameters

threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);

// Initialize array Capacity of capacity

table = new Entry[capacity];

initHashSeedAsNeeded(capacity);

}

roundUpToPowerOf2 Method , Let's take a brief look at the function of this method

`private static int roundUpToPowerOf2(int number) {`

// assert number >= 0 : "number must be non-negative";

// Judge whether the value of the parameter is greater than the maximum capacity

return number >= MAXIMUM_CAPACITY

// If it is greater than, the maximum capacity will be returned

? MAXIMUM_CAPACITY

/**

* If it is less than 1 return 1

* highestOneBit Method can be simply understood as returning the number less than or equal to the nearest 2 The number of squares

* for example

* 2 Of 1 Power 2

* 2 Of 2 Power 4

* 2 Of 3 Power 8

* 2 Of 4 Power 16

* 2 Of 5 Power 32

* Less than 15, And the distance 15 Current 2 The number of squares : 8

* Less than 16, And the distance 15 Current 2 The number of squares : 16

* Less than 17, And the distance 15 Current 2 The number of squares : 16

*/

: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;

}

We will not continue to study the implementation of specific methods , It's not the theme of this article , Keep looking. `inflateTable`

The content of the method is

`threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);`

This step is to recalculate threshold Value , That's the critical value , Calculate the critical value by multiplying the calculated capacity by the load factor

Math.min The method is to determine the size of the two values , Go back to the little one , If the parameters have the same value , Then the result is the same value . If any value is NaN, The result is NaN

After that, a Entry An array of types assigned to table

`// Initialize array Capacity of capacity`

table = new Entry[capacity];

So let's take a look at this Entry class

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

final K key;

V value;

Entry<K, V> next;

int hash;

}

So and the example at the beginning Node Basically the same idea , Define a separate variable in the class to store the next node `next`

go back to put Method , Let's take a look at the next judgment

`// HashMap Support key by null`

if (key == null)

//key by null Call alone to store null key Methods

return putForNullKey(value);

Let's take a look at this putForNullKey Method

`private V putForNullKey(V value) {`

// Get the subscript as 0 Of Entry node

for (Entry<K, V> e = table[0]; e != null; e = e.next) {

if (e.key == null) {

V oldValue = e.value;

e.value = value;

// Empty method

e.recordAccess(this);

return oldValue;

}

}

modCount++;

addEntry(0, null, value, 0);

return null;

}

stay HashMap in ,key by null Of entry Will be stored in the subscript 0 The location of , The overlay operation is performed on it , Look at addEntry Method

`void addEntry(int hash, K key, V value, int bucketIndex) {`

/* JDK1.7 Future expansion conditions ;size Greater than or equal to threshold, And the index value of the newly added element is not equal to null

That is, even when size To achieve or surpass threshold, New elements , As long as it doesn't cause hash Conflict does not expand ;

JDK1.8 Removed for null The judgment of the

*/

if ((size >= threshold) && (null != table[bucketIndex])) {

// Double the size

resize(2 * table.length);

// If key by null, Put index by 0 The location of , Otherwise, take hash The operation of

hash = (null != key) ? hash(key) : 0;

// According to the hash Value to get the subscript

bucketIndex = indexFor(hash, table.length);

}

// establish entry

createEntry(hash, key, value, bucketIndex);

}

Let's look at the expansion resize() Method , What's coming in is 2 Times the length of the old array

`void resize(int newCapacity) {`

// The old table Assign a value to oldTable

Entry[] oldTable = table;

// Get old table length

int oldCapacity = oldTable.length;

// If the length is already equal to, the maximum limit is set to Integer The maximum of

if (oldCapacity == MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return;

}

// Create a new table, The length is the parameter. The length is the parameter passed in newCapacity

Entry[] newTable = new Entry[newCapacity];

// This method will oldTable The data is copied to newTable

transfer(newTable, initHashSeedAsNeeded(newCapacity));

// The newly expanded table Now hashmap The storage table

table = newTable;

// Recalculate the threshold

threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

}

In the expansion method, we mainly focus on transferring data transfer Method

`void transfer(Entry[] newTable, boolean rehash) {`

// Get the newly created table length

int newCapacity = newTable.length;

// Traverse the old table

for (Entry<K, V> e : table) {

/* The code first determines if the current subscript entry Is it empty ,

If it is empty, switch to the next Entry node

If it's not empty , The second time is to judge the current subscript entry Whether to form a linked list

If a linked list is formed, it will always judge whether there is a next node , After traversing the subscript list ,

Then switch to the next entry Nodes do the same thing

* */

while (null != e) {

// Get the next one entry

Entry<K, V> next = e.next;

if (rehash) {

/**

* Judge e.key Is it null, If null take e.hash The assignment is 0

* Otherwise, call hash() Method to calculate hash

*/

e.hash = null == e.key ? 0 : hash(e.key);

}

// Through the current traversal of the old table entry Of hash Value and new table To get the subscript position in the new table

int i = indexFor(e.hash, newCapacity);

/*

* jdk1.7 It's head insertion , That is, you don't need to know whether the current subscript position exists Entry

* Just put the old table in Entry node , By calculating the subscript position

* In the newly added Entry Assign the current subscript element directly to next attribute , The newly added node is then assigned to the current subscript

*/

e.next = newTable[i];

newTable[i] = e;

e = next;

}

}

}

There are several ways to focus on

`//hash()====== This method is simply understood as to pass key To calculate hash, stay get Through hash Make sure it's the same entry object `

final int hash(Object k) {

int h = hashSeed;

if (0 != h && k instanceof String) {

return sun.misc.Hashing.stringHash32((String) k);

}
h ^= k.hashCode();
// 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);

}

//indexFor()===========

/**

Use here & It depends on the operator , The two are the same 1 return 1, Otherwise return to 0, for example

0010 1101

1010 1011

result 0010 1001

*/

static int indexFor(int h, int length) {

return h & (length - 1);

}

Let's go back to resize Expansion method , The most important method is to copy the data from the old array to the new array transfer() The method , Other operations have comments on them , It should be able to understand

Here we mainly talk about **indexFor** Method ,** Initializing HashMap Why must the initial size be set to 2 Multiple **

** Let's say HashMap Initialization size is 16 For example **

First & Both operators are 1 Only then 1, Otherwise 0

hypothesis hash The value is ....1010 1010 And now hashmap The length of is 16, namely (16-1)=15

hash:1010 1010

15: 0000 1111

because 15 The lower four places of 1, That is to say through & Only four of the lower four bit operators can affect the result 1, All the others are 0

This is also hash() The purpose of the method is to involve as many other people as possible hash operation , To achieve a more decentralized hash value

Suppose the initial size is odd , for example 15, Then through the `(length - 1);`

, The result is 14,14 The binary of is

0000 1110

So and the calculated hash Conduct & The number of bits that the operation can affect the result will be reduced 1 position , This is still a good situation , If the initial size passed in is 17 So what happens ?

17 adopt length-1 The operation of is 16,16 The binary of is 0001 0000, Then talk to hash Value for & The operation of

hash: 1010 1010

16: 0001 0000

There are only two cases ,0000 0000 and 0001 0000 , So set up hashmap The size of that will have no effect ,

Only in 0000 0000 and 0001 0000 The location of put operation , and 0000 0000 by 0 Subscript , Used to add null Of key Then all the added data will be added To 16 The location of !

Let's go back to addEntry() In the method

`void addEntry(int hash, K key, V value, int bucketIndex) {`

/* JDK1.7 Future expansion conditions ;size Greater than or equal to threshold, And the index value of the newly added element is not equal to null

That is to say size To achieve or surpass threshold, New elements , As long as it doesn't cause hash Conflict does not expand ;

JDK1.8 Removed for null The judgment of the

*/

if ((size >= threshold) && (null != table[bucketIndex])) {

// Double the size

resize(2 * table.length);

// If key by null, Put index by 0 The location of , Otherwise, take hash The operation of

hash = (null != key) ? hash(key) : 0;

// According to the hash Value to get the subscript

bucketIndex = indexFor(hash, table.length);

}

// establish entry

createEntry(hash, key, value, bucketIndex);

}

resize() The method is as follows hash Operation of the hash() Method and get subscript indexFor All the methods have been written on it , No more details here

Next, let's focus on createEntry Method

`void createEntry(int hash, K key, V value, int bucketIndex) {`

// Get the current subscript first entry node , Also may be null

Entry<K, V> e = table[bucketIndex];

// If there is entry node , So adding new entry Will form a linked list

table[bucketIndex] = new Entry<>(hash, key, value, e);

// take hashmap The size of the add 1

size++;

}

because hash value , All subscript positions have been obtained , So the method passes in parameters and uses them directly

Come here put In the method putForNullKey() add to null key This is the way to do it , We go back to put The method continues

`//put Method , Omit some of the methods just written `

int hash = hash(key);

int i = indexFor(hash, table.length);

// Next , find table[i] It's about , And the linked list of data there , See if there are the same key; Judge key identical ,

// First judgement hash Whether the values are equal , And then again Judge key Of equals Whether the methods are equal

for (Entry<K, V> e = table[i]; e != null; e = e.next) {

Object k;

// First judgement hash, If the object's hashCode Method is not overridden , that hash Two objects must be equal when their values are equal

// And judge if key Equal or key If the values of are equal to each other, then the old value

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

V oldValue = e.value;

e.value = value;

e.recordAccess(this);

return oldValue;

}

}

modCount++;

// Add operation

addEntry(hash, key, value, i);

return null;

At the top hash() and indexFor() The method says , I won't repeat , The intermediate judgment override reference note should be understandable , And the following addEntry The method also says

## get Method

If you understand put After the method ,get The method will be relatively simple

`public V get(Object key) {`

// Determine if the key be equal to null Words , Call directly to get nullkey Methods

if (key == null)

return getForNullKey();

// adopt getEntry The way to entry node

Entry<K, V> entry = getEntry(key);

// Judge if it is null return null, Otherwise return to entry Of value

return null == entry ? null : entry.getValue();

}

First of all to see key by null The situation of

`private V getForNullKey() {`

// If hashmap The size is 0 return null

if (size == 0) {

return null;

}

/**

When I started my research, I had a problem , When I was blogging, I suddenly understood ,

The problem is that since it's known key by null Of entry Will be placed in the subscript 0 The location of , Why cycle , Direct access to 0 Subscript entry Can't you cover it

And then I'm writing indexFor When I think of the method , Not only null Of key Subscript to be 0, If one hash After the algorithm is finished, it passes indexFor Method

The calculated subscript is exactly 0 Well , It has to go through the loop to find that key by null Of entry

*/

for (Entry<K, V> e = table[0]; e != null; e = e.next) {

if (e.key == null)

return e.value;

}

return null;

}

The logic is simple , No explanation , We go back to get Look at the next getEntry Method

`final Entry<K, V> getEntry(Object key) {`

// If hashmap The size is 0 return null

if (size == 0) {

return null;

}

// Judge key If null Then return to 0, Otherwise it would be key Conduct hash

int hash = (key == null) ? 0 : hash(key);

//indexFor Methods by hash Values and table Gets the corresponding subscript

// Traversing the subscript of ( If there is ) Linked list

for (Entry<K, V> e = table[indexFor(hash, table.length)];

e != null;

e = e.next) {

Object k;

// Judge the present entry Of key Of hash If and when you're involved key Return to the current entry node

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

return e;

}

return null;

}

Here we are JDK1.7 in HashMap Basic get,put The method is finished

This article is for personal understanding only , If there is something wrong, you are welcome to comment or send a private letter , thank you ٩(๑>◡<๑)۶

## JDK1.7-HashMap More articles on the principles

- JDK1.8 HashMap Source code analysis
One .HashMap summary stay JDK1.8 Before ,HashMap Use arrays + Linked list implementation , That is, using linked lists to handle conflicts , same hash The values of the nodes are stored in a linked list . But when there are more elements in a bucket , namely hash When there are many elements with equal values ...

- Java:HashMap Principles and design reasons
Preface Java The most commonly used data structure in is basically ArrayList and HashMap,HashMap The principle also often appears in various interview questions , This article is about HashMap The design and design reasons are explained one by one , And answer some common interview questions . ...

- java in HashMap principle ？
Reference resources :https://www.cnblogs.com/yuanblog/p/4441017.html( recommend ) https://blog.csdn.net/a745233700/article/deta ...

- == and equasl、hashmap principle （***）
public class String01 { public static void main(String[] args) { String a="test"; String b ...

- Java Basics -hashMap Principle analysis
Java Basics -hashMap Principle analysis author : Yin Zhengjie Copyright notice : Original works , Declined reprint ! Otherwise, the legal liability will be investigated . One . What is hash (Hash) answer :Hash It's hash , That is to break up the objects . for instance , Yes 100000 Number of pieces ...

- JDK1.8 HashMap$TreeNode.balanceInsertion Red black tree balanced insertion
Introduction to the red and black tree 1. Nodes are red or black . 2. The root node is black . 3. Each leaf node is a black, empty node (NIL node ). 4 The two children of each red node are black .( You cannot have two consecutive red nodes on all paths from each leaf to the root ) ...

- JDK1.8 HashMap$TreeNode.rotateLeft The red black tree is left-handed
Introduction to the red and black tree 1. Nodes are red or black . 2. The root node is black . 3. Each leaf node is a black, empty node (NIL node ). 4 The two children of each red node are black .( You cannot have two consecutive red nodes on all paths from each leaf to the root ) ...

- HashMap principle ( Two ) Expansion mechanism and access principle
We were in the last chapter <HashMap principle ( One ) Concept and underlying architecture > I explained HashMap Storage data structure and commonly used concepts and variables , Include capacity Capacity ,threshold Variables and loadFactor ...

- jdk1.8 HashMap Underlying data structure ： In depth analysis of why jdk1.8 HashMap The capacity must be 2 Of n The next power
Preface 1. This article is based on jdk1.8 Source code to analyze HashMap The capacity value problem of : 2. This article has done jdk1.8 HashMap.resize() Source code analysis of expansion method : See below “ One .3. Capacity expansion : We also need to ensure that the capacity after expansion is ...

- JDK1.7 hashMap Source code analysis
understand HashMap Let's look at several data structures before we start to understand the principles : 1. Array : Using a continuous memory space to store data . A lookup for the specified subscript , The time complexity is O(1), The search for a given element , You need to traverse the entire data , The time complexity is O(n). but ...

## Random recommendation

- preservation emoji To the database
/// <summary> /// <summary> /// String rotation Unicode /// </summary> /// <param name=&quo ...

- io.js introduction （ Two ）—— Supported by the ES6（ On ）
io.js There is a special introduction on the official website of ES6 Feature pages ( Check me out. ), It's about , comparison nodeJS,io.js Has fundamentally supported the new version V8 Supported by the engine ES6 characteristic , There is no need to add any more runtime flags ( Such as --harm ...

- Write simple games , Learning programming languages -python piece
ok , First of all, I have to admit that the topic is exaggerated , A talent rookie , Game related programming also knows some concepts . But I am more interested in game development , I believe most people like to play games , Because it does bring a lot of fun , And the learning of programming language is boring for me at least ...

- stay eclipse.ini It is specified in jdk The way
stay eclisep Installation directory , open eclipse.ini file , Plus this line , As shown in red below , Pay attention to the addition -Vmargs front , The difference between the two ways is : The second way is to have eclipse There will also be a java process . ...

- Routes
Routes Routing lets you create your own URL paths, based on the path you can load a closure or a con ...

- Oracle EBS-SQL (GL-1): From general ledger to receiving
SELECT je_header_id, je_line_num, trx_class_name, trx_type_name, trx_number_displayed, trx_date,comm ...

- note ：Spring Cloud Eureka Common configuration and description
Configuration parameters The default value is explain Service registry configuration Bean class :org.springframework.cloud.netflix.eureka.server.EurekaServerConfigBean ...

- Axure RP8 Registration code
The upgrade 8.1.0.3381 After version , You need to use the following set of registration codes License:zdfansKey:fZw2VoYzXakllUuLVdTH13QYWnjD6NZrxgubQkaRyxD5+HNMqdr+ ...

- 001_HTTP Parameters in Etag Importance
Research on tornado when , There is one Etag More curious , Excerpts from online inquiries are as follows :

- Go Language lock free queue component implementation (chan/interface/select)
1. background go It's very easy to implement asynchrony in the code ,go funcName(). But the process needs to control the number of coroutines within a reasonable range , Corresponding to a large number of tasks, you can use " Xie Chengchi + Lockless queue " Realization . 2. golang ...