05_集合
2024-05-23 21:52:05 4 举报Java集合源码剖析,ArrayList，linkedlist，hashmap，stack，linkedhashmap等
作者其他创作
大纲/内容
LinkedHashMap
6 b
100
压入
fail-fast机制
109
110
扩容1倍
l 代表的是上一个node把上一个node的next指针指向新增的这个node
Y
null
张三
在数组下标设置值elementData[size++] = e
prev
3 e
4 现在指向
7 null
c
99
first不动
108
iteam
引用
next
Node
5
elementAt(len - 1);
4
红黑树插入node
add()
5 c
扩容原来的一半，总大小是原来的1.5倍
2
first
120
put的对象的hash和key都和原来index位置上的node一直，就进行覆盖，替换旧值
LinkedList
Set 底层完全基于HashMap，Set直接set一个只有key和空value的node。linkedHashSet 基于linkedHashMap实现，用链表记录顺序。TreeSet基于TreeMap实现，可以实现key自然排序和自定义排序
130
转为红黑树
0 a
l
当前值插入后的数组长度大于插入之前的长度
1 f
直接将node PUT到index位置
color = BLACK
last
l.next
1
N
初始化大小16和负载因子0.75f
e
3
2 g
hash降低冲突新算法(h = key.hashCode()) ^ (h >>> 16)通过高16位和低16位异或，更好的获取hash特征，让数据更加分散的分布在map数据结构中
删除弹出的数据，也就是最后加入的对象removeElementAt(len - 1)
put
在初始化Iterator里面的 expectedModCount 就会被初始化为当时的modCount，也就是当前的修改次数。如果迭代到某一个node发现modCount != expectedModCount 就会抛出ConcurrentModificationException，并发修改的异常，终止迭代，这个机制就叫做fail fast异常
压入栈顶，也就是最后一个，可能会扩容
4 d
peek()找出对象
hash寻址通过位运算&操作来代替取模length & hash每次扩容，数组的大小就是2的n次方，保证定位到某个index中去
第2次
split 数据重排
获取指定位置的数据：（它已经尽力了）get(5) 获取第5个元素，他会做一个“于” index > (size >> 1) size >> 1获取到当前链表的长度的一半如果index在上半段，就从头开始向后找；反之，就从链表的尾部开始向前查找。
2 f
ArrayList
resize()
基本原理：左小右大但是红黑树是有旋转，变色和动态调整整个tree的平衡机制，是一个平衡的二叉查找树
pop()弹出对象
之前指向
链表长度是否>8
b
111
left
数据结构：红黑树性能：O（logn） ， hashMap在不考虑冲突的情况下是O（1）特点：根据key的自然顺序排序或自己实现comparator场景：大量统计或者增删改查的KV场景，希望有顺序的KV场景。（非插入顺序）
1 g
4 d
初次
是否treeNode
head
数据结构：链表 + Map（数组+链表+红黑树），是HashMap的高级封装。场景：需要记录顺序的KV集合亮点：继承HashMap，重写了newNode方法，在新增完node后，执行了linkNodeLast来记录顺序。链表的核心对象Entry继承了HashMap.Node。增加了before和tail两个指针默认按插入顺序，也可以设置true/false 改变顺序为访问书顺序
tail
push()压入对象
链表
新插入的node
指向
依然指向
right
结构：数组+链表+红黑树使用场景： 高性能 无序 非多线程 KV存储需求扩容：达到（负载因子*长度）后，进行扩容，扩容后，大小和负载因子都翻一倍亮点：hash高低位异或，取特征进行hash寻址，减少冲突通过位操作&，代替取模%，提高性能控制链表长度，大于8直接转换为红黑树，get的时间复杂度从O(n)变为O(logn)
peek()elementAt(len - 1);
a
Stack
是否红黑树
index位置是否有Node对象
5 指向
扩容：int newCapacity = oldCapacity + (oldCapacity >> 1);亮点：位移扩容，增加到原来容量的1.5倍右位移1，相当于capacity/2
Map（数组+链表+红黑树）
栈，stack继承vector，实现栈数据结构：数组特点：先进后出扩容：和ArrayList扩容机制一样，但是默认扩大原来的2倍，而不是1.5
parent
HashSet LinkedHashSet TreeSet
当前node.next
李四
TreeMap
扩容resize()原来的2倍
HashMap
如果当前index的next指针是null，也就是数组的这个index上不是链表，就直接放入node即可。如果不是null，则将链表重排，值得注意的是，扩容两倍后，如果原来的数据是在index=3的位置上，那重排后，就是在index=3+原大小 的下标上
扩容grow()
是否要扩容minCapacity - elementData.length > 0
0 条评论
下一页
为你推荐
查看更多
