【JAVA学习之路 | 进阶篇】HashMap源码剖析

简介: 【JAVA学习之路 | 进阶篇】HashMap源码剖析

1.JDK7版本创建与添加数据的的过程

(1). HashMap<String, Integer> map =new HashMap<>();


//创建对象过程中,底层会初始化数组Entry[] table =new Object[16];16是2的倍数.


...


map.put("hexua", 66);


将"hexua"和66封装到一个Entry对象entry中.并将此对象添加到table数组中.

(2). 添加修改的过程.

将(key1, value1)添加到当前的map中
首先需要调用key1所在类的hashCode()方法,计算key1对象的哈希值1(往往是根据key1中的属性计算的), 此哈希值再经过hash()方法后,得到哈希值2,哈希值2再经过indexFor方法后,确定了(key1, value1)在table数组中的索引位置i;
    |----> 如果此索引位置上没有元素(table[i] == null), 则(key1, value1)添加成功
    |---->如果此索引位置上已有元素(key2, value2), 则需要比较key2,key1的哈希值2是否相等.
          |---->如果二者的哈希值2不相等,则(key1, value1)添加成功
          |---->如果二者还相等,则继续比较二者的equals();调用key1的equals,key2作为参数传入
                |---->如果equals返回flase,添加成功
                |---->返回true,说明key1,key2是相同的,默认情况下,value1替换value2;

说明 :

  • 如果索引i处无元素,(key1, value1)被添加到该索引处.
  • 如果索引i处只有一个元素,则(key1, value1)与(key2, value2)构成单向链表.如果索引i处有一条单向链表,则按照头插法插入到该链表中.

(3). 随着不断插入数据,在满足下列条件的情况下,可以考虑扩容.


(size >=threshoud) && (null !=table[i])


  • threshold为临界值,当添加的元素的个数>threshold(数组的长度*加载因子,加载因子一般被初始化为0.75f)时.考虑扩容.
  • 默认的临界值 : 16*0.75=12.默认扩容为原来的两倍.始终保证数组的长度是2的整数倍.

2.JDK8与JDK7的不同之处

(因为我下载的是JDK17版本,听说17与8版本差别不大,所以在此查看的是17版本的源码.)

(1).

HashMap<String, Integer> map =new HashMap<>();

//底层并不会初始化数组.只是做了一个初始化操作.

public HashMap() {
     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
loadFactor是加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
DEFAULT_LOAD_FACTOR全局常量为0.75

当首次put(key1, value1)时,才会初始化数组.

put方法底层会调用到putVal方法.

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

首先key被扔到hash()方法中,我们查看hash方法的源码.

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

先调用key的hashCode()方法计算得到的哈希值1,再进行计算,得到哈希值2.并将哈希值2返回作为putVal方法的实参传入.

我们再看putVal方法的源码.

table是Node类型的数组.Node实现了Map.Entry接口.类似于JDK7中的Entry类.

transient Node<K,V>[] table;
 
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
 
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

第一个if判断table是否分配了的内存空间,第一次put(key1, value1),table =null.所以table调用了resize()方法,初始化table数组.

我们再查看resize()源码.

oldTable指向了table.而且oldCap等于0.所以并没有进入到前面的if(oldCap >0)等语句中.直接看else语句.

else {        // zero initial threshold signifies using defaults
      newCap = DEFAULT_INITIAL_CAPACITY;
      newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
 
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

可以清晰的看到 :

newCap为初始化时数组的长度.即16.

newThr为初始化时数组的临界值,即12.

截取了部分代码.可以看到,底层new了一个长度为16的Node类型的数组.而且将数组返回.

按住Ctrl+Alt+←

再查看putVal源码.

if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

第二个if语句中,(n-1)&hash求出索引i.如果tab[i]为null意味着此处无元素,那么将新new的Node对象放到该数组位置上.


至于(n-1)&hash设计的很巧妙.由于n为数组的长度.数组的长度都是2的倍数.如初始化时数组的长度为16.n-1用二进制表示为1111.那么只需对比hash二进制表示的后四位进行位运算.计算得到的索引必然也是在0到15内.这也是为什么每次数组扩容默认的都是2倍的原因.


因为执行了上面的if语句,下面的else语句跳过.执行第三个if语句.

如果++size>临界值,那么将扩容.

相关文章
|
3天前
|
Java
Java 实现 捕鱼达人 小游戏【附源码】
Java 实现 捕鱼达人 小游戏【附源码】
7 0
|
3天前
|
Java
Java实现一个坦克大战的小游戏【附源码】
Java实现一个坦克大战的小游戏【附源码】
8 0
|
4天前
|
传感器 小程序 搜索推荐
(源码)java开发的一套(智慧校园系统源码、电子班牌、原生小程序开发)多端展示:web端、saas端、家长端、教师端
通过电子班牌设备和智慧校园数据平台的统一管理,在电子班牌上,班牌展示、学生上课刷卡考勤、考勤状况汇总展示,课表展示,考场管理,请假管理,成绩查询,考试优秀标兵展示、校园通知展示,班级文化各片展示等多种化展示。
27 0
(源码)java开发的一套(智慧校园系统源码、电子班牌、原生小程序开发)多端展示:web端、saas端、家长端、教师端
|
2天前
|
存储 Java 测试技术
滚雪球学Java(61):从源码角度解读Java Set接口底层实现原理
【6月更文挑战第15天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
9 1
滚雪球学Java(61):从源码角度解读Java Set接口底层实现原理
|
2天前
|
存储 安全 Java
深入解析Java HashMap的高性能扩容机制与树化优化
深入解析Java HashMap的高性能扩容机制与树化优化
6 1
|
3天前
|
Java
Java 实现 植物大战僵尸 小游戏【附源码】
Java 实现 植物大战僵尸 小游戏【附源码】
7 3
|
3天前
|
Java
Java 实现 贪吃蛇 小游戏【附源码】
Java 实现 贪吃蛇 小游戏【附源码】
7 0
|
3天前
|
Java
Java 实现 1024 小游戏【附源码】
Java 实现 1024 小游戏【附源码】
9 2
|
3天前
|
Java
Java实现一个打飞机的小游戏【附源码】
Java实现一个打飞机的小游戏【附源码】
14 0
|
3天前
|
Java
java中如何确保一个集合不能被修改? - 源码解读详细--JavaPub版本
java中如何确保一个集合不能被修改? - 源码解读详细--JavaPub版本
6 2