java集合类源码分析
2023-06-26 17:26:51 0 举报AI智能生成
登录查看完整内容
java集合类源码分析
作者其他创作
大纲/内容
底层实现数据结构是数组，内存结构是连续的
与普通数组相比，ArrayList实现了动态扩容机制
增删较慢，查询快
线程不安全
特点：
ArrayList中维护了一个Object类型的数组elementData
当new ArrayList（）的时候，默认会创建一个空的Object数组，大小为0在第一次使用add方法添加数据的时候，会给这个数组初始化一个大小，这个大小默认为10
之后在每次调用add方法时，都会先计算整个数组的空间够不够，如果够就直接添加就好了，如果不够，则会触发扩容扩容在源码中，有一个grow（）方法，每次扩容都是原来的1.5倍，比如说，初始值是10，那么当第11个元素进来的时候，会发现数组的空间不够了，所以就会触发扩容，容量会扩大到15数组扩容完之后，会调用Arrays.copyOf()方法来对数组进行拷贝
如果需要调用addAll时容量不够，也会触发扩容，但是和add方法的扩容策略不同的是，addAll方法是按照最小容量来进行扩容的
源码逻辑概括：
ArrayList
底层实现数据结构是双向链表
增删较快，查询较慢
LinkedList底层维护了一个双向链表
还维护了两个属性为first和last的节点，分别为首节点和尾节点
每个节点里面又维护了prev，next，item三个属性，通过prev指向前一个节点，通过next指向后一个节点，最终实现双向链表
所以LinkedList的元素的添加和删除不是通过数组完成的，相对来说效率更高
源码概括：
LinkedList
底层实现数据结构也是数组
也有动态扩容机制
Vector是线程同步的，也就是线程安全的，Vector类的操作方法都带有Synchronized
Vector和ArrayList差不多，区别就在于grow（）方法中的扩容大小不同，Vector的扩容大小为原来的2倍，而ArrayList为1.5倍
然后Vector的所有操作方法都有Synchronized关键字修饰
Vector
List
无序（添加和取出的顺序不一致），取出的顺序取决于hash后，在确定索引的结果，没有索引
不允许重复元素，所以最多包含一个null
实际上是用的HashMap的键实现的，所有值默认为一个静态常量Object类（private statis final Object PERSENT = newObject（））
使用自定义对象为元素时，如果需要保证存储唯一，则需要重写自定义对象的hashcode（）方法
底层使用的是HashMap
添加一个元素时，先得到hash值（计算hash值的算法为：hashCode（算法为h= key.hashCode()^（h>>>16）），使用按位异或和算术右移操作的是为了减少hash碰撞概率），然后用hash值和table长度做&运行得到索引值
然后判断存储数据的table中该索引处是否有值，如果没有则直接添加，如果有则先判断是链表还是红黑树，
如果是链表则用for循环依次和该链表的每一个元素比较，如果链表中有相同的则直接不添加，如果没有则添加到链表的尾部，添加到链表尾部后，会立即判断当前链表长度是否达到8，如果达到8则调用treeifyBin（）方法，这是会判断table的长度是否>64，如果>64则进行树化操作，如果<64就会先扩容调用resize（）方法
如果是红黑树，则判断红黑树中是否有该元素，如果没有则添加到树中，如果没有则不添加
在添加完最后会判断数组元素是否>扩容临界值/阈值（负载因子*数组大小），如果大于则会进行扩容，扩容大小是原来的两倍
HashSet
LinkedHashSet继承了HashSet
LinkedHashSet更据元素的hashCode值来决定元素的存储未知，同时使用双向链表维护元素的次序，以保证存取的有序
LinkedHashSet不允许添加重复元素
底层是一个LinkedHashMap（是HashMap的子类），底层维护了一个数组+双向链表
LinkedHashSet中维护了一个数组table+双向链表，还有head节点和tail节点
第一次添加时，直接将数组table扩容到16，存放的节点类型是LinkedHashMap$Entry类型，添加元素时，会先确定该元素在table数组中的位置，然后添加元素（添加逻辑和HashSet的逻辑一样），然后将添加的元素添加到双向链表
添加的每一个节点有before和after属性，这样形成双向链表，来确保存取顺序
LinkedHashSet
底层使用的是TreeMap
TreeSet
Set
Collection
jdk1.7底层使用数组+链表的方式实现，每次插入使用的是头插法
jdk1.8底层使用数组+链表+红黑树的方式实现，每次插入使用的是尾插法
无序
HashMap是线程不安全的
Node内部类实现了Map.Entry接口，Map.Entry接口主要提供一些方法，如K getKey()，V getVaule()
执行put() 方法添加一个key-val时，先得到key的hash值（计算hash值的算法为：hashCode（算法为h= key.hashCode()^（h>>>16）），使用按位异或和算术右移操作的是为了减少hash碰撞概率），然后用hash值和table长度做&运行得到索引值
然后判断存储数据的table中该索引处是否有元素，如果没有则直接添加，如果有则先判断该元素的key和准备加入的key是否相等，如果相等则直接替换原有val
如果不相等则判断是树结构还是链表结构，作出响应的处理
如果判断存储是链表则用for循环依次和该链表的每一个元素比较，如果链表中有相同的则直接不添加，如果没有则添加到链表的尾部，添加到链表尾部后，会立即判断当前链表长度是否达到8，如果达到8则调用treeifyBin（）方法，这是会判断table的长度是否>64，如果>64则进行树化操作，如果<64就会先扩容调用resize（）方法，因为调用resize（）会对HashMap中的元素进行重新散列hash
如果是红黑树，则判断红黑树中是否有该元素，如果没有则添加到树中，如果有则不添加
调用remove（）方法删除元素时，当数组中元素是红黑树时，红黑树元素个数等于6时，会进行树的退化，由红黑树退化成链表
容量是2的n次幂，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞，避免形成链表的结构，使得查询效率降低！
为什么初始化容量都是2等n次幂？
HashMap
HashTable中的健值都不可为null，否则会抛出空指针异常
HashTable是线程安全的（操作方法上加了Synchronized关键字）
底层有数组HashTable$Entry[] 初始化大小为11
调用put（）方法会内部执行addEntry（hash，hash，value，index）；添加K-V封装到Entry中
扩容机制是，当HashTable中元素个数>阈值时，就进行扩容
扩容按照int newCapacity = (oldCapacity <<1)+1;的大小扩容（也就是原来容量的2倍+1）
HashTable
和linkedHashSet实现差不多，只不过存的是双列值K-V
LinkedHashMap
底层使用红黑树数据结构
可以传一个Comparator匿名内部类
如果没有传Compartor匿名内部类则会默认按照ASCII自然排序
如果传了Compartor匿名内部类则会调用compare方法进行循环遍历比较
如果循环遍历比较过程中，发现准备添加的key和当前key相等，就覆盖值
TreeMap
Map
默认初始化元素的长度为32，由Segment[]数组默认长度（16）* HashEntry[]数组默认长度（2）可得32
Segment对象实现了ReentrantLock对象（这也就是所谓的分段锁，每个Segment对象都有自己的锁）
不允许空值空键
底层使用Segment锁对象（分段锁）+红黑树+链表实现
1，调用put（）方法，会使用key计算hash值，然后使用key的hash值取高位计算Segment[]的索引
2，然后判断Segment[]中，当前索引位置是否为null，如果为空则创建HashEntry[]放在当前索引位置，然后返回当前Segment对象，如果不为null，则直接返回Segment对象
3，然后调用当前Segment对象中的put（）方法，此时会调用tryLock（）方法尝试获取当前Segment对象的锁，如果获取锁成功就继续往下执行，如果获取锁失败则调用scanAndLockForPut（）方法自旋获取锁，最大自旋次数是64，然后调用lock（）方法加阻塞锁，在自旋的同时会创建好HashEntry对象
4，当获取到锁后，会先拿到Segment对象中的HashEntry[] 数组，同时使用key的hash值和HashEntry[]数组的大小进行&运行（int index= （tab.length-1）&hash），获取当前需要存储的值在HashEntry[]数组中的索引下标
5，获取到HashEntry[]数组下标后，会判断该下标处是否为null，如果为null则直接创建一个HashEntry对象，然后元素个数+1，然后在判断是否需要扩容，如果不需要扩容则直接添加值
6，如果获取到HashEntry[]数组下标后，判断该下标处不为null，则会判断当前当前HashEntry链表中是否有相同key，有则替换，没有则添加
7，在添加前会判断元素大小是否>阈值，如果大于则需要扩容
8，扩容后的HashEntry[]数组大小为原来的2倍，然后比那里原来的元素，重新按新HashEntry[]的长度进行&操作
9，调用size（）方法获取集合长度，会遍历拿到每个Segment对象中的元素个数累加，然后到最后一个Segment对象时会遍历给所有Segment对象加lock锁，然后统计出元素的总个数，之后会记录最后一次统计元素个数的值，然后在进行第二次元素个数的统计，如果与第一次统计值相等则判断证明没有进行新的增删改操作，返回sum，如果不相等则继续统计，最多统计4次，最少统计两次，也就是说，这个for循环最少会执行两次，然后统计成功后释放锁
源码概括
jkd1.7
线程安全的
扩容有多线程协助扩容
底层使用CAS+synchronize锁+红黑树+链表实现
ConcurrentHashMap与HashMap一样，new的时候不会初始化数组大小，只有调用put（）方法往里面添加元素时才会初始化大小，默认初始化大小为16
sizeCtl为0，代表数组未初始化， 且数组的初始容量为16
sizeCtl为正数，如果数组未初始化，那么其记录的是数组的初始容量，如果数组已经初始化，那么其记录的是数组的扩容阈值
sizeCtl为-1，表示数组正在进行初始化
sizeCtl小于0，并且不是-1，表示数组正在扩容， -(1+n)，表示此时有n个线程正在共同完成数组的扩容操作
sizeCtl含义：
ConcurrentHashMap中有一个volatile 修饰的sizeCtr成员变量，如果sizeCtl是-1，表示正在初始化，如果是正数表示当前数组要扩容时候的阈值，如果是0则是未初始化
1，调用put（）方法，会调用putVal（）方法，然后计算使用key计算hash值，然后判断数组是否初始化，如果没有初始化就会先初始化，默认初始化大小是16
2，如果已经初始化了，则通过hash计算得到桶位是否有元素，如果没有则利用cas添加元素
3，如果计算桶未知元素的hash为MOVED，则证明此时正在扩容，此时就会先去协助扩容
4，如果计算桶位置元素不是空，且当前没有处于扩容阶段，就进行元素的添加
5，在给对应桶位置添加元素时，会使用synchronized代码(锁对象是索引位置当前节点对象)块给当前桶位置节点上锁，保证线程的安全
7，如果判断hash不满足>=0的条件，此时桶内节点为红黑树节点，此时会往红黑树中添加元素
9，最后会调用addCount（）方法去维护元素个数
10，统计元素个数时，先会使用baseCount属性去进行CAS操作，如果加成功，则统计完成
11，如果使用baseCount属性进行CAS操作失败，则会调用fullAddCount（）方法，初始化出一个CounterCell[]数组，然后通过计算给这个数组中的一个元素进累加，累加成功则最后进行计算元素个数，如果计算在整个数组中的所有元素都没有累加成功，会进行CounterCell[]数组扩容，扩容后继续重新计算数组元素进行累加
12统计完元素个数后，会判断当前数组元素个数是否满足扩容条件，如果满足则会触发扩容机制
14，协助扩容的线程会去领取自己负责迁移数据的任务，此时会判断当前cpu核心数，如果是多核心cpu，那么每个线程会划分任务，最小任务是16个桶位置，任务的划分是从后往前开始划分的
15，当线程领取到了任务后，会从后往前进行帮助数据迁移，如果前完一个桶位置元素，则会将该迁移完的桶元素位置赋值为ForWardingNode节点对象（这个FowardingNode节点对象的hash值为1）
jdk1.8
ConcurrentHashMap
写时复制
new CopyOnWritArrayList时会创建一个长度为0的数组
CopyOnWritArrayList中有一个ReentrantLock的成员变量
当调用add（）方法添加元素时，会使用ReentrantLock的lock方法上锁
添加元素成功后，新数组将旧数组替换，然后会在finally中释放锁
调用get（）方法的时候，不会上锁，会获取老数组中的数据，也就是说CopyOnWriteArrayList的数据实时性比较低
CopyOnWriteArrayList
牺牲了一些新增的效率，提高了查询的效率
红黑树特点：
集合类源码分析
增删多
改查多
允许重复
HashMap（键不允许重复）
有序
不允许重复
如何选择集合实现类
反转List中的元素的顺序
reverse（List）
对List集合中元素进行随机排序
shuffle（List）
更据元素的自然顺序对指定List集合元素按升序排序
sort（List）
根据指定的Comparator产生的顺序对List集合元素进行排序
sort（List，Comparator）
将指定集合中的i处元素和j处元素进行交换
swap（List，int，int）
根据元素的自然排序，返回给定集合中最大的元素
max（Collection）
更据Comparator指定的顺序，返回给定集合中的最大元素
max（Collection，Comparator）
min（Collection）
min（Collection，Comparator）
将src中的内容复制到dest中
copy（List dest，List src）
返回集合中指定元素的出现次数
frequency（Collection，Object）
使用新值替换list对象的所有旧值
replaceAll（List list，Object oldVal，Object newVal）
Collections工具类常用方法
java集合类源码分析
收藏
收藏
0 条评论
回复 删除
下一页
