Java 集合系列07--- HashMap详细介绍(源码解析)----新(一)

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 今天学习了基于JDK1.8的HashMap的源码,主要从如下几个方面来阐述,HashMap的数据结构,HashMap如何支持动态扩容,HashMap的散列函数是如何实现的,并且如何防止散列冲突,最后就是对HashMap的常用方法的源码解析。

前言

今天学习了基于JDK1.8的HashMap的源码,主要从如下几个方面来阐述,HashMap的数据结构,HashMap如何支持动态扩容,HashMap的散列函数是如何实现的,并且如何防止散列冲突,最后就是对HashMap的常用方法的源码解析。

目录

HashMap的数据结构

HashMap的散列函数

散列冲突的处理

HashMap的扩容机制

put 方法的源码解析

get 方法和remove的源码解析

基本的全局常量

1.默认初始化的容器大小16:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  // aka 16  1 左移4位

2.最大的数据容量2的30次方。也就是说最多存放2的30次方个数据

static final int MAXIMUM_CAPACITY = 1 << 30;

3.默认的加载因子 0.75f

static final float DEFAULT_LOAD_FACTOR = 0.75f;

PS: 散列表的加载因子=填入表中的元素个数/散列表的长度

加载因子越大,说明空闲位置越小,冲突越多,散列表的性能会下降。

4. 默认的链表转红黑树的链表长度

static final int TREEIFY_THRESHOLD = 8;

5.默认的红黑树转链表的红黑树节点个数

static final int UNTREEIFY_THRESHOLD = 6;

6.最小的链表树形化的table的大小。

static final int MIN_TREEIFY_CAPACITY = 64;

HashMap的数据结构(基于JDK1.8)

HashMap的数据结构是散列表+链表+红黑树,其中散列表是其基本的数据结构(散列表使用的是桶数组,其实就是一个容量为N的普通数组A[0…N-1]。只不过,在这里我们要将每个单元都想象成一个"桶"(Bucket),每个桶单元里都可以存放一个条目。)。链表是用来存储散列值相同的结点的,当链表的默认长度大于8时链表就可能会转化成红黑树。

其数据结构图如下图所示:

从源码可知,HashMap类中有个非常重要的字段Node<K,V>[] table,即哈希桶数组,其实本质上就是一个数组。而Node是HashMap的一个内部类 ,实现了Map.Entry<K,V>接口,本质上就是一个键值对。

static class Node<K,V> implements Map.Entry<K,V> {
        //用来定位数组索引位置(hash值)
  final int hash;
  //hash表的键
        final K key;
  //存储的值
        V value;
  //链表的下一个结点
        Node<K,V> next;
    }

HashMap的散列函数

散列表中,我们需要一个函数,将任意键key转换为介于0与N-1之间的整数,这个函数就是散列函数(又称哈希函数),散列函数应该要满足如下三点基本要求:


散列函数计算得到的散列值必须是一个非负整数(因为数组的下标不可能是负数)

如果key1=key2, 那么hash(key1)=hash(key2)。

如果key1=/=key2, 那么hash(key1)=/=hash(key2)。

在HashMap中散列函数的实现如下:

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

如上代码我们可以看出hashMap的散列函数是通过调用key的hashCode()方法得到其hashCode值(该方法适用于所有Java对象)。然后再通过hashCode值的高16位异或低16位(其中h >>> 16表示在二进制中将h右移16位)来得到hash值。

最后通过 (n - 1) & hash;(n-1对hash值做按位与运算,也就是求模运算) 得到该键值对的存储位置 。

下面举例说明,n为table的长度

4f2b09445ac7b5cda84f0c3055328819_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1MzQ4MDg=,size_16,color_FFFFFF,t_70.png


散列冲突的处理

当两个key定位到相同的位置是,就会发生散列冲突,散列函数计算结果越分数均匀,散列冲突的概率就会越小,map存储的效率就会越高。在HashMap中是通过链表法来处理,即位置相同的结点会存储到同位置上的链表上。具体的代码实现如下:

//遍历链表
  for (int binCount = 0; ; ++binCount) {
        //当p.next (后继指针)为null时,则设置node结点
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                    }
      //如果键和值已经存在则返回
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }

如上代码所示:散列冲突之后

1.首先遍历链表,在循环中,当p.next (后继指针)为null时,则设置node结点。

2.如果键和值已经存在则直接返回已经存在的数据。

HasMap的扩容机制

如果哈希桶数组很大,即使较差的散列函数也会比较分散,如果哈希桶数组很小,即使再好的散列函数,也会出现较多的散列冲突。所以,我们需要权衡时间成本和空间成本上权衡。其实就是根据实际情况确定哈希桶数组大小。并在此基础上设计较好的散列函数,HashMap就是通过良好的散列函数加扩容机制来控制map使得Hash碰撞较小。介绍扩容机制之前,我们需要知道几个重要的属性

int threshold;  //map所能容纳的键值对的极限
  final float loadFactor;   //装载因子
  int modCount;  //记录HashMap被结构修改的次数,用于fast-fail
  int size;  //map中包含的key-value的个数

HashMap的构造器主要是给这几个属性设值。 正如前面说到的HashMap默认的容器大小(capacity)是16,默认的转载因子(loadFactor)是0.75,而 threshold=loadFactor*capacity,也就是说转载因子越大,map所能容纳的键值对就越多。 当HashMap中元素的个数超过threshold就会启动扩容,每次扩容都会扩容到原来的两倍大小。默认的装载因子0.75是对空间和效率的一种平衡选择,建议大家不要修改。而size 表示HashMap中实际存在的键值对数量,modCount字段主要是用来记录HashMap内部结构发生变化的次数,主要用于迭代快速失败。例如put新键值对,但是对某个key对应的value值覆盖不属于结构变化。

其扩容主要分为如下两步:

1.创建一个新的两倍于原容量的数组。

2.循环将原数组中的数据移到新数组中。

具体代码如下:

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) { //不是初始化,走扩容流程
            //超过最大值就不在扩容
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //扩容后的容量是原来的2倍,左移一位就可以将数据翻倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; //向左位移一位,达到原阀值的2倍。
        }
        else if (oldThr > 0) // 初始化容量,容量大小是threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            //容量,阀值指定初值
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //计算新的resize上限
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        //建立新容量数组
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            //遍历原来的数组,把所有的元素都转移到新数组上去
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null; //原数组置空,以便GC
                    if (e.next == null)  //原数组该位置无冲突,正常存放
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)  // 原数组在这个位置上是一个红黑树
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {// 原数组该位置冲突,但是还未达到树形化阈值,因此还是链表结构
                        // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            // 循环链表转移至新数组
                            next = e.next;
                            //原索引
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            //原索引+oldCap
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //原索引放在bucket里
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //原索引+oldCap放在bucket里
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小(也就是数组的长度)。其中的哈希桶数组table的size=2, 所以key = 3、7、5,put顺序依次为 3、7、5。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1,即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4,然后所有的Node重新rehash的过程。

a013e4d14fee7dbf8fc6575f67a957b9_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1MzQ4MDg=,size_16,color_FFFFFF,t_70.png

经过观测可以发现,我们使用的是2次幂的扩展(指长度扩为原来的两倍),所以元素的位置要么在原来位置,要么是在原来位置再移动2次幂的位置,看下图就可以明白这句话的意思,n为table的长度,图(a)表示扩容前key1和key2确定的索引位置示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。

04ffb630c670b4a725920e4e18868117_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1MzQ4MDg=,size_16,color_FFFFFF,t_70.png

元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色) 因此新的index就会发生这样的变化:

resize 00101=5 原位置

0101=5 ————>

16==>2*16 10101=21=5+16 原位置+oldCap

因此,我们在扩充HashMap的时候,不在需要像JDK1.7实现的那样重新计算hash。只需要看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引就变成 原索引+oldCap,可以看看下图为16扩充为32的resize示意图:

0f722d2ffe4421fc42e3d76fcf782690_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1MzQ4MDg=,size_16,color_FFFFFF,t_70.png

相关文章
|
4天前
|
Java Apache Maven
Java百项管理之新闻管理系统 熟悉java语法——大学生作业 有源码!!!可运行!!!
文章提供了使用Apache POI库在Java中创建和读取Excel文件的详细代码示例,包括写入数据到Excel和从Excel读取数据的方法。
20 6
Java百项管理之新闻管理系统 熟悉java语法——大学生作业 有源码!!!可运行!!!
|
4天前
|
JSON 前端开发 Java
震惊!图文并茂——Java后端如何响应不同格式的数据给前端(带源码)
文章介绍了Java后端如何使用Spring Boot框架响应不同格式的数据给前端,包括返回静态页面、数据、HTML代码片段、JSON对象、设置状态码和响应的Header。
33 1
震惊!图文并茂——Java后端如何响应不同格式的数据给前端(带源码)
|
2天前
|
安全 Java 编译器
Java 泛型深入解析:类型安全与灵活性的平衡
Java 泛型通过参数化类型实现了代码重用和类型安全,提升了代码的可读性和灵活性。本文深入探讨了泛型的基本原理、常见用法及局限性,包括泛型类、方法和接口的使用,以及上界和下界通配符等高级特性。通过理解和运用这些技巧,开发者可以编写更健壮和通用的代码。
|
4天前
|
自然语言处理 Java 数据处理
Java IO流全解析:字节流和字符流的区别与联系!
Java IO流全解析:字节流和字符流的区别与联系!
17 1
|
4天前
|
存储 前端开发 Java
Java后端如何进行文件上传和下载 —— 本地版(文末配绝对能用的源码,超详细,超好用,一看就懂,博主在线解答) 文件如何预览和下载?(超简单教程)
本文详细介绍了在Java后端进行文件上传和下载的实现方法,包括文件上传保存到本地的完整流程、文件下载的代码实现,以及如何处理文件预览、下载大小限制和运行失败的问题,并提供了完整的代码示例。
49 1
|
5天前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
24 2
|
8天前
|
存储 算法 安全
深入理解Java中的集合框架
【9月更文挑战第34天】本文将带你走进Java的集合框架,探索其背后的设计哲学和实现细节。我们将从集合的基本概念出发,逐步深入到具体的接口和类的实现,最后通过一个实际的例子来展示如何在Java程序中高效地使用集合。无论你是初学者还是有经验的开发者,这篇文章都将为你提供新的视角和深度理解。
13 1
|
1天前
|
Java
Java 集合存在相同属性,其他元素累加
Java 集合存在相同属性,其他元素累加
|
3天前
|
监控 数据可视化 搜索推荐
医院绩效核算系统源码开发,平衡计分卡在绩效管理中的应用解析
医院绩效核算系统是专为医疗机构设计的系统,通过科学方法评估科室和员工绩效,与HIS系统集成,确保数据准确实时。核心功能包括战略导向配置、现代技术架构、自动数据集成、灵活绩效核算机制及模块化管理,支持RBRVS、DRGs等多种考核方法,确保全面科学评估。采用平衡计分卡等工具,实现多维度绩效管理,促进组织持续改进与发展。
|
4天前
|
存储 分布式计算 Java
Stream很好,Map很酷,但答应我别用toMap():Java开发中的高效集合操作
在Java的世界里,Stream API和Map集合无疑是两大强大的工具,它们极大地简化了数据处理和集合操作的复杂度。然而,在享受这些便利的同时,我们也应当警惕一些潜在的陷阱,尤其是当Stream与Map结合使用时。本文将深入探讨Stream与Map的优雅用法,并特别指出在使用toMap()方法时需要注意的问题,旨在帮助大家在工作中更高效、更安全地使用这些技术。
17 0

推荐镜像

更多