JDK1.7-HashMap原理

JameJN 2021-01-14 19:04:19
jdk 原理 hashmap jdk1.7-hashmap


JDK1.7 HashMap

如何在源码上添加自己的注释

打开jdk下载位置

解压src文件夹,打开idea,ctrl+shift+alt+s打开项目配置

选择jdk版本1.7,然后点击Sourcepath

选择刚刚解压的src文件目录,然后选择src.zip的文件点击- 号,项目中只留下刚才解压的src文件即可

打开源码,输入时会出一个提示框,直接点击ok即可,然后就可以输入自己的注释了

在开始前先了解一下JDK1.7的HashMap的数据结构,就算没有研究过源码也听过JDK1.7中HashMap是数组加链表,1.8中是数组加链表加红黑树,今天我们主要研究1.7,首先数组肯定都知道,链表这个一听以为是很难的东西,其实一点也不难

什么叫链表呢,以java代码形式

假设现在有一个节点,里有具体的值和下一个节点的引用

public class Node{
private int number;
private Node next;
}

当节点的next引用指向下一个Node节点,许多的节点连接起来就叫做链表

JDK1.7的数据结构就是如下图所示

在开始前建议自己跟着打开对应的类,方法来自己看一看源码,不然很容易就不知道在哪里了

HashMap中的全局变量

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;

我们来看一下全局变量,简单描述一下它们的作用

DEFAULT_INITIAL_CAPACITY

默认的初始容量,而大小使用了一个左移运算符,怎么来看它的值呢?java中所有的位运算都是在二进制的情况下进行的

首先1的二进制是 0000 0001 而<< 4 符号的意思是将所有的数字往左边移动4位,移出来的位置用0替换

也就是 0001 0000 转换为10进制就是16,也就是HashMap的默认容量

MAXIMUM_CAPACITY

最大容量,也是使用位运算符,1<<30 转换为10进制就是1073741824

DEFAULT_LOAD_FACTOR

默认的负载因子,默认为0.75f,现在可能不太理解,先有个印象即可

Entry[] EMPTY_TABLE

初始化的一个空数组

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

真正存储数据的数组

size

存储元素的个数,map.size()方法就是直接返回这个变量

public int size() {
return size;
}

threshold

临界值,当容量到达这个容量是进行判断是否扩容,而这个临界值计算公式就是,容量大小乘以负载因子,如果初始化没有设置map的大小和负载因子的话,默认就是16*0.75=12

loadFactor

如果创建HashMap时设置了负载因子,那么会赋值给这个变量,没有特殊需求的话一般不需要设置这个值,太大导致链表过长,影响get方法,太小会导致经常进行扩容浪费性能

modCount

HashMap的结构被修改的次数,用于迭代器

构造方法

首先来看无参构造

public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

调用了重载的构造,传入的就是默认大小(16)和默认的负载因子大小(0.75f)

那么我们来看有参构造

public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量是否大于最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
//如果大于最大容量,则将容量设置为最大容量
initialCapacity = MAXIMUM_CAPACITY;
//如果负载系数小于0或者不是一个数字抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 设置负载因子,临界值此时为容量大小,后面第一次put时由inflateTable(int toSize)方法计算设置
this.loadFactor = loadFactor;
threshold = initialCapacity;
//空方法,由其他实现类实现
init();
}

put方法

扩容就是在put方法中实现的,来看代码

public V put(K key, V value) {
// 如果table引用指向成员变量EMPTY_TABLE,那么初始化HashMap(设置容量、临界值,新的Entry数组引用)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// HashMap 支持key为null
if (key == null)
//key为null单独调用存储空key的方法
return putForNullKey(value);
//计算key的hash值
int hash = hash(key);
// 根据hash值和表当前的长度,得到一个在数组中的下标,重点关注一下indexFor方法的实现。
// 该算法主要返回一个索引,0 到 table.length-1的数组下标。
int i = indexFor(hash, table.length);
//接下来,找到 table[i]处,以及该处的数据链表,看是否存在相同的key;判断key相同,
// 首先判断hash值是否相等,然后再 判断key的equals方法是否相等
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//首先判断hash,如果对象的hashCode方法没有被重写,那么hash值相等两个对象一定相等
//并且判断如果key相等或者key的值相等那么覆盖并返回旧的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++;
//进行添加操作
addEntry(hash, key, value, i);
return null;
}

我们来一步一步看,首先来看第一个判断

// 如果table引用指向成员变量EMPTY_TABLE,那么初始化HashMap(设置容量、临界值,新的Entry数组引用)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}

如果这个判断成立,也就是说这个数组还没有进行过初始化,则调用inflateTable(threshold);方法来进行初始化,传入的参数为临界值,我们来看inflateTable方法

private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 首先计算容量, toSize 容量为 threshold,在构造方法中,threshold默认等于初始容量,也就是16
int capacity = roundUpToPowerOf2(toSize);
// 然后重新计算 threshold的值,默认为 capacity * loadFactor
//Math.min 方法用于返回两个参数中的最小值
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//初始化数组 容量为 capacity
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}

roundUpToPowerOf2方法,简单来看一下这个方法的作用

private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
//判断参数的值是否大于最大容量
return number >= MAXIMUM_CAPACITY
//如果大于将返回最大容量
? MAXIMUM_CAPACITY
/**
* 如果小于1返回1
* highestOneBit方法可以简单理解为返回小于等于输入的数字最近的2的次方数
* 例如
* 2的1次方 2
* 2的2次方 4
* 2的3次方 8
* 2的4次方 16
* 2的5次方 32
* 小于15,并且距离15最近的2的次方数 : 8
* 小于16,并且距离15最近的2的次方数 : 16
* 小于17,并且距离15最近的2的次方数 : 16
*/
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

具体方法实现就不继续研究了,不是这篇的主题,继续来看inflateTable方法中内容

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

这一步操作是重新计算threshold的值,也就是临界值,通过计算出的容量大小乘以负载因子大小来算出临界值的大小

Math.min方法是判断两个值大小,返回小的那个,如果参数具有相同的值,则结果为相同的值。如果任一值为NaN,则结果为NaN

之后将初始化一个Entry类型的数组赋值给table

//初始化数组 容量为 capacity
table = new Entry[capacity];

那么我们现在来看一下这个Entry类

static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
int hash;
}

那么和开头举的例子Node基本一样的思路,在类中单独定义一个用来存储下一个节点的变量next

回到put方法,来看下一个判断

// HashMap 支持key为null
if (key == null)
//key为null单独调用存储空key的方法
return putForNullKey(value);

我们来看一下这个putForNullKey方法

private V putForNullKey(V value) {
//获取下标为0的Entry节点
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
//空方法
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}

在HashMap中,key为null的entry会存储在下标0的位置,上面进行覆盖操作,来看addEntry方法

void addEntry(int hash, K key, V value, int bucketIndex) {
/* JDK1.7以后的扩容条件;size大于等于threshold,并且新添加元素所在的索引值不等为空
也就是即使当size达到或超过threshold,新增加元素,只要不会引起hash冲突则不扩容;
JDK1.8去掉了为null的判断
*/
if ((size >= threshold) && (null != table[bucketIndex])) {
//将大小扩容到原来的两倍
resize(2 * table.length);
//如果key为null,将放到index为0的位置,否则进行取hash的操作
hash = (null != key) ? hash(key) : 0;
//根据获取的hash值进行获取下标
bucketIndex = indexFor(hash, table.length);
}
//创建entry
createEntry(hash, key, value, bucketIndex);
}

来看扩容resize()方法,传入的是2倍的旧数组的长度

void resize(int newCapacity) {
//将旧table赋值给oldTable
Entry[] oldTable = table;
//获取旧table长度
int oldCapacity = oldTable.length;
//如果长度已经等于最大限制设置为Integer的最大值
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//创建新table,长度为参数为传入的参数newCapacity
Entry[] newTable = new Entry[newCapacity];
//该方法将oldTable的数据复制到了newTable
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//将新扩容的table改为当前hashmap的存储table
table = newTable;
//重新计算阈值
threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

在扩容方法中主要关注将数据转移的transfer方法

void transfer(Entry[] newTable, boolean rehash) {
//获取新创建的table长度
int newCapacity = newTable.length;
//遍历旧table
for (Entry<K, V> e : table) {
/*代码第一次判断如果当前下标entry是否为空,
如果为空则切换到下一个Entry节点
如果不为空,第二次就是判断当前下标的entry是否形成链表
如果形成链表将一直判断是否有下一个节点,当把该下标链表遍历完毕后,
然后切换到下一个entry节点进行相同的操作
* */
while (null != e) {
//获取下一个entry
Entry<K, V> next = e.next;
if (rehash) {
/**
* 判断e.key是否为null,如果为null将e.hash赋值为0
* 否则调用hash()方法进行计算hash
*/
e.hash = null == e.key ? 0 : hash(e.key);
}
//通过当前遍历旧表的entry的hash值和新table的长度来获取在新表的下标位置
int i = indexFor(e.hash, newCapacity);
/*
* jdk1.7是进行头插法,也就是不需要知道当前下标位置是否存在Entry
* 只需要将旧表中Entry节点,通过计算出下标位置
* 在新添加的Entry中直接将当前下标元素赋值给next属性,然后新添加的节点赋值给当前下标
*/
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}

其中有几个需要关注的方法

//hash()======这个方法简单理解为来通过key来计算hash,在get时通过hash可以确保是同一个entry对象
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()===========
/**
这里使用&于运算符,两个相同为1返回1,否则返回0,例如
0010 1101
1010 1011
结果 0010 1001
*/
static int indexFor(int h, int length) {
return h & (length - 1);
}

我们现在回到resize扩容方法,这个方法中最主要的就是这个将旧数组中数据复制到新数组中这个transfer()方法了,其他的操作上面都有注释,对应着看应该可以看懂

这里再主要说一下indexFor方法,在初始化HashMap时为什么在设置初始大小的时候必须为2的倍数

下面以HashMap初始化大小为16为例

首先&运算符两都为1才为1,否则为0

假设hash值为....1010 1010 而现在hashmap的长度为16,即(16-1)=15

hash:1010 1010
15: 0000 1111

因为15的低四位为1,也就是说通过&位运算符能对结果造成影响的只有低四位的四个1,其他高为都为0

这也是hash()方法的用处尽量让其他位参与hash运算,达到更加分散的hash值

假设初始大小为单数,例如15,那么通过(length - 1);,结果为14,14的二进制为

0000 1110

那么和计算出的hash进行&运算能对结果进行影响的位数会减少1位,这还是好的情况,如果传入的初始大小为17那么会怎样?

17通过length-1的操作为16,16的二进制为0001 0000,那么再和hash值进行&的操作
hash: 1010 1010
16: 0001 0000
只有两种情况,0000 0000 和0001 0000 ,那么设置的hashmap的大小将毫无作用,
只会在0000 0000 和0001 0000 的位置进行put操作,而0000 0000 为0下标,用来添加null的key那么添加的数据将会全部添加 到16的位置!

那我们回到addEntry()方法中

void addEntry(int hash, K key, V value, int bucketIndex) {
/* JDK1.7以后的扩容条件;size大于等于threshold,并且新添加元素所在的索引值不等为空
也就是当size达到或超过threshold,新增加元素,只要不会引起hash冲突则不扩容;
JDK1.8去掉了为null的判断
*/
if ((size >= threshold) && (null != table[bucketIndex])) {
//将大小扩容到原来的两倍
resize(2 * table.length);
//如果key为null,将放到index为0的位置,否则进行取hash的操作
hash = (null != key) ? hash(key) : 0;
//根据获取的hash值进行获取下标
bucketIndex = indexFor(hash, table.length);
}
//创建entry
createEntry(hash, key, value, bucketIndex);
}

resize()方法下面取hash操作的hash()方法和获取下标的indexFor方法都已经在上面写过,这里就不再赘述

接下来主要来看createEntry方法

void createEntry(int hash, K key, V value, int bucketIndex) {
//先获取当前下标entry节点,也可能为null
Entry<K, V> e = table[bucketIndex];
//如果有entry节点,那么在添加新的entry时将会形成链表
table[bucketIndex] = new Entry<>(hash, key, value, e);
//将hashmap的大小加1
size++;
}

因为hash值,所在下标位置都已经获取过了,所以方法传入参数直接使用

到这里put方法中putForNullKey()添加null key的方法就完成了,我们返回put方法继续

//put方法,省略一些刚刚写过的方法
int hash = hash(key);
int i = indexFor(hash, table.length);
//接下来,找到 table[i]处,以及该处的数据链表,看是否存在相同的key;判断key相同,
// 首先判断hash值是否相等,然后再 判断key的equals方法是否相等
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//首先判断hash,如果对象的hashCode方法没有被重写,那么hash值相等两个对象一定相等
//并且判断如果key相等或者key的值相等那么覆盖并返回旧的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++;
//进行添加操作
addEntry(hash, key, value, i);
return null;

最上面hash()和indexFor()方法上面写过,不再赘述,中间的判断覆盖参考注释应该可以理解,而下面的addEntry方法上面也写过

get方法

如果理解了put方法后,get方法会相对简单很多

public V get(Object key) {
//判断如果key等于null的话,直接调用得到nullkey的方法
if (key == null)
return getForNullKey();
//通过getEntry方法的到entry节点
Entry<K, V> entry = getEntry(key);
//判断如果为null返回null,否则返回entry的value
return null == entry ? null : entry.getValue();
}

首先来看key为null的情况

private V getForNullKey() {
//如果hashmap的大小为0返回null
if (size == 0) {
return null;
}
/**
开始研究时有个问题困扰着我,写博客时突然明白了,
问题就是既然已知key为null的entry都会被放入下标0的位置,为什么还要循环,直接获取0下标的entry覆盖不行吗
然后我在写indexFor方法时想到,不仅仅null的key下标为0,如果一个hash算法算完后通过indexFor方法
算出的下标正好是0呢,它就必须通过循环来找到那个key为null的entry
*/
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}

逻辑比较简单,就不解释了,我们回到get看下一个getEntry方法

final Entry<K, V> getEntry(Object key) {
//如果hashmap的大小为0返回null
if (size == 0) {
return null;
}
//判断key如果为null则返回0,否则将key进行hash
int hash = (key == null) ? 0 : hash(key);
//indexFor方法通过hash值和table的长度获取对应的下标
//遍历该下标下的(如果有)链表
for (Entry<K, V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//判断当前entry的key的hash如果和和参入的key相同返回当前entry节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}

到此JDK1.7中HashMap的基本get,put方法就完成了

本文仅个人理解,如果有不对的地方欢迎评论指出或私信,谢谢٩(๑>◡<๑)۶

版权声明
本文为[JameJN]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/sunankang/p/14278837.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?