java集合源码分析
2021-07-11 09:08:44 0 举报AI智能生成
登录查看完整内容
java集合源码分析
作者其他创作
大纲/内容
集合源码分析
arrayList
介绍
ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能
ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的
ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
类成员变量介绍
DEFAULT_CAPACITY=10
当用户指定ArrayList的容量为0时，默认容量为10
elementData
Object[]类型数组
size
动态数组的实际大小
ArrayList方法
查找
indexOf（正序查找，for循环从前往后遍历）
lastIndexOf（正序查找，for循环从后往前遍历）
删除
E remove(int index)
boolean remove(Object o)
void fastRemove(int index)
增加
关于ArrayList的一些问题
简单介绍下ArrayList
ArrayList是以数组实现，可以自动扩容的动态数组，当超出限制的时候会增加50%的容量，用ystem.arraycopy()复制到新的数组，因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。arrayList的性能很高效，不论是查询和取值很迅速，但是插入和删除性能较差，该集合线程不安全。
ArrayList的自动扩容怎么样实现的
每次在add()一个元素时，arraylist都需要对这个list的容量进行一个判断。如果容量够，直接添加，否则需要进行扩容。在1.8 arraylist这个类中，扩容调用的是grow()方法
在核心grow方法里面，首先获取数组原来的长度，然后新增加容量为之前的1.5倍。随后，如果新容量还是不满足需求量，直接把新容量改为需求量，然后再进行最大化判断
通过grow()方法中调用的Arrays.copyof()方法进行对原数组的复制，在通过调用System.arraycopy()方法进行复制，达到扩容的目的
ArrayList的构造方法过程
无参的构造方法 先将数组为空，第一次加入的时候 然后扩充默认为10
有参的构造方法 ，直接创建这个数组
传入集合元素，先将集合元素转换为数组，把不是object的数组转化为object数组
ArrayList可以无限扩大吗
程序
数据结构
数组
底层结构：采用一段连续的存储单元来存储数据
特点：查询快O(1)，插入慢O(N)
链表
底层结构：是一种物理存储单元上非连续、非顺序的存储结构
算法
哈希算法（散列）
简介
将任意长度（key）通过散列算法变换成固定长度的key（地址），通过这个地址进行访问的数据结构
原理
对字符串算出ascii码，先进行相加，再进行mod（取模），算出哈希表的下标
取模的原因：节省数组的空间
问题
哈希冲突（哈希碰撞）
两个字符串的ascii码相同
解决方案
开放地址法
发生冲突，继续寻找下一块未被占用的存储地址
再散列函数法
链地址法
数组+链表
hashMap
jdk1.7
底层结构
1、链表存储的结构，查询效率慢
jdk1.8
参数
链表转红黑树的要求
1、数组长度>=64
2、链表长度>=8
问题：为什么不直接设置为红黑树？
默认大小
8
阈值
0.75
扩容
长度左移动1位，使用位运算
hashCode()
对字符串进行ascii码取值
通话和重地的hashCode()一样
hash
h=key.hashCode())^(h>>>16)
让h的高16位与低16位进行异或运算，减少hash冲突的概率
位运算
在Java中，整数的二进制是以补码的形式存在的
十进制转为二进制
正数
原码=反码=补码
负数
原码
十进制转二进制不足32位的，最高位补符号位，其余补零
反码
补码
get
为什么要保证capacity是2的次幂呢？
1、需要在node数组中查询下标
2、因为n永远是2的次幂，所以n-1通过二进制表示，永远都是尾端以连续1的形式表示（00001111，00000011）当(n-1)和hash做与运算时，会保留hash中后x位的1
好处
&运算速度快，至少比%取模运算块
能保证索引值肯定在capacity中，不会超出数组长度
(n-1)&hash，当n为2次幂时，会满足一个公式：(n-1)&hash=hash%n
put
大体流程
1、根据key通过哈希算法和数组长度-1进行与运算得到数组下标
2、如果数组下标位置元素为空，则将key和value封装为Entry对象（jdk7是Entry对象，jdk8是Node对象）并放入该位置
3、如果数组下标不为空
jdk7
1、先判断是否需要扩容
2、如果不用扩容就生成Entry对象，并使用头插法添加到当前位置的链表中
jdk8
当前位置上的Node类型为红黑树
1、将key和value封装为一个红黑树节点并添加进红黑树
2、在过程中会判断红黑树中是否存在此key，存在的话更新value
当前位置上的Node类型为链表
1、将key和value封装为一个链表Node并通过尾插法插入到链表的最后位置去
2、尾插法要遍历链表，在遍历过程中会判断是否存在当前key，存在则更新value
3、遍历完成后，将链表新Node插入到链表中去，判断是否链表节点超过8
4、若超过8调用treeifyBin()方法，会判断数组长度是否大于64，若小于则执行resize操作，若大与则转换为红黑树
64的容量之前，因为容量比较小，在数据量比较多的时候，很容易出现hash冲突，直接扩容的效率比树化并不差，并且还可以减少后续元素落在同一个index的概率
插入链表或红黑树后，才会判断是否需要扩容
tableSizeFor
1、cap-1：是为了传进来的本身就是2的幂次方整数这种情况不减一会返回本身的两倍，减一返回本身
concurrentHashMap
无参构造方法
Segment[]，默认长度为16
每个Segement保存HashEntry[]，默认长度为2
Segment
继承了ReentrantLock，是一个锁对象，实现了分段锁机制
HashEntry
初始容量为32
我们添加的元素，是存入对应的Segment中的HashEntry[]中。所以ConcurrentHashMap中默认元素的长度是32个，而不是16个
method
hash(Object k)
h ^=k.hashCode()，在经历一系列比较复杂的位运算，获取hash值
注意：键值对都不允许为null，否则报空指针异常
通过高位来获取segment[]的下标，通过低位来获取HashEntry[]的下标
1、首先尝试获取锁
获取到后，继续走到自己的方法
while(!try.Lock())锁的自旋
如果自旋超过了64次，直接进行lock()操作
size()
1、获取segment[]
2、获取modCount的累加值和真正size的累加
3、判断modCount和上次是否相同，不相同将modCount赋值给last，最少循环两次，当循环到第五次时会加锁
4、挨个解锁
5、如果溢出则返回int最大值，如果没有则返回size
变量
sizeCtl
0
数组未初始化，且数组初始容量为16
1或大于1
数组未初始化，记录的是数组初始容量，如果已经初始化，则记录数组的扩容阈值
-1
数组正在进行初始化
小于0 但不为-1
数组正在扩容 ，-（1+n），表示此时有n个线程正在共同完成数组扩容操作
HASH_BITS
0x7fffffff
32位字节码只有第一位是0
初始化
new时不传任何参数，默认是无参的构造方法
传入容量参数32时，会给tableSizeFor传 （32+(32>>>1)+1）
在put的时候，才会对数组初始化
spread
(h ^ (h>>>16)) & HASH_BITS
initTable
1、不断自旋的判断使用CAS替换sizeCtl的值为-1，若CAS操作成功个，则对Node数组进行初始化，
2、sizeCtl=sz=n-(n>>>2)存储阈值
Unsafe（CAS核心类）
一、简介
Unsafe类相当于是一个java语言中的后门类，**提供了硬件级别的原子操作**
二、Unsafe Api
arrayBaseOffset
获取数组的基础偏移量
arrayIndexScale
获取数组中元素的偏移间隔，要获取对应所以的元素，将索引号和该值相乘，获得数组中指定角标元素的偏移量
getObjectVolatile
获取对象上的属性值或者数组中的元素
getObject
获取对象上的属性值或者数组中的元素，已过时
putOrderedObject
设置对象的属性值或者数组中某个角标的元素，不保证线程间即时可见性，更高效
putObjectVolatile
设置对象的属性值或者数组中某个角标的元素
putObject
设置对象的属性值或者数组中某个角标的元素，已过时
三、问题
1、ABA
CAS是比较值，如果值相等则变换。此处可能存在这样的情况，线程1获取变量值为5，线程2将值改为10，线程3再将值改回5。对于线程1，变量的值没有变，但对于计数等后续操作是不正确的
解决思路
可以参考数据库乐观锁机制，加版本号，变量更新时版本号会改变。通过比较版本号代替比较变量值。与集合的Fast-Fail机制类似，检查modCount值是否一致
0 条评论
回复 删除
下一页
