江苏龙网

  1. 首页 > 资讯 > 科技 > >

大数据&云计算|炸裂，大神图解JDK容器三大将之——哈希表


作者：JackpotDC
链接：https://juejin.im/post/6861544032859127822
JDK容器三大将
任何一项新的技术、一种新的语言本质上都是算法+数据结构 。 任何技术的选型本质上都是在基于业务和硬件条件的充分理解 ， 采用合适的数据结构、适当的算法以达到资源和效率的最优解 。 Java开发亦是如此 ， 工欲善其事 ， 必先利其器 ， 想要使用Java这种语言开发好程序 ， 就必须选择合适的数据结构来进行开发 。 JDK容器则是所有Java应用开发的基础 ， 不论是业务代码 ， 还是各种知名的Java开源项目（如异步网络框架netty、容器管理框架Spring、分布式计算框架Hadoop、搜索引擎框架Elastic Search） ， 全都是大量在JDK容器的基础上进行开发 。 而JDK容器作为这些优秀开源项目的默认选择 ， 必然有其优势 ， 本文将分析下JDK容器三大将之哈希表 。
大数据&云计算|炸裂，大神图解JDK容器三大将之——哈希表
本文插图

JDK容器三大将：List、Set、Map
HashMap介绍

所有编程语言都躲不开数据结构原理中的几种经典结构 ， 链表、线性表、哈希表等 。 哈希表以其O(1) 的查找耗时在查找速度方面傲视群雄 ， Java中哈希表的实现即HashMap类 。（原JDK中还有一个Hashtable类 ， 由于put和get操作都加了synchronized锁导致单线程性能差 ， 多线程又有基于分段锁的ConcurrentHashMap作为更好的选择 ， 官方已经声明不再维护）
先来看下HashMap的继承关系图如下
【大数据&云计算|炸裂，大神图解JDK容器三大将之——哈希表】大数据&云计算|炸裂，大神图解JDK容器三大将之——哈希表
本文插图

Map接口为实现类暴露了一系列方法 ， AbstractMap抽象类为Map的一些基础功能提供了简单实现
Cloneable表示该类支持通过java.lang.Object#clone()方法克隆 ， clone方法相关的细节（浅拷贝、深拷贝）读者可以搜索相关关键字阅读
Serializable接口表示该类支持Java自带序列化功能进行序列化
HashMap的数据结构
HashMap的数据结构如下图
大数据&云计算|炸裂，大神图解JDK容器三大将之——哈希表
本文插图

下面分别来介绍下图中的几个概念：
size ， 存着HashMap当前的大小 ， 执行hashMap.size()时直接在O(1)的时间返回哈希表的大小 ， 如图有着三个键值对 ， 所以size=3
modCount ， 记录哈希表结构变更的次数 ， 用于在HashMap结构变更时能够快速失败 ， 后面会详细介绍

table ， 是一个Node数组（默认大小16） ， Node是HashMap的内部定义类 ， 结构如图 ， 保存着一对键值对 。 当执行map.put(k, v)命令时会根据k的哈希值映射到Node数组的某个位置 ， 并且通过拉链法处理哈希冲突
loadFactor、threshold ， 分别为装载因子（默认0.75）和阈值（Node.length * 装载因子） ， 当HashMap的容量（即size）超过阈值时会触发rehash ， 对Node数组进行扩容
HashMap的put/get操作执行过程 put()
HashMap的put操作的执行过程伪代码如下
void put(key, value) { index = hash(key) if(table[index] == null) table[index] = newNode(key, value) // 节点没有hash冲突时将该kv录入节点 else insertIntoLastNode(table[index], key, value) // 节点hash冲突时写入拉链的最后}复制代码
当hash冲突写入拉链时 ， HashMap有着一个常量TREEIFY_THRESHOLD=8 ， 当拉链长度超过阈值后链表会升级为红黑树
上文提到过的参数threshold = Node.length * 装载因子 ， 当put完的哈希表节点总数达到Node数组容量的0.75时会触发扩容


推荐阅读


上一篇：雷达|Python可视化：matplotlib 制作雷达图进行对比分析

下一篇：|手机品牌各系列怎么选，来这看看就明白了！