HashMap 和 ConcurrentHashMap,Java1.8版本
1. HashMap
Entry,一对kv就是一个Entry,还包括一些next指针,用来解决散列冲突。
table,内部用来存储Entry的数组,resize时候table会成倍扩容。
容量,table数组的长度。
装填因子,当key的数量大于table.length*装填因子就要进行扩容,默认75%。
resize操作,同步的重新计算一遍hash值对应的新的slot
Put操作
和所有hashmap一样,都是计算hash值,检查容量,映射到slot。当发生冲突的时候会往entry链表的后面插入。
不过,java还做了一个优化,这个链表长度当大于8个的时候会把他优化成一个有序的Tree。
Get操作
根据hash值找到slot,然后比较第一个Entry是不是要找的kv,不是的话,就沿着next指针的Entry往下找。
如果,发现是个Tree不是链表,直接做有序的查找
2. ConcurrentHashMap
以下和HashMap相同的地方就不说了
问题,ConcurrentHashMap多线程情况下怎么初始化table,以及table在多线程情况下resize
解决,
有一个sizeCtl的属性,这个属性只可能是0或者-1,通过CAS,只有一个线程把他设置成-1。
其他没设置成功的线程调用Thread.yield,原话是“lost initialization race; just spin”
问题,Put的时候slot之前没有值,怎么防止多个线程同时设置新值
解决,
尝试用CAS更新一次这个空的位置,更新失败的时候,对slot上的第一个Node加锁,用插入到链表或者TreeNode
问题,Put以后要size++
解决,
这里没有使用AtomicInteger,而是把每个slot对应一个CounterCell代表这个slot下Entry的数量,这里没读懂为什么使用CounterCell
问题,resize相关的策略
解决,
之前用装填因子和数量来判断是否需要resize,java8是通过是否有散列冲突来扩容。
与redis的策略一样,java8也是采用渐进性哈希的方式。
最新文章
- 更简洁的 CSS 清理浮动方式
- iOS高级必备
- mysql运行参数详解
- linux工具之putty
- WCF 服务的ABC之地址(五)
- 走进React的学习之路
- Entity Framework 利用 Database.SqlQuery<;T>; 执行存储过程,并返回Output参数值
- BNUOJ 34981 A Matrix
- Node.js学习笔记(一):快速开始
- 常见的jquery一些效果
- centos如何安装python库?
- 一个成功的 Git 分支模型(适用于商业应用开发)
- randperm
- Golang 笔记 3 if、switch、for、select语句
- Springmvc的原理和业务处理
- swift - 使用系统app导航
- warning: LF will be replaced by CRLF in dubbo-demo-api/pom.xml.
- js 转义
- mvc 读写txt文档
- CF1143D/1142A The Beatles
热门文章
- 快速掌握用python写并行程序
- JavaScript中类型检测
- Codeforces 671 A——Recycling Bottles——————【思维题】
- [转]error MSB4018: The ";GenerateResource"; task failed unexpectedly
- Swift可选链
- Expression Blend实例中文教程(9) - 行为快速入门Behaviors
- 如何移除git不需要提交的文件
- 重构指南 - 为布尔方法命名(Rename boolean method)
- python logging的应用
- JavaScript AMD 与CMD的代码区别