史上最全的Java容器集合之HashMap(源码解读)(上)

本文涉及的产品
容器镜像服务 ACR,镜像仓库100个 不限时长
容器服务 Serverless 版 ACK Serverless,317元额度 多规格
容器服务 Serverless 版 ACK Serverless,952元额度 多规格
简介: 前言文本已收录至我的GitHub仓库,欢迎Star:github.com/bin39232820…种一棵树最好的时间是十年前,其次是现在

前言


文本已收录至我的GitHub仓库,欢迎Star:github.com/bin39232820…

种一棵树最好的时间是十年前,其次是现在

絮叨


equals和hashCode理解了,接下来就是HashMap了,这个也是平时我们工作中用的最多的容器之一

🔥史上最全的Java容器集合之入门

🔥史上最全的Java容器集合之基础数据结构(手撕链表)

🔥史上最全的Java容器集合之ArrayList(源码解读)

🔥史上最全的Java容器集合之Vector和LinkedList(源码解读)

🔥史上最全的Java容器集合之equals 和 hashCode


因为HashMap的源码确实比List要多很多,这边也不能说面面俱到,只能挑一些重点的东西讲。


一 什么是Map


  • Map是一个接口,他是key-value的键值对,一个map不能包含重复的key,并且每一个key只能映射一个value;
  • Map接口提供了三个集合视图:key的集合,value的集合,key-value的集合;
  • Map内元素的顺序取决于Iterator的具体实现逻辑,获取集合内的元素实际上是获取一个迭代器,实现对其中元素的遍历;
  • Map接口的具体实现中存在三种Map结构,其中HashMap和TreeMap都允许存在null值,而HashTable的key不允许为空,但是HashMap不能保证遍历元素的顺序,TreeMap能够保证遍历元素的顺序。


二 HashMap中的几个概念


什么是哈希表

哈希表(HashTable,散列表)是根据key-value进行访问的数据结构,他是通过把key映射到表中的一个位置来访问value,加快查找的速度,其中映射的函数叫做散列函数,存放value的数组叫做散列表,哈希表的主干是数组。


上面的图中就是一个值插入哈希表中的过程,那么存在的问题就是不同的值在经过hash函数之后可能会映射到相同的位置上,当插入一个元素时,发现该位置已经被占用,这时候就会产生冲突,也就是所谓的哈希冲突,因此哈希函数的设计就至关重要,一个好的哈希函数希望尽可能的保证计算方法简单,但是元素能够均匀的分布在数组中,但是数组是一块连续的且是固定长度的内存空间,不管一个哈希函数设计的多好,都无法避免得到的地址不会发生冲突,因此就需要对哈希冲突进行解决。 (1)开放定址法:当插入一个元素时,发生冲突,继续检查散列表的其他项,直到找到一个位置来放置这个元素,至于检查的顺序可以自定义;


(2)再散列法:使用多个hash函数,如果一个发生冲突,使用下一个hash函数,直到找到一个位置,这种方法增加了计算的时间;

(3)链地址法:在数组的位置使用链表,将同一个hashCode的元素放在链表中,HashMap就是使用的这种方法,数组+链表的结构。


关于 HashMap 源码中提到的几个重要概念


  • 哈希桶(buckets):在 HashMap 的注释里使用哈希桶来形象的表示数组中每个地址位置。注意这里并不是数组本身,数组是装哈希桶的,他可以被称为哈希表。
  • 初始容量(initial capacity) : 这个很容易理解,就是哈希表中哈希桶初始的数量。如果我们没有通过构造方法修改这个容量值默认为DEFAULT_INITIAL_CAPACITY = 1<<4 即16。值得注意的是为了保证 HashMap 添加和查找的高效性,HashMap 的容量总是 2^n 的形式。
  • 加载因子(load factor):加载因子是哈希表(散列表)在其容量自动增加之前被允许获得的最大数量的度量。当哈希表中的条目数量超过负载因子和当前容量的乘积时,散列表就会被重新映射(即重建内部数据结构),重新创建的散列表容量大约是之前散列表哈系统桶数量的两倍。默认加载因子(0.75)在时间和空间成本之间提供了良好的折衷。加载因子过大会导致很容易链表过长,加载因子很小又容易导致频繁的扩容。所以不要轻易试着去改变这个默认值。
  • 扩容阈值(threshold):其实在说加载因子的时候已经提到了扩容阈值了,扩容阈值 = 哈希表容量 * 加载因子。哈希表的键值对总数 = 所有哈希桶中所有链表节点数的加和,扩容阈值比较的是是键值对的个数而不是哈希表的数组中有多少个位置被占了。
  • 树化阀值(TREEIFY_THRESHOLD) :这个参数概念是在 JDK1.8后加入的,它的含义代表一个哈希桶中的节点个数大于该值(默认为8)的时候将会被转为红黑树行存储结构。
  • 非树化阀值(UNTREEIFY_THRESHOLD): 与树化阈值相对应,表示当一个已经转化为数形存储结构的哈希桶中节点数量小于该值(默认为 6)的时候将再次改为单链表的格式存储。导致这种操作的原因可能有删除节点或者扩容。
  • 最小树化容量(MIN_TREEIFY_CAPACITY): 经过上边的介绍我们只知道,当链表的节点数超过8的时候就会转化为树化存储,其实对于转化还有一个要求就是哈希表的数量超过最小树化容量的要求(默认要求是 64),且为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD);在达到该有求之前优先选择扩容。扩容因为因为容量的变化可能会使单链表的长度改变。


HashMap的类图


HashMap继承自AbstractMap,实现了Map接口,Map接口定义了所有Map子类必须实现的方法。AbstractMap也实现了Map接口,并且提供了两个实现Entry的内部类:SimpleEntry和SimpleImmutableEntry。


HashMap是基于哈希表的Map接口的实现,提供所有可选的映射操作,允许使用null值和null键,存储的对象时一个键值对对象Entry<K,V>, 是基于数组+链表的结构实现,在内部维护这一个数组table,数组的每个位置保存着每个链表的表头结点,查找元素时,先通过hash函数得到key值对应的hash值,再根据hash值得到在数组中的索引位置,拿到对应的链表的表头,最后去遍历这个链表,得到对应的value值。



HashMap类中的主要方法


常量

// 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; 
    // 默认的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶(bucket)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8; 
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组,总是2的幂次倍
    transient Node<k,v>[] table; 
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数,注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;   
    // 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容
    int threshold;
    // 加载因子
    final float loadFactor;
复制代码


HashMap的Node实体

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; // 哈希值,存放元素到hashmap中时用来与其他元素hash值比较
        this.key = key;
        this.value = value;
        this.next = next;
    }
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    // 重写hashCode()方法
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    // 重写 equals() 方法
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))
                return true;
            }
        return false;
    }
}
复制代码


其中key值定义的为final,因此在定义之后就无法进行修改,key和value就是在调用map时对应的键值对,next存储的是链表中的下一个节点,他是一个单链表,hash是对key的hashcode再次进行哈希运算之后得到的值,存储起来是为了避免重复计算。

相关文章
|
14天前
|
存储 Java
深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。
【10月更文挑战第16天】本文深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。HashSet基于哈希表实现,添加元素时根据哈希值分布,遍历时顺序不可预测;而TreeSet利用红黑树结构,按自然顺序或自定义顺序存储元素,确保遍历时有序输出。文章还提供了示例代码,帮助读者更好地理解这两种集合类型的使用场景和内部机制。
32 3
|
14天前
|
存储 Java 数据处理
Java Set接口凭借其独特的“不重复”特性,在集合框架中占据重要地位
【10月更文挑战第16天】Java Set接口凭借其独特的“不重复”特性,在集合框架中占据重要地位。本文通过快速去重和高效查找两个案例,展示了Set如何简化数据处理流程,提升代码效率。使用HashSet可轻松实现数据去重,而contains方法则提供了快速查找的功能,彰显了Set在处理大量数据时的优势。
26 2
|
6天前
|
JavaScript Java 项目管理
Java毕设学习 基于SpringBoot + Vue 的医院管理系统 持续给大家寻找Java毕设学习项目(附源码)
基于SpringBoot + Vue的医院管理系统,涵盖医院、患者、挂号、药物、检查、病床、排班管理和数据分析等功能。开发工具为IDEA和HBuilder X,环境需配置jdk8、Node.js14、MySQL8。文末提供源码下载链接。
|
11天前
|
安全 Java 程序员
深入Java集合框架:解密List的Fail-Fast与Fail-Safe机制
本文介绍了 Java 中 List 的遍历和删除操作,重点讨论了快速失败(fail-fast)和安全失败(fail-safe)机制。通过普通 for 循环、迭代器和 foreach 循环的对比,详细解释了各种方法的优缺点及适用场景,特别是在多线程环境下的表现。最后推荐了适合高并发场景的 fail-safe 容器,如 CopyOnWriteArrayList 和 ConcurrentHashMap。
39 5
|
9天前
|
移动开发 前端开发 JavaScript
java家政系统成品源码的关键特点和技术应用
家政系统成品源码是已开发完成的家政服务管理软件,支持用户注册、登录、管理个人资料,家政人员信息管理,服务项目分类,订单与预约管理,支付集成,评价与反馈,地图定位等功能。适用于各种规模的家政服务公司,采用uniapp、SpringBoot、MySQL等技术栈,确保高效管理和优质用户体验。
|
12天前
|
安全 Java 程序员
Java集合之战:ArrayList vs LinkedList,谁才是你的最佳选择?
本文介绍了 Java 中常用的两个集合类 ArrayList 和 LinkedList,分析了它们的底层实现、特点及适用场景。ArrayList 基于数组,适合频繁查询;LinkedList 基于链表,适合频繁增删。文章还讨论了如何实现线程安全,推荐使用 CopyOnWriteArrayList 来提升性能。希望帮助读者选择合适的数据结构,写出更高效的代码。
40 3
|
14天前
|
Java 开发者
在Java集合世界中,Set以其独特的特性脱颖而出,专门应对重复元素
在Java集合世界中,Set以其独特的特性脱颖而出,专门应对重复元素。通过哈希表和红黑树两种模式,Set能够高效地识别并拒绝重复元素的入侵,确保集合的纯净。无论是HashSet还是TreeSet,都能在不同的场景下发挥出色的表现,成为开发者手中的利器。
24 2
|
3天前
|
Java API Apache
java集合的组内平均值怎么计算
通过本文的介绍,我们了解了在Java中计算集合的组内平均值的几种方法。每种方法都有其优缺点,具体选择哪种方法应根据实际需求和场景决定。无论是使用传统的循环方法,还是利用Java 8的Stream API,亦或是使用第三方库(如Apache Commons Collections和Guava),都可以有效地计算集合的组内平均值。希望本文对您理解和实现Java中的集合平均值计算有所帮助。
11 0
|
3天前
|
Kubernetes 监控 开发者
掌握容器化:Docker与Kubernetes的最佳实践
【10月更文挑战第26天】本文深入探讨了Docker和Kubernetes的最佳实践,涵盖Dockerfile优化、数据卷管理、网络配置、Pod设计、服务发现与负载均衡、声明式更新等内容。同时介绍了容器化现有应用、自动化部署、监控与日志等开发技巧,以及Docker Compose和Helm等实用工具。旨在帮助开发者提高开发效率和系统稳定性,构建现代、高效、可扩展的应用。
|
15天前
|
存储 Docker 容器
docker中挂载数据卷到容器
【10月更文挑战第12天】
42 5

热门文章

最新文章