深入Java集合系列之三:HashMap

简介:

前言

无意中发现有很多对Map尤其是HashMap的线程安全性的话题讨论,在我的理解中,对HashMap的理解中也就知道它是线程不安全的,以及HashMap的底层算法采用了链地址法来解决哈希冲突的知识,但是对其线程安全性的认知有限,故写这篇博客的目的就是让和我对这块内容不熟悉的小伙伴有一个对HashMap更深的认知,为了让你更好的查看你感兴趣的内容,你也可以直接点击右边的文章目录进行阅读。

写这篇文章是在一年前,这里只是重新发表

哈希表

在数据结构中有一种称为哈希表的数据结构,它实际上是数组的推广。如果有一个数组,要最有效的查找某个元素的位置,如果存储空间足够大,那么可以对每个元素和内存中的某个地址对应起来,然后把每个元素的地址用一个数组(这个数组也称为哈希表)存储起来,然后通过数组下标就可以直接找到某个元素了。这种方法术语叫做直接寻址法。这种方法的关键是要把每个元素和某个地址对应起来,所以如果当一组数据的取值范围很大的时候,而地址的空间又有限,那么必然会有多个映射到同一个地址,术语上称为哈希冲突,这时映射到同一个地址的元素称为同义词。毕竟,存储空间有限,所以冲突是不可避免的,但是可以尽量做到减少冲突。目前有两种比较有效的方法来解决哈希冲突:

  • 链地址法
  • 开放地址法

这里简要说明一下开放地址法,顾名思义,就是哈希表中的每个位置要么存储了一个元素要么为NULL。当数据比较多的时候,查找一个元素挺费事的,但是可以使用探测的方法进行查找。这个话题与本主题关系不大,感兴趣的小伙伴可以自行研究。

链地址法

为什么要把链地址法单独拿出来呢?因为后面有用。
链地址法的大概思想是:对于每个关键字,使用哈希函数确定其在哈希表中位置(也就是下标),如果该位置没有元素则直接映射到该地址;如果该位置已经有元素了,就把该元素连接到已存在元素的尾部,也就是一个链表,并把该元素的next设置为null。这样的话,每个哈希表的位置都可能存在一个链表,这种方式要查找某个元素效率比较高,时间复杂度为O(1+a),a为哈希表中每个位置链表的平均长度。这里需要假设每个元素都被等可能映射到哈希表中的任意一个位置。

下面这张图展示了链地址法的过程:

链地址法

HashMap


HashMap底层实现

HashMap允许使用null作为key或者value,并且HashMap不是线程安全的,除了这两点外,HashMap与Hashtable大致相同,下面是官方API对HashMap的描述:

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

如果有多个线程对Hash映射进行访问,那么至少有一个线程会对哈希映射进行结构的修改:

结构上的修改是指添加或删除一个或多个映射关系的任何操作;仅改变与实例已经包含的键关联的值不是结构上的修改

那么很显然,当多个线程同时(严格来说不能称为同时,因为CPU每次只能允许一个线程获取资源,只不过时间上非常短,CPU运行速度很快,所以理解为同时)修改哈希映射,那么最终的哈希映射(就是哈希表)的最终结果是不能确定的,这只能看CPU心情了。如果要解决这个问题,官方的参考方案是保持外部同步,什么意思?看下面的代码就知道了:

Map m = Collections.synchronizedMap(new HashMap(...));
AI 代码解读

但是不建议这么使用,因为当多个并发的非同步操作修改哈希表的时候,最终结果不可预测,所以使用上面的方法创建HashMap的时候,当有多个线程并发访问哈希表的情况下,会抛出异常,所以并发修改会失败。比如下面这段代码:

for (int i = 0; i < 20; i++) {
        collectionSynMap.put(i, String.valueOf(i));
    }
    Set<Entry<Integer,String>> keySets = collectionSynMap.entrySet();
    Iterator<Entry<Integer, String>> keySetsIterator = keySets.iterator();
    try {
        while(keySetsIterator.hasNext()){
            Entry<Integer,String> entrys = (Entry<Integer, String>) keySetsIterator.next();
            System.out.println(entrys.getValue());
            if(entrys.getValue().equals("1")){
                System.out.println(entrys.getValue());
                collectionSynMap.remove(1);
                //keySetsIterator.remove();
            }
        }
    } catch (Exception e) {
        e.printStackTrace();
    }
AI 代码解读

就会抛出ConcurrentModificationException异常,因为在使用迭代器遍历的时候修改映射结构,但是使用代码中注释的删除是不会抛出异常的。

通过上面的分析,我们初步了解HashMap的非线程安全的原理,下面从源码的角度分析一下,为什么HashMap不是线程安全的:

public V put(K key, V value) {
    //这里省略了对重复键值的处理代码
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}
AI 代码解读

那么问题应该处在addEntry()上,下面来看看其源码:

void addEntry(int hash, K key, V value, int bucketIndex) {
    //如果达到Map的阈值,那么就扩大哈希表的容量
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //扩容
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    //创建Entry键值对,此处省略这部分代码
}
AI 代码解读

假设有线程A和线程B都调用addEntry()方法,线程A和B会得到当前哈希表位置的头结点(就是上面链地址法的第一个元素),并修改该位置的头结点,如果是线程A先获取头结点,那么B的操作就会覆盖线程A的操作,所以会有问题。

下面再看看resize方法的源码:

void resize(int newCapacity) {
    //此处省略如果达到阈值扩容为原来两倍的过程代码
    Entry[] newTable = new Entry[newCapacity];
    //把当前的哈希表转移到新的扩容后的哈希表中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
AI 代码解读

所以如果有多个线程执行put方法,并调用resize方法,那么就会出现多种情况,在转移的过程中丢失数据,或者扩容失败,都有可能,所以从源码的角度分析这也是线程不安全的。

HashMap测试代码

    for (int i = 0; i < 40; i++) {
        hashMap.put(i, String.valueOf(i));
    }
    Set<Entry<Integer,String>> keySets = hashMap.entrySet();
    final Iterator<Entry<Integer, String>> keySetsIterator = keySets.iterator();
    Thread t3 = new Thread(){
        public void run(){
            try {
                while(keySetsIterator.hasNext()){
                    Entry<Integer,String> entrys = (Entry<Integer, String>) keySetsIterator.next();
                    System.out.println(entrys.getValue());
                    if(entrys.getValue().equals("1")){
                        System.out.println(entrys.getValue());
                        hashMap.remove(1);
                    }
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    };
    Thread t4 = new Thread(){
        public void run(){
            try {
                while(keySetsIterator.hasNext()){
                    Entry<Integer,String> entrys = (Entry<Integer, String>) keySetsIterator.next();
                    System.out.println(entrys.getValue());
                    if(entrys.getValue().equals("1")){
                        System.out.println(entrys.getValue());
                        hashMap.remove(1);
                    }
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    };
    t3.start();
    t4.start();
AI 代码解读

这段代码启动了两个线程并发修改HashMap的映射关系,所以会抛出两个ConcurrentModificationException异常,通过这段测试代码在此证明了HashMap的非线程安全。

目录
打赏
0
0
0
0
85
分享
相关文章
JUC并发—1.Java集合包底层源码剖析
本文主要对JDK中的集合包源码进行了剖析。
Java 集合面试题 PDF 下载及高频考点解析
本文围绕Java集合面试题展开,详细解析了集合框架的基本概念、常见集合类的特点与应用场景。内容涵盖`ArrayList`与`LinkedList`的区别、`HashSet`与`TreeSet`的对比、`HashMap`与`ConcurrentHashMap`的线程安全性分析等。通过技术方案与应用实例,帮助读者深入理解集合类的特性和使用场景,提升解决实际开发问题的能力。文末附带资源链接,供进一步学习参考。
54 4
现代应用场景中 Java 集合框架的核心技术与实践要点
本内容聚焦Java 17及最新技术趋势,通过实例解析Java集合框架的高级用法与性能优化。涵盖Record类简化数据模型、集合工厂方法创建不可变集合、HashMap初始容量调优、ConcurrentHashMap高效并发处理、Stream API复杂数据操作与并行流、TreeMap自定义排序等核心知识点。同时引入JMH微基准测试与VisualVM工具分析性能,总结现代集合框架最佳实践,如泛型使用、合适集合类型选择及线程安全策略。结合实际案例,助你深入掌握Java集合框架的高效应用与优化技巧。
64 4
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
108 3
Java 集合框架中的老炮与新秀:HashTable 和 HashMap 谁更胜一筹?
嗨,大家好,我是技术伙伴小米。今天通过讲故事的方式,详细介绍 Java 中 HashMap 和 HashTable 的区别。从版本、线程安全、null 值支持、性能及迭代器行为等方面对比,帮助你轻松应对面试中的经典问题。HashMap 更高效灵活,适合单线程或需手动处理线程安全的场景;HashTable 较古老,线程安全但性能不佳。现代项目推荐使用 ConcurrentHashMap。关注我的公众号“软件求生”,获取更多技术干货!
114 3
|
3月前
|
Java LinkedList集合的深度剖析
总的来说,我希望像说故事一样讲解Java LinkedList集合的使用和实现原理,让有些许枯燥的编程知识变得趣味盎然。在这个“公交车”故事中,你不仅熟悉了LinkedList集合的实现和使用,而且还更深入地理解了数据结构中的链表。链表可能会因为插入和删除的便利性而被选用,虽然它的查找效率并不高,但是在很多场景中仍然十分有效。这就像公交车,虽然它速度不快,但却是城市出行的重要工具。
73 8
Java HashMap详解及实现原理
Java HashMap是Java集合框架中常用的Map接口实现,基于哈希表结构,允许null键和值,提供高效的存取操作。它通过哈希函数将键映射到数组索引,并使用链表或红黑树解决哈希冲突。HashMap非线程安全,多线程环境下需注意并发问题,常用解决方案包括ConcurrentHashMap和Collections.synchronizedMap()。此外,合理设置初始化容量和加载因子、重写hashCode()和equals()方法有助于提高性能和避免哈希冲突。
229 17
Java HashMap详解及实现原理
|
3月前
|
Java 集合框架详解:系统化分析与高级应用
本文深入解析Java集合框架,涵盖List、Set、Map等核心接口及其常见实现类,如ArrayList、HashSet、HashMap等。通过对比不同集合类型的特性与应用场景,帮助开发者选择最优方案。同时介绍Iterator迭代机制、Collections工具类及Stream API等高级功能,提升代码效率与可维护性。适合初学者与进阶开发者系统学习与实践。
95 0
java常见的集合类有哪些
Map接口和Collection接口是所有集合框架的父接口: 1. Collection接口的子接口包括:Set接口和List接口 2. Map接口的实现类主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap以及 Properties等 3. Set接口的实现类主要有:HashSet、TreeSet、LinkedHashSet等 4. List接口的实现类主要有:ArrayList、LinkedList、Stack以及Vector等
【Java集合类面试二十五】、有哪些线程安全的List?
线程安全的List包括Vector、Collections.SynchronizedList和CopyOnWriteArrayList,其中CopyOnWriteArrayList通过复制底层数组实现写操作,提供了最优的线程安全性能。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等