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