java集合梳理
2024-03-18 15:40:49 8 举报
AI智能生成
登录查看完整内容
Java List Java Set Java Map
作者其他创作
大纲/内容
内容发生变化,就会改变modCount的值
Iterator遍历的时候,检测modCount变量是否为expectedmodCount值,是的话就返回遍历;否则抛出ConcurrentModificationException 异常,终止遍历。
modCount
fail-fast
使用 Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合
集合不能被修改
使用 Iterator.remove() 方法
移除 Collection
遍历 Set 和 List 集合,只能单向遍历
Iterator
添加了一些额外的功能,添加一个元素、替换一个元素、获取前面或后面元素的索引位置
遍历 List,可以双向遍历
ListIterator
Iterator 和 ListIterator
for 循环遍历,基于计数器
迭代器遍历,Iterator
只能做简单的遍历,不能在遍历过程中操作数据集合,例如删除、替换。
foreach 循环遍历,foreach 循环遍历
遍历方式
先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素,然后遍历 elementData,只序列化已存入的元素
不希望 elementData 数组被序列化,重写了 writeObject 实现
ArrayList 的 elementData 加上 transient
指向同一个内存空间,引用是否相同
==
所指向的内存空间的值是不是相同
equals
==与equals的区别
如果没有元素 poll()会返回 null,而 remove()会直接抛出 NoSuchElementException 异常。
add和offer
在进行检索或移除一个元素的时候,它会等待队列变为非空;当在添加一个元素时,它会等待队列中的可用空间
用于实现生产者-消费者模式
BlockingQueue
Arrays. asList(array)
array 数组
toArray()
ArrayList 集合
Array 和 ArrayList
collection 集合类的一个顶级接口
Collections 工具类/帮助类
Collection 和 Collections
知识
对一个有序的key集合进行遍历
红黑树
有序
实现 Comparable 接口compareTo()方法
在排序时如何比较元素
第二个参数,参数是Comparator 接口的子类型(需要重写 compare 方法实现元素的比较),通过接口注入比较元素大小的算法
Collections 工具类中的 sort()方法
TreeMap
保持插入顺序
双向链表
LinkedHashMap
扩容 hashCode ->> 扰动函数 ->> (h&length-1)重新去计算其Hash值,根据Hash值对其进行分发
头插法(先讲原位置的数据移到后1位,再插入数据到该位置),高并发可能会出现循环链表问题
扰动处理 = 9次扰动 = 4次位运算 + 5次异或运算
数组+链表
jdk7
扩容 扩容后的位置=原位置 or 原位置 + 旧容量
尾插法(直接插入到链表尾部/红黑树)
扰动处理 = 2次扰动 = 1次位运算 + 1次异或运算高16bit不变,低16bit和高16bit做了一个异或两次就够了,已经达到了高位低位同时参与运算的目的
大于阈值(默认为8),数组+红黑树,从原来的O(n)到O(logn)
jdk8
每个对象生成的hashcode通过hash分桶,再通过equals判断是否相同
equals方法被覆盖过,则hashCode方法也必须被覆盖
hashCode()与equals()
size是否超多了最大容量threshold,扩容或者红黑树
null直接添加,不为空使用equals判断是否相同进行覆盖或者添加
计算下标index = (table.length - 1) & hash
hash 高16bit不变,低16bit和高16bit做了一个异或,目的是减少碰撞
put
HashMap 的长度为什么是2的幂次方取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作提高运算效率&操作 1111取模
要么在原位置,要么移动到原偏移量两倍的位置
初始大小为16,扩展2倍,Threshold 0.75
扩容
HashMap
初始大小为11,之后每次扩充,容量变为原来的2n+1
synchronized 全表锁
HashTable
默认分配16个Segment,比Hashtable效率提高16倍
分割分段(Segment),Segment + HashEntry,分段锁
Node还没有初始化,CAS插入
Node不为空,且当前该节点不处于移动状态,则对该节点加synchronized锁
只锁定当前链表或红黑二叉树的首节点
synchronized 和 CAS 粒度为一个节点
Node 数组+链表+红黑树
ConcurrentHashMap
Map
增加 50%
查找、尾增删快
数组
Arraylist
删除、插入快
双向循环链表
LinkedList
扩容每次会增加 1 倍
Synchronized
线程安全
Vector
Collections.synchronizedList
合适读多写少的场景
需要拷贝数组,会消耗内存
不能用于实时读的场景,像拷贝数组、新增元素都需要时间
没法保证 CopyOnWriteArrayList 到底要放置多少数据,万一数据稍微有点多,每次 add/set 都要重新复制数组
写入将导致创建整个底层数组的副本,而源数组将保留在原地,使得复制的数组在被修改时,读取操作可以安全地执行
1.加锁:保证同一时刻数组只能被一个线程操作;
2.数组拷贝:保证数组的内存地址被修改,修改后触发 volatile 的可见性,其它线程可以立马知道数组已经被修改;
3.volatile:值被修改后,其它线程能够立马感知最新值
1.volatile 关键字修饰的是数组,如果我们简单的在原来数组上修改其中某几个元素的值,是无法触发可见性的,我们必须通过修改数组的内存地址才行,也就说要对数组进行重新赋值才行。
2.在新的数组上进行拷贝,对老数组没有任何影响,只有新数组完全拷贝完成之后,外部才能访问到,降低了在赋值过程中,老数组数据变动的影响。
加锁 + 数组拷贝+ volatile
CopyOnWriteArrayList
List
TreeSet
LinkedHashSet
HashSet的值存放于HashMap的key上,HashMap的value统一为PRESENT
HashSet
set只能用迭代,因为他无序,无法用下标来取得想要的值
Set
java集合
0 条评论
回复 删除
下一页