文档章节

java7,java8 中HashMap和ConcurrentHashMap简介

o
 osc_odyg6b92
发布于 2018/07/13 15:15
字数 1734
阅读 7
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

##一:Java7 中的HashMap ###结构: HashMap 里面是一个数组,然后数组中每个元素是一个单向链表。链表中每个元素称为一个Entry 实例,Entry 包含四个属性:key, value, hash 值和用于单向链表的 next。

###属性: capacity:当前数组容量,始终保持 2^n,可以扩容,扩容后数组大小为当前的 2 倍。

loadFactor:负载因子,默认为 0.75。

threshold:扩容的阈值,等于 capacity * loadFactor

(一)put操作大概过程 在第一个元素插入 HashMap 的时候做一次数组的初始化,就是先确定初始的数组大小,并计算数组扩容的阈值。通过hash(key)找到数组下标后,会先进行 key 判重,如果没有重复,就准备将新值放入到链表的表头。主要逻辑就是先判断是否需要扩容,需要的话先扩容,然后再将这个新的数据插入到扩容后的数组的相应位置处的链表的表头。数组扩容 在插入新值的时候,如果当前的 size 已经达到了阈值(capacity * loadFactor),并且要插入的数组位置上已经有元素,那么就会触发扩容,扩容后,数组大小为原来的 2 倍。

(二)get 操作大概过程

①根据 key 计算 hash 值。 ②找到相应的数组下标:hash & (length – 1)。 ③遍历该数组位置处的链表,直到找到相等(==或equals)的 key。

##二:Java7 中的ConcurrentHashMap ConcurrentHashMap采用了分段锁的设计,只有在同一个分段内才存在竞态关系,不同的分段锁之间没有锁竞争。相比于对整个Map加锁的设计,分段锁大大的提高了高并发环境下的处理能力。 ###结构: 整个 ConcurrentHashMap 由一个个 Segment 组成,Segment 代表”部分“或”一段“的意思,所以很多地方都会将其描述为分段锁。每一个Segment中又存储一个类似HashMap的数组链表结构,可以简称为外层数组里面又一个内层数组,内层数组中是一个链表,这样的三维结构。

###属性: concurrencyLevel:Segment 数,默认是 16,也就是说 ConcurrentHashMap 有 16 个 Segments,最多可以同时支持 16 个线程并发写,只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值,但是一旦初始化以后,它是不可以扩容的。

initialCapacity:初始容量,这个值指的是整个 ConcurrentHashMap 的初始容量,实际操作的时候需要平均分给每个 Segment。

loadFactor:负载因子,之前我们说了,Segment 数组不可以扩容,所以这个负载因子是给每个 Segment 内部使用的。

(一)put操作大概过程 ①计算key的hash值确定在某个Segment写 ②获得锁,也就是分段锁,操作确定的segment的时,不允许其他线程操作 ③和HashMap的操作一样

对于扩容的操作,segment的容量一旦确定后是不能修改的,只能扩容segment [ i ] ,也是和HashMap一样的操作。

(二)get操作大概过程

①计算 hash 值,找到 segment 数组中的具体位置 ②segment 中也是一个数组,根据 hash 找到数组中具体的位置 ③到这里是链表了,顺着链表进行查找即可

##三:Java8 中的HashMap

Java8 对 HashMap 进行了一些修改,最大的不同就是利用了红黑树,所以其由 数组+链表+红黑树 组成。根据 Java7 HashMap 的介绍,我们知道,查找的时候,根据 hash 值我们能够快速定位到数组的具体下标,但是之后的话,需要顺着链表一个个比较下去才能找到我们需要的,时间复杂度取决于链表的长度,为 O(n)。为了降低这部分的开销,在 Java8 中,当链表中的元素超过了 8 个以后,会将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

Java7 中使用 Entry 来代表每个 HashMap 中的数据节点,Java8 中使用 Node,基本没有区别,都是 key,value,hash 和 next 这四个属性,不过,Node 只能用于链表的情况,红黑树的情况需要使用 TreeNode。

###结构: Java8 中的HashMap里面是一个数组,然后数组中每个元素是一个单向链表,或者是一颗红黑树。当链表长度大于8时转化为红黑树

(一)put操作大概过程 ①第一次插入初始化(默认16),不是第一次则计算hash(key)计算下标(判断是否需要扩容) ②判断下标的第一个节点是否是红黑树节点TreeNode ,如果是按照红黑树的插入规则插入。 ③如果不是红黑树节点,而是链表节点Node,再判断加入节点后是否大于8。如果是转化为红黑树结构,如果不是,则比较并插入。

扩容也是超过阀定值,则扩容为原来的两倍。 (二)get操作大概过程 ①计算 key 的 hash 值,根据 hash 值找到对应数组下标 ②判断数组该位置处的元素是否刚好就是我们要找的,如果不是,走第三步 ③判断该元素类型是否是 TreeNode,如果是,用红黑树的方法取数据,如果不是,走第四步 ⑥遍历链表,直到找到相等(==或equals)的 key

##四:Java8 中的ConcurrentHashMap

###结构: 和 Java8 的 HashMap 基本上一样,里面是一个数组,然后数组中每个元素是一个单向链表,或者是一颗红黑树。当链表长度大于8时转化为红黑树

(一)put操作大概过程 ①如果没有初始化就先调用initTable()方法来进行初始化过程 ②如果没有hash冲突就直接CAS插入 ③如果还在进行扩容操作就先进行扩容 ④如果存在hash冲突,就加锁来保证线程安全,这里有两种情况,一种是链表形式就直接遍历到尾端插入,一种是红黑树就按照红黑树结构插入, ⑤最后一个如果该链表的数量大于阈值8,就要先转换成黑红树的结构,break再一次进入循环 ⑥如果添加成功就调用addCount()方法统计size,并且检查是否需要扩容

(二)get操作大概过程 ①计算hash值,定位到该table索引位置,如果是首节点符合就返回 ②如果遇到扩容的时候,会调用标志正在扩容节点ForwardingNode的find方法,查找该节点,匹配就返回 ③以上都不符合的话,就往下遍历节点,匹配就返回,否则最后就返回null

o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
开源数据访问组件--Smark.Data

Smark.Data是基于Ado.net实现的数据访问组件,提供基于强类型的查询表达式进行灵活的数据查询,统计,修改和删除等操作;采用基于条件驱动的操作模式,使数据操作更简单轻松;内部通过标准SQL...

泥水佬
2013/03/12
2.5K
0
浏览器中的scheme解释器--SchemeScript

一个用javascript实现的scheme解释器,可以运行在浏览器中或node.js中。 刚刚看到编译原理与实践第二章,一时兴起,想写个以前就想写的scheme的解释器。昨天晚上开始写,到刚才为止,接近一天...

zoowii
2012/11/01
1.1K
0
ThinkPHP助手

ThinkPHP助手 简介 ThinkPHP助手是运行在本地的ThinkPHP开发辅助性工具,也是本人的初学LAMP的学习成果,基于ThinkPHP+XML,前端采用jQuery和Bootstrap。主要目的是将应用开发过程中的一些繁琐...

朱__朱
2012/11/16
9.2K
2
高性能NoSQL数据库--SSDB

SSDB 是一个 C/C++ 语言开发的高性能 NoSQL 数据库, 支持 zset(sorted set), map(hash), kv, list 等数据结构, 用来替代或者与 Redis 配合存储十亿级别列表的数据. SSDB 在 QIHU 360 被大量使...

ideawu
2013/01/08
2.6W
4
Android 快速开发框架--ThinkAndroid

ThinkAndroid简介 ThinkAndroid是一个免费的开源的、简易的、遵循Apache2开源协议发布的Android开发框架,其开发宗旨是简单、快速的进行Android应用程序的开发,包含Androidmvc、简易sqlite ...

white-cat
2013/05/05
6.8W
6

没有更多内容

加载失败,请刷新页面

加载更多

如何在SQL Server中将多行文本合并为单个文本字符串?

问题: Consider a database table holding names, with three rows: 考虑一个包含名称的数据库表,该表具有三行: PeterPaulMary Is there an easy way to turn this into a single str......

富含淀粉
22分钟前
9
0
在JavaScript中生成特定范围内的随机整数? - Generating random whole numbers in JavaScript in a specific range?

问题: 如何可以生成两个指定的变量之间的随机整数在JavaScript中,例如x = 4和y = 8将输出任何的4, 5, 6, 7, 8 ? 解决方案: 参考一: https://stackoom.com/question/6PRz/在JavaScript中...

fyin1314
52分钟前
8
0
Vim清除最后一个搜索突出显示 - Vim clear last search highlighting

问题: Want to improve this post? 想要改善这篇文章吗? Provide detailed answers to this question, including citations and an explanation of why your answer is correct. 提供此问题......

技术盛宴
今天
23
0
马化腾每天刷 Leetcode?代码你打算写到几岁?

本文作者:o****0 前几天,一张未证真伪的截图流传,图中显示马化腾几乎每天都会在 Leetcode 上提交代码。 截图还贴出一个 Leetcode 账户地址。该地址的头像已从马化腾的照片换成腾讯 logo,...

百度开发者中心
前天
13
0
滴滴 3000+ Kylin Cube 背后的实践经验揭秘

本次分享主要有三个部分:Kylin 在滴滴的整体应用、架构的实践经验、滴滴全局字典最新版本的实现以及 Kylin 最新实时 OLAP 探索经验分享。 Kylin 在滴滴的应用&架构 Kylin 在滴滴的三类应用场...

浪尖聊大数据
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部