Jdk1.7-hashmap principle

JameJN 2021-01-14 19:04:56
jdk1.7-hashmap jdk hashmap principle


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, I don't quite understand now , Just have an impression first

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 ٩(๑>◡<๑)۶

版权声明
本文为[JameJN]所创,转载请带上原文链接,感谢
https://javamana.com/2021/01/20210114190418079C.html

  1. Learn about RPC, why RPC was born, and what's the difference between RPC and HTTP?
  2. Learn about RPC, why RPC was born, and what's the difference between RPC and HTTP?
  3. Learn java base conversion supplementary learning
  4. JDBC测试连接数据库
  5. JDBC test connection database
  6. 大厂面试官竟然这么爱问Kafka,一连八个Kafka问题把我问蒙了?
  7. The interviewers of big factories love to ask Kafka so much. I'm blinded by eight Kafka questions in a row?
  8. 安卓开发和java开发有什么区别!2021年BATJ30套大厂Android经典高频面试题,面试必问
  9. Spring Security OAuth2.0認證授權四:分散式系統認證授權
  10. What's the difference between Android development and java development! 2021 batj30 Android classic high frequency interview questions
  11. Spring security oauth2.0 authentication and authorization 4: distributed system authentication and authorization
  12. Java微服务 vs Go微服务,究竟谁更强!?
  13. 大厂面试官竟然这么爱问Kafka,一连八个Kafka问题把我问蒙了?
  14. Who is stronger, Java microservice vs go microservice!?
  15. Java微服务 vs Go微服务,究竟谁更强!?
  16. The interviewers of big factories love to ask Kafka so much. I'm blinded by eight Kafka questions in a row?
  17. Who is stronger, Java microservice vs go microservice!?
  18. springboot异常处理之404
  19. Spring boot exception handling 404
  20. Spring Boot Security 国际化 多语言 i18n 趟过巨坑
  21. springboot异常处理之404
  22. Spring boot security international multilingual I18N
  23. Spring boot exception handling 404
  24. Netty系列化之Google Protobuf编解码
  25. Netty之编解码
  26. Java编解码
  27. Netty解码器
  28. Netty与TCP粘包拆包
  29. Netty开发入门
  30. Java集合遍历时遇到的坑
  31. Spring IOC 源码解析(下)
  32. Spring IoC源码解析(上)
  33. Google protobuf codec of netty serialization
  34. Encoding and decoding of netty
  35. Java codec
  36. Netty decoder
  37. Netty and TCP packet sticking and unpacking
  38. Introduction to netty development
  39. Problems encountered in Java collection traversal
  40. Spring IOC source code analysis (2)
  41. Spring IOC source code analysis (Part one)
  42. 半小时用Spring Boot注解实现Redis分布式锁
  43. Implementing redis distributed lock with spring boot annotation in half an hour
  44. What should we do if we can't get tickets for Spring Festival transportation? You can solve this problem by using these ticket grabbing apps!
  45. 百度智能(文本识别),API传图OC代码与SDK使用
  46. springboot源码解析-管中窥豹系列之aware(六)
  47. Baidu intelligent (text recognition), API map, OC code and SDK
  48. Spring boot source code analysis
  49. springboot源码解析-管中窥豹系列之aware(六)
  50. 百度智能(文本识别),API传图OC代码与SDK使用
  51. Spring boot source code analysis
  52. Baidu intelligent (text recognition), API map, OC code and SDK
  53. Java学习笔记
  54. Java learning notes
  55. Sentry(v20.12.1) K8S 雲原生架構探索, SENTRY FOR JAVASCRIPT 手動捕獲事件基本用法
  56. 我的程式設計師之路:自學Java篇
  57. SpringBoot專案,如何優雅的把介面引數中的空白值替換為null值?
  58. Sentry (v20.12.1) k8s cloud native architecture exploration, sentry for JavaScript manual capture event basic usage
  59. My way of programmer: self study java
  60. Spring boot project, how to gracefully replace the blank value in the interface argument with null value?