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

HashMapJDK1.8原理分析

HashMap、Hashtable、LinkedHashMap和TreeMap下面针对各个实现类的特点做一些说明:(1)HashMap:它根据键的hashCode值存储数据,大多数

《HashMap JDK1.8原理分析》 HashMap、Hashtable、LinkedHashMap和TreeMap

下面针对各个实现类的特点做一些说明:

(1) HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。

(2) Hashtable:Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,并且是线程安全的,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。

(3) LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

(4) TreeMap:TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类,要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化,Map对象很可能就定位不到映射的位置了。

通过上面的比较,我们知道了HashMap是Java的Map家族中一个普通成员,鉴于它可以满足大多数场景的使用条件,所以是使用频度最高的一个。下文我们主要结合源码,从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。

《HashMap JDK1.8原理分析》 HashMap1.8原理:数组+链表+红黑树

JDK1.8中HashMap的数据结构(数组+链表+红黑树)

一、主要类属性:

默认的初始容量是16
默认的负载因子0.75
当桶上的结点数大于8会转成红黑树
当桶上的结点数小于6红黑树转链表
Node[] table //存储元素的哈希桶数组,总是2的幂次倍
int threshold // 所能容纳的key-value对极限,当put超过这个值的时候就会进行扩容
final float loadFactor // 负载因子

//类属性
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
// 序列号
private static final long serialVersiOnUID= 362498820763181265L;
// 默认的初始容量是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[] table;
// 存放具体元素的集
transient Set> entrySet;
// 存放元素的个数,注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容
int threshold;
// 填充因子
final float loadFactor;
}

二、在HashMap中,哈希桶数组table的长度length大小必须为2的n次方(一定是合数),HashMap采用这种非常规设计(常规的设计是把桶的大小设计为素数),主要是为了在取模和扩容时做优化。

1、tab[i = (n &#8211; 1) & hash]) 计算索引位置时位运算&速度高于取模运算%
如果length为2的次幂 则length-1 转化为二进制必定是11111……的形式,在与h的二进制与操作效率比较高。扩容的时候只需要看新增的一位的0还是1就可以了。
2、保证元素分布的均匀
而且空间不浪费;如果length不是2的次幂,比如length为15,则length-1为14,对应的二进制为1110,在于h与操作,最后一位都为0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率。

三、确定哈希桶数组索引位置

这里的Hash算法本质上就是三步:取key的hashCode值、高位运算、取模运算。

JDK 源码中 HashMap 的 hash 方法原理
右位移16位,正好是32bit的一半,自己的高半区和低半区做异或,就是为了混合原始哈希码的高位和低位,以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保留下来。
假如没有进行高位运算,那最后参与运算的永远只是取模运算的最后几位,相似性会比较大。

《HashMap JDK1.8原理分析》 扰动函数

static final int hash(Object key) { //jdk1.8
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
四、put

了解链表、红黑树转换,扩容的时机

《HashMap JDK1.8原理分析》 image.png

五、扩容

首次put元素需要进行扩容为默认容量16,阈值16*0.75=12,以后扩容后的table大小变为原来的两倍,接下来就是进行扩容后table的调整:
假设扩容前的table大小为2的N次方,有上述put方法解析可知,元素的table索引为其hash值的后N位确定
那么扩容后的table大小即为2的N+1次方,则其中元素的table索引为其hash值的后N+1位确定,比原来多了一位
因此,table中的元素只有两种情况:
元素hash值第N+1位为0:不需要进行位置调整
元素hash值第N+1位为1:调整至原索引的两倍位置
扩容或初始化完成后,resize方法返回新的table。

总结

(1) 扩容是一个特别耗性能的操作,所以当程序员在使用HashMap的时候,估算map的大小,初始化的时候给一个大致的数值,避免map进行频繁的扩容。
(2) 负载因子是可以修改的,也可以大于1,但是建议不要轻易修改,除非情况非常特殊。
(3) HashMap是线程不安全的,不要在并发的环境中同时操作HashMap,建议使用ConcurrentHashMap。
(4) JDK1.8引入红黑树大程度优化了HashMap的性能,查找的时间复杂度从链表的O(n)优化到O(logn)


推荐阅读
  • 本文介绍了 Oracle SQL 中的集合运算、子查询、数据处理、表的创建与管理等内容。包括查询部门号为10和20的员工信息、使用集合运算、子查询的注意事项、数据插入与删除、表的创建与修改等。 ... [详细]
  • HashTable与ConcurrentHashMap均可实现HashMap的功能,对外提供了键值对存储的数据结构。但是在内部结构及实现上有何区别,性能上的差异到底在哪里又是如何导致的 ... [详细]
  • 视觉Transformer综述
    本文综述了视觉Transformer在计算机视觉领域的应用,从原始Transformer出发,详细介绍了其在图像分类、目标检测和图像分割等任务中的最新进展。文章不仅涵盖了基础的Transformer架构,还深入探讨了各类增强版Transformer模型的设计思路和技术细节。 ... [详细]
  • 图解HashMap
    什么是HashMap,文章内HashMap源码主要来自Android7.0HashMap是开发中常用的一个类,那么他究竟是什么呢?HashMap是一个存储key-value的集合, ... [详细]
  • 本文探讨了如何使用Scrapy框架构建高效的数据采集系统,以及如何通过异步处理技术提升数据存储的效率。同时,文章还介绍了针对不同网站采用的不同采集策略。 ... [详细]
  • Gradle 是 Android Studio 中默认的构建工具,了解其基本配置对于开发效率的提升至关重要。本文将详细介绍如何在 Gradle 中定义和使用共享变量,以确保项目的一致性和可维护性。 ... [详细]
  • 汇总了2023年7月7日最新的网络安全新闻和技术更新,包括最新的漏洞披露、工具发布及安全事件。 ... [详细]
  • 【MySQL】frm文件解析
    官网说明:http:dev.mysql.comdocinternalsenfrm-file-format.htmlfrm是MySQL表结构定义文件,通常frm文件是不会损坏的,但是如果 ... [详细]
  • spring boot使用jetty无法启动 ... [详细]
  • Web动态服务器Python基本实现
    Web动态服务器Python基本实现 ... [详细]
  • 流处理中的计数挑战与解决方案
    本文探讨了在流处理中进行计数的各种技术和挑战,并基于作者在2016年圣何塞举行的Hadoop World大会上的演讲进行了深入分析。文章不仅介绍了传统批处理和Lambda架构的局限性,还详细探讨了流处理架构的优势及其在现代大数据应用中的重要作用。 ... [详细]
  • Java集合详解5:深入理解LinkedHashMap和LRU缓存
    Java集合详解5:深入理解LinkedHashMap和LRU缓存今天我们来深入探索一下LinkedHashMap的底层原理,并且使用linkedhashmap来实现LRU缓存。具体代码在我的 ... [详细]
  • 转载自:http:www.blogjava.netCarpenterLeearchive20160427430268.html总体介绍之所以把HashSet和HashMa ... [详细]
  • 一、使用Microsoft.Office.Interop.Excel.DLL需要安装Office代码如下:2publicstaticboolExportExcel(S ... [详细]
  • SQL Server 存储过程实践任务(第二部分)
    本文档详细介绍了三个SQL Server存储过程的创建与使用方法,包括统计特定类型客房的入住人数、根据房间号查询客房详情以及删除特定类型的客房记录。 ... [详细]
author-avatar
兔子东大门一手批发
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有