高清思维导图已同步Git:https://github.com/SoWhat1412/xmindfile,关注公众号sowhat1412获取海量资源
随机搜罗了一些常见HashMap
问题,如果把下述代码都看懂了应付这些应该没问题。
位运算操作是由处理器支持的底层操作,底层硬件只支持01这样的数字,因此位运算运行速度很快。尽管现代计算机处理器拥有了更长的指令流水线和更优的架构设计,使得加法和乘法运算几乎与位运算一样快,但是位运算消耗更少的资源。常用的位运算如下:
(1&1=1 1&0=0 0&0=0)
(1|1=1 1|0=1 0|0=0)
( ~1=0 ~0=1)
(1^1=0 1^0=1 0^0=0)
在执行右移操作时,若参与运算的数字为正数,则在高位补0;若为负数,则在高位补1。
无论参与运算的数字为正数或为负数,在执运算时,都会在高位补0。
对于左移是没有正数跟负数这一说的,因为负数在CPU中是以补码的形式存储的,对于正数左移相当于乘以2的N次幂。
敲重点:上面的重重都是简单的只是为了引出下面的结论:
a % (Math.pow(2,n))
等价于a&( Math.pow(2,n)-1)
比如a%16
最终的结果一定是0~15
之间的数字,而a&1111
正好把a除16后的余数有效的现实出来了因为如果是1 1111这样的话最前面一位其实代表的16,也就是说二进制从倒数第五位开始只要出现了1那绝对代表的是16的倍数。结论:位运算比除法运算在运行效率上更高,对一个数取余尽量用a&二进制数
这样可以更好的提速。
我们知道ArrayList
是一个数组队列,相当于动态数组。与Java中的基本数组相比,它的容量能动态增长。它具有以下几个重点。
默认构造函数
,则ArrayList的默认容量大小JDK7=10
,JDK8=0
。1.5
倍。Vector
实现线程安全级别的动态数组 初始值为10
,扩容为2
倍,底层用synchronized
实现的!优点:
缺点:
双向链表每一个节点包含三部分(data,prev,next),它不要求空间是连续的。类似于节点跟节点之间通过前后两条线串联起来的。
ArrayList和LinkedList总结:
首先你需要对二叉树有个了解,知道这是什么样子的一个数据组合方式,然后知道二叉树查找的时候缺点,可能发生数据倾斜。因此引入了平衡二叉树,平衡二叉树的左右节点深度之差不会超过1,查找方便构建麻烦,因此又出现了红黑树。红黑树是一种平衡的二叉查找树,是一种计算机科学中常用的数据结构,最典型的应用是实现数据的关联,例如map等数据结构的实现,红黑树重要特性是( 左节点 < 根节点 < 右节点) 红黑树有以下限制:
如果您对红黑树还不太了解推荐看下博主以前写的RBT
Hash表是一种特殊的数据结构,它同数组、链表以及二叉排序树等相比较有很明显的区别,它能够快速定位到想要查找的记录,而不是与表中存在的记录的关键字进行比较来进行查找。这个源于Hash表设计的特殊性,它采用了==函数映射==的思想将记录的存储位置与记录的关键字关联起来,从而能够很快速地进行查找。评价函数的性能关键在于==装填因子==,以及如何合理的解决哈希冲突,具体的可看博主以前写的彻底搞定哈希表
通常具备前面一些知识点的铺垫就可以很好的开展HashMap的讲解了,既然ArrayList
,LinkedList
,Red Black Tree
各有优缺点,我们能不能集百家之长实现一个综合产物呢 === >HashMap
,本文所以讲解都是基于JDK8。
HashMap
的组成部分:数组 + 链表 + 红黑树。HashMap
的主干是一个Node
数组。Node
是HashMap
的基本组成单元,每一个Node
包含一个key-value
键值对。HashMap
的时间复杂读几乎可以接近O(1)
(如果出现了 哈希冲突可能会波动下),并且HashMap
的空间利用率一般就是在40%左右。HashMap
的大致图如下:
PS:其中几个重要节点关系如下:
interface
定义了一些比较的接口函数。HashMap
中存储的基本的KV。Enrty
这个类继承自HashMap.Node
这个类,Enrty
是LIinkedHashMap
的一个内部类,TreeNode
的构造函数向上追溯继承了LinkedHashMap.Entry
,而后者又继承了HashMap.Node
。所以TreeNode
既保有Node
的属性,同时由于添加了prev
这个前驱指针使得==链表==变为了==双向==。前三个节点跟第五个红黑树相关,第四个跟next
跟双向链表相关。数据存储的大致步骤有三步。
HashTable
里的映射函数来决定将该数据放到数组的那个地方,数组初始化时候一定是2的次幂,默认16,初始化传入的任何数字都会经过tableSizeFor
调整为2次幂。TREEIFY_THRESHOLD=8
且数组长度 >= MIN_TREEIFY_CAPACITY=64
,则会将该链表进化位RedBlackTree
,如果RedBlackTree
中节点个数小于UNTREEIFY_THRESHOLD=6
会退化为链表。特别提醒:读HashMap源码之前需要知道它大致特性如下:
共存
的,切记。key
,会强制性的判别出个高低,判别高低主要是为了决定向左还是向右。root
节点和链表的头节点 跟table[i]
节点融合成一个。RBT
类似,找个合适的节点来填充已删除的节点。root
节点不一定
跟table[i]
也就是链表的头节点是同一个哦,三者同步是靠MoveRootToFront
实现的。而HashIterator.remove()
会在调用removeNode
的时候movable=false
。初始容量,默认容量=16,箱子的个数不能太多或太少。如果太少,很容易触发扩容,如果太多,遍历哈希表会比较慢。
数组的最大容量,一般情况下只要内存够用,哈希表不会出现问题
默认的负载因子。因此初始情况下,当存储的所有节点数 > (16 * 0.75 = 12 )时,就会触发扩容。默认负载因子(0.75)在时间和空间成本上提供了很好的折衷。较高的值会降低空间开销,但提高查找成本(体现在大多数的HashMap类的操作,包括get和put)。设置初始大小时,应该考虑预计的entry数在map及其负载系数,并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子,rehash操作将不会发生。
从上面的表中可以看到当桶中元素到达8个的时候,概率已经变得非常小,也就是说用0.75作为加载因子,每个碰撞位置的链表长度超过8个是几乎不可能的。4. static final int TREEIFY_THRESHOLD = 8
这个值表示当某个箱子(数组的某个item)中,链表长度 >= 8 时,有可能会转化成树。设置为8,是系统根据泊松分布的数据分布图来设定的。
在哈希表扩容时,如果发现链表长度 <= 6,则会由树重新退化为链表。设置为6猜测是因为时间和空间的权衡 当链表长度为6时 查询的平均长度为 n/2=3,红黑树 log(6) = 2.6 为8时 :链表 8/2=4, 红黑树 log(8)=3
链表转变成树之前,还会有一次判断,只有数组长度大于 64 才会发生转换。这是为了避免在哈希表建立初期,多个键值对恰好被放入了同一个链表中而导致不必要的转化。
HashMap的链表数组。无论我们初始化时候是否传参,它在自扩容时总是2的次幂。
HashMap实例中的Entry的Set集合
HashMap表中存储的实例KV个数。
凡是我们做的增删改都会引发
modCount
值的变化,跟版本控制功能类似,可以理解成version
,在特定的操作下需要对version
进行检查,适用于Fai-Fast
机制。 在java的集合类中存在一种Fail-Fast
的错误检测机制,当多个线程对同一集合的内容进行操作时,可能就会产生此类异常。比如当A通过iterator去遍历某集合的过程中,其他线程修改了此集合,此时会抛出ConcurrentModificationException
异常。此类机制就是通过modCount
实现的,在迭代器初始化时,会赋值expectedModCount
,在迭代过程中判断modCount
和expectedModCount
是否一致。
扩容阈值 threshold = capacity * loadFactor
可自定义的负载因子,不过一般都是用系统自带的0.75。
==tableSizeFor==:作用是返回大于输入参数且最小的2的整数次幂的数。比如10,则返回16。
详解如下:
先来分析有关n位操作部分:先来假设n的二进制为01xxx...xxx。接着 对n右移1位:001xx...xxx,再位或:011xx...xxx 对n右移2为:00011...xxx,再位或:01111...xxx 此时前面已经有四个1了,再右移4位且位或可得8个1 同理,有8个1,右移8位肯定会让后八位也为1。
综上可得,该算法让最高位的1后面的位全变为1。最后再让结果n+1,即得到了2的整数次幂的值了。现在回来看看第一条语句:
int n = cap - 1;
让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000,十进制数值为8。如果不对它减1而直接操作,将得到答案10000,即16。显然不是结果。减1后二进制为111,再进行操作则会得到原来的数值1000,这种二进制方法的效率非常高。
map
的大小来反推需要的threshold
,同时还可能会涉到resize
,然后住个put
到 容器中。无论我们put
数据还是get
数据都要先获得该数据在这个哈希表中对应的位置。比如put
数据,它的流程分为2步。
1.先获得key对应的hash值。2. 将该数据的hash值A,跟将A右无符号移动16位后再
^
得到最终值。这个操作叫扰动
,原因是怕低几位出现想同的概率太大,尽可能的将数据实现均匀分布。
同时JDK8跟JDK7的扰动目的一样,不过复杂程度不一样。
相对来说很简单,为方便理解先说下代码大致流程思路。
get
。宏观查找函数细节:
红黑树查找节点细节:
查询该key是否实现了Comparable
接口。
既然实现了Comparable接口就用该实现进行对比判断如何何去何从。
跟随源码梳理下put操作的大致流程。
数据插入的时候大致流程如下:
Hash
值计算。table
的状态,如果table
是空需要调用resize
来进行初始化。key
的目标位置。并判断当前位置情况。putTreeVal
。在JDK8中寻找待插入点
e
是通过==尾插法==(类似与排队在最后面),而在JDK7中是==前插法==(类似与加塞在最前面,之所以这样做是HashMap发明者认为后插入节被访问概率更大),对应代码如下。
7. 对找到的旧节点e
进行判断
Setnx
同样的功能。modCount
加1,同时看最新的总的节点数是否需要扩容了,如果是就扩容。主要功能是根据参数的阈值范围绝对是否将链表转化为红黑树,然后首先将单项链表转化为双向链表,再调用treeify
以头节点为根节点构建红黑树。
双向链表跟红黑树创建,主要步骤分3步。
table[i]
对应好。确保将root
节点挪动到table[first]
上,如果红黑树构建成功而没成功执行这个任务会导致tablle[first]
对应的节点不是红黑树的root
节点。正常执行的时候主要步骤分2步。
root
节点放到跟节点,至此关于红黑树到操作搞定。first
节点,现在将可能是中间节点的root
节点挪到first
节点前面。其中 checkInvariants
函数的作用:校验TreeNode
对象是否满足红黑树和双链表的特性。因为并发情况下会发生很多异常。
链表形式的重新划分解释如下:注意:不是(e.hash & (oldCap-1))
而是(e.hash & oldCap)
, 后一个得到的是 元素的在数组中的位置是否需要移动,示例如下
示例1:e.hash= 10 0000 1010 oldCap=16 0001 0000 & =0 0000 0000 比较高位的第一位 0结论:元素位置在扩容后数组中的位置没有发生改变 示例2:e.hash= 17 0001 0001 oldCap=16 0001 0000 & =1 0001 0000 比较高位的第一位 1结论:元素位置在扩容后数组中的位置发生了改变,新的下标位置是原下标位置+原数组长度
在这里插入图片描述
扩容后如何处理原来一个table[i]
上的红黑树,代码的整体思路跟处理链表的时候差不多,只要理解节点关系保存红黑树的时候也保存了双向链表就OK了。
函数功能就是以指定的一个节点为根节点,根据指定的key
跟value
进行查找。
key
不一样,继续查找分为三种情况。Comparable
对数据看向左还是向右。对两个对象进行比较,一定能比出个高低。
函数入口而已:
removeNode
无非就是查看table[i]是否存在,然后是否在首节点上,是否在红黑树上,是否在链表上。这几种情况,找到了则直接删除,同时注意平衡性。
该函数的 目的就是移除调用此方法的节点,也就是该方法中的this节点。移除包括链表的处理和红黑树的处理。可以看以前写过的RBT,删除的时候思路大致是一样的,这里大致分为3步骤。
p
节点尝试从pr
找最小的或者从pl
找最大的目标节点s
,将两点兑换。replacement
来跟p
进行替换。balance
。红黑树退化成链表
关于这个问题可以直接看博主以前写的红黑叔添加跟删除RBT
JDK7对旧table
数据重定位到新table
的函数transfer
如下,其中重点关注部分以标出。
Entry<K,V> next = e.next
就被挂起了,而线程2正常执行完毕,结果图如下:线程1接着下面继续执行:
通过逐步分析跟绘图可以知道 会有环产生。
Hash
用了4次,8中只用了1次。HashMap
不管78都是现场不安全的,多线程情况下记得用ConcurrentHashmap
。ConcurrentHashmap
下篇文章说。