热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HashMap和ConcurrentHashMap的区别,HashMap的底层源码。   

Hashmap本质是数组加链表。根据key取得hash值,然后计算出数组下标,如果多个key对应到同一个下标,就用链表串起来,新插入的在前面。ConcurrentHashMap:在

  Hashmap本质是数组加链表。根据key取得hash值,然后计算出数组下标,如果多个key对应到同一个下标,就用链表串起来,新插入的在前面。

  ConcurrentHashMap:在hashMap的基础上,ConcurrentHashMap将数据分为多个segment,默认16个(concurrency level),然后每次操作对一个segment加锁,避免多线程锁的几率,提高并发效率。

一、HashMap概述

 

  HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

 

  值得注意的是HashMap不是线程安全的,如果想要线程安全的HashMap,可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。

1  Map map = Collections.synchronizedMap(new HashMap());

 

二、HashMap的数据结构

 HashMap的底层主要是基于数组和链表来实现的,它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置,能够很快的计算出对象所存储的位置。HashMap中主要是通过key的hashCode来计算hash值的,只要hashCode相同,计算出来的hash值就一样。如果存储的对象对多了,就有可能不同的对象所算出来的hash值是相同的,这就出现了所谓的hash冲突。学过数据结构的同学都知道,解决hash冲突的方法有很多,HashMap底层是通过链表来解决hash冲突的。

                                      HashMap和ConcurrentHashMap的区别,HashMap的底层源码。
    





		
 
 
 

从上图中可以看出,HashMap底层就是一个数组结构,数组中存放的是一个Entry对象,如果产生的hash冲突,也就是说要存储的那个位置上面已经存储了对象了,这时候该位置存储的就是一个链表了。我们看看HashMap中Entry类的代码:

 1 static class Entry implements Map.Entry {
 2         final K key;
 3         V value;
 4         Entry next;
 5         final int hash;
 6 
 7         /**
 8          * Creates new entry.
 9          */
10         Entry(int h, K k, V v, Entry n) {
11             value = v;
12             next = n; //hash值冲突后存放在链表的下一个
13             key = k;
14             hash = h;
15         }
16 
17         .........
18     }

HashMap其实就是一个Entry数组,Entry对象中包含了键和值,其中next也是一个Entry对象,它就是用来处理hash冲突的,形成一个链表。

三、HashMap源码分析

  先看看HashMap类中的一些关键属性:

1 transient Entry[] table;//存储元素的实体数组
2 
3 transient int size;//存放元素的个数
4 
5 int threshold; //临界值   当实际大小超过临界值时,会进行扩容threshold = 加载因子*容量
6 
7 final float loadFactor; //加载因子
8 
9 transient int modCount;//被修改的次数

    其中加载因子是表示Hash表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,
好处是:冲突的机会减小了,但:空间浪费多了.冲突的机会越大,则查找的成本越高.反之,查找的成本越小.因而,查找时间就越小.因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷.

  如果机器内存足够,并且想要提高查询速度的话可以将加载因子设置小一点;相反如果机器内存紧张,并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它,让它取默认值0.75就好了。

  下面看看HashMap的几个构造方法:

 1 public HashMap(int initialCapacity, float loadFactor) {
 2         //确保数字合法
 3         if (initialCapacity <0)
 4             throw new IllegalArgumentException("Illegal initial capacity: " +
 5                                                initialCapacity);
 6         if (initialCapacity > MAXIMUM_CAPACITY)
 7             initialCapacity = MAXIMUM_CAPACITY;
 8         if (loadFactor <= 0 || Float.isNaN(loadFactor))
 9             throw new IllegalArgumentException("Illegal load factor: " +
10                                                loadFactor);
11 
12         // Find a power of 2 >= initialCapacity
13         int capacity = 1;   //初始容量
14         while (capacity 

  我们可以看到在构造HashMap的时候如果我们指定了加载因子和初始容量的话就调用第一个构造方法,否则的话就是用默认的。默认初始容量为16,默认加载因子为0.75。我们可以看到上面代码中13-15行,这段代码的作用是确保容量为2的n次幂,使capacity为大于initialCapacity的最小的2的n次幂,至于为什么要把容量设置为2的n次幂,我们等下再看。

  下面看看HashMap存储数据的过程是怎样的,首先看看HashMap的put方法:

 1 public V put(K key, V value) {
 2         if (key == null) //如果键为null的话,调用putForNullKey(value)
 3             return putForNullKey(value);
 4         int hash = hash(key.hashCode());//根据键的hashCode计算hash码
 5         int i = indexFor(hash, table.length);
 6         for (Entry e = table[i]; e != null; e = e.next) { //处理冲突的,如果hash值相同,则在该位置用链表存储
 7             Object k;
 8             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果key相同则覆盖并返回旧值
 9                 V oldValue = e.value;
10                 e.value = value;
11                 e.recordAccess(this);
12                 return oldValue;
13             }
14         }
15 
16         modCount++;
17         addEntry(hash, key, value, i);
18         return null;
19     }

当我们往hashmap中put元素的时候,先根据key的hash值得到这个元素在数组中的位置(即下标),然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了,那么在同一个位子上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。从hashmap中get元素时,首先计算key的hashcode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。

具体的实现是:

当你的key为null时,会调用putForNullKey,HashMap允许key为null,这样的对像是放在table[0]中。

如果不为空,则调用int hash = hash(key.hashCode());这是hashmap的一个自定义的hash,在key.hashCode()基础上进行二次hash

1 static int hash(int h) {  
2         h ^= (h >>> 20) ^ (h >>> 12);  
3         return h ^ (h >>> 7) ^ (h >>> 4);  
4   }  

得到hash码之后就会通过hash码去计算出应该存储在数组中的索引,计算索引的函数如下:

1 static int indexFor(int h, int length) {  
2        return h & (length-1);  
3    }  

 这个方法非常巧妙,它通过 h & (table.length -1) 来得到该对象的保存位,而HashMap底层数组的长度总是 2 的n 次方,这是HashMap在速度上的优化。当length总是 2 的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。当数组长度为2的n次幂的时候,不同的key算得得index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。

下面我们继续回到put方法里面,前面已经计算出索引的值了,看到第6到14行,如果数组中该索引的位置的链表已经存在key相同的对象,则将其覆盖掉并返回原先的值。如果没有与key相同的键,则调用addEntry方法创建一个Entry对象,addEntry方法如下:

1 void addEntry(int hash, K key, V value, int bucketIndex) {
2         Entry e = table[bucketIndex]; //如果要加入的位置有值,将该位置原先的值设置为新entry的next,也就是新entry链表的下一个节点
3         table[bucketIndex] = new Entry<>(hash, key, value, e);
4         if (size++ >= threshold) //如果大于临界值就扩容
5             resize(2 * table.length); //以2的倍数扩容
6     }

参数bucketIndex就是indexFor函数计算出来的索引值,第2行代码是取得数组中索引为bucketIndex的Entry对象,第3行就是用hash、key、value构建一个新的Entry对象放到索引为bucketIndex的位置,并且将该位置原先的对象设置为新对象的next构成链表。

  第4行和第5行就是判断put后size是否达到了临界值threshold,如果达到了临界值就要进行扩容,HashMap扩容是扩为原来的两倍。resize()方法如下:

 1 void resize(int newCapacity) {
 2         Entry[] oldTable = table;
 3         int oldCapacity = oldTable.length;
 4         if (oldCapacity == MAXIMUM_CAPACITY) {
 5             threshold = Integer.MAX_VALUE;
 6             return;
 7         }
 8 
 9         Entry[] newTable = new Entry[newCapacity];
10         transfer(newTable);//用来将原先table的元素全部移到newTable里面
11         table = newTable;  //再将newTable赋值给table
12         threshold = (int)(newCapacity * loadFactor);//重新计算临界值
13     }

扩容是需要进行数组复制的,上面代码中第10行为复制数组,复制数组是非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。


推荐阅读
  • 如何利用Java 5 Executor框架高效构建和管理线程池
    Java 5 引入了 Executor 框架,为开发人员提供了一种高效管理和构建线程池的方法。该框架通过将任务提交与任务执行分离,简化了多线程编程的复杂性。利用 Executor 框架,开发人员可以更灵活地控制线程的创建、分配和管理,从而提高服务器端应用的性能和响应能力。此外,该框架还提供了多种线程池实现,如固定线程池、缓存线程池和单线程池,以适应不同的应用场景和需求。 ... [详细]
  • 本文深入解析了Java 8并发编程中的`AtomicInteger`类,详细探讨了其源码实现和应用场景。`AtomicInteger`通过硬件级别的原子操作,确保了整型变量在多线程环境下的安全性和高效性,避免了传统加锁方式带来的性能开销。文章不仅剖析了`AtomicInteger`的内部机制,还结合实际案例展示了其在并发编程中的优势和使用技巧。 ... [详细]
  • 投融资周报 | Circle 达成 4 亿美元融资协议,唯一艺术平台 A 轮融资超千万美元 ... [详细]
  • 开发日志:201521044091 《Java编程基础》第11周学习心得与总结
    开发日志:201521044091 《Java编程基础》第11周学习心得与总结 ... [详细]
  • Java学习第10天:深入理解Map接口及其应用 ... [详细]
  • 第六章:枚举类型与switch结构的应用分析
    第六章深入探讨了枚举类型与 `switch` 结构在编程中的应用。枚举类型(`enum`)是一种将一组相关常量组织在一起的数据类型,广泛存在于多种编程语言中。例如,在 Cocoa 框架中,处理文本对齐时常用 `NSTextAlignment` 枚举来表示不同的对齐方式。通过结合 `switch` 结构,可以更清晰、高效地实现基于枚举值的逻辑分支,提高代码的可读性和维护性。 ... [详细]
  • 手指触控|Android电容屏幕驱动调试指南
    手指触控|Android电容屏幕驱动调试指南 ... [详细]
  • 本文探讨了 Java 中 Pair 类的历史与现状。虽然 Java 标准库中没有内置的 Pair 类,但社区和第三方库提供了多种实现方式,如 Apache Commons 的 Pair 类和 JavaFX 的 javafx.util.Pair 类。这些实现为需要处理成对数据的开发者提供了便利。此外,文章还讨论了为何标准库未包含 Pair 类的原因,以及在现代 Java 开发中使用 Pair 类的最佳实践。 ... [详细]
  • 并发编程入门:初探多任务处理技术
    并发编程入门:探索多任务处理技术并发编程是指在单个处理器上高效地管理多个任务的执行过程。其核心在于通过合理分配和协调任务,提高系统的整体性能。主要应用场景包括:1) 将复杂任务分解为多个子任务,并分配给不同的线程,实现并行处理;2) 通过同步机制确保线程间协调一致,避免资源竞争和数据不一致问题。此外,理解并发编程还涉及锁机制、线程池和异步编程等关键技术。 ... [详细]
  • 第二章:Kafka基础入门与核心概念解析
    本章节主要介绍了Kafka的基本概念及其核心特性。Kafka是一种分布式消息发布和订阅系统,以其卓越的性能和高吞吐量而著称。最初,Kafka被设计用于LinkedIn的活动流和运营数据处理,旨在高效地管理和传输大规模的数据流。这些数据主要包括用户活动记录、系统日志和其他实时信息。通过深入解析Kafka的设计原理和应用场景,读者将能够更好地理解其在现代大数据架构中的重要地位。 ... [详细]
  • 在前文探讨了Spring如何为特定的bean选择合适的通知器后,本文将进一步深入分析Spring AOP框架中代理对象的生成机制。具体而言,我们将详细解析如何通过代理技术将通知器(Advisor)中包含的通知(Advice)应用到目标bean上,以实现切面编程的核心功能。 ... [详细]
  • 本文深入探讨了CGLIB BeanCopier在Bean对象复制中的应用及其优化技巧。相较于Spring的BeanUtils和Apache的BeanUtils,CGLIB BeanCopier在性能上具有显著优势。通过详细分析其内部机制和使用场景,本文提供了多种优化方法,帮助开发者在实际项目中更高效地利用这一工具。此外,文章还讨论了CGLIB BeanCopier在复杂对象结构和大规模数据处理中的表现,为读者提供了实用的参考和建议。 ... [详细]
  • 通过使用七牛云存储服务,本文详细介绍了如何将本地图片高效上传至云端,并实现了内容的便捷管理。借助七牛云的 Python SDK,文章提供了从认证到文件上传的具体代码示例,包括导入必要的库、生成上传凭证以及处理文件路径等关键步骤。此外,还探讨了如何利用七牛云的 URL 安全编码功能,确保数据传输的安全性和可靠性。 ... [详细]
  • 在Python多进程编程中,`multiprocessing`模块是不可或缺的工具。本文详细探讨了该模块在多进程管理中的核心原理,并通过实际代码示例进行了深入分析。文章不仅总结了常见的多进程编程技巧,还提供了解决常见问题的实用方法,帮助读者更好地理解和应用多进程编程技术。 ... [详细]
  • 在Python网络编程中,多线程技术的应用与优化是提升系统性能的关键。线程作为操作系统调度的基本单位,其主要功能是在进程内共享内存空间和资源,实现并行处理任务。当一个进程启动时,操作系统会为其分配内存空间,加载必要的资源和数据,并调度CPU进行执行。每个进程都拥有独立的地址空间,而线程则在此基础上进一步细化了任务的并行处理能力。通过合理设计和优化多线程程序,可以显著提高网络应用的响应速度和处理效率。 ... [详细]
author-avatar
wy6968308431
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有