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 ...