Java 集合框架
2021-03-07 17:48:49 0 举报AI智能生成
Java 面试集合框架 Map Set List
作者其他创作
大纲/内容
基础知识
数据物理结构
顺序存储结构：数组
一段连续的内存空间
优点：随机访问
缺点：插入删除效率低，大小固定
链式存储结构：链表
不连续的内存空间
优点：大小动态扩展，插入删除效率高
缺点：不能随机访问
索引
为了方便查找，整体无序，但索引块之间有序，需要额外空间，存储索引表
优点：对顺序查找的一种改进，查找效率高
缺点：需要额外空间存储索引
散列
选取某个函数，数据元素根据函数计算存储位置，可能存在多个数据元素存储在同一位置，引起地址冲突
优点：查找基于数据本身即可找到，查找效率高，存储效率高
缺点：存取随机，不便于顺序查找
数据逻辑结构
集合
数据元素同属一个集合，单个数据之间没有任何关系
线性
数据元素之间是一对一的关系
树形
数据元素之间存在一对多的关系
图形
数据之间是多对多的关系
线程安全
乐观锁：CAS + 自旋
悲观锁：ReentrantLock ，synchronize
Collection
List
ArrayList
数据结构：动态数组，自动扩容
添加元素时容量不够
新建一个数组，长度为原数组的长度 * 扩容因子 --> 1.5
新元素放入新数组，并将新数组赋值给集合，原数组丢弃
两个常量空数组：节省集合创建时占用的内容
EMPTY_ELEMENTDATA
构造器指定了初始容量，容量不够时按 1.5 倍进行扩容
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
无参构造器，初次添加元素时容量默认初始化为10，容量不足时再进行按照 1.5 倍扩容
迭代器：fail-fast（快速失败机制）
iterator() 获取迭代器时，保存 modCount(操作次数)快照，游标 cursor 初始化为 0
hasNext 判断条件： cursor != size， 如果有其他线程修改了集合长度(新增删除元素)，会导致 size 变化，modCount 和快照也会有差
next() 取元素时，为防止下标越界，先判断 modCount 和快照是否相同。不同意味着 size 已变化
拷贝：拷贝栈中的内容
拷贝前后变量是否独立
基本数据类型：独立
引用类型：不独立
String：独立
正常拷贝，实现 Cloneable 接口，clone 方法默认，则为浅拷贝
深拷贝：需要递归所有的引用类型，递归到基本类型和 String，数组为止，都拷贝一次
序列化
重写序列化方法，因为存放元素的数组 elementData 里面有很多占位用的 null，序列化时只需要按照 size 读写
Arrays.asList
接收的是可变参数，基本类型不支持泛型化。会把整个数组当成一个元素放入新的数组，传入可变参数。
Vector：线程安全
方法粒度的 synchronize
LinkedList
数据结构：链表，维护一个内部类 Node，元素以 Node 节点的 item 属性存在，同时维护 next 和 prev 记录前驱后继的指针
双端队列：实现了 Deque 接口
支持从首部和尾部存取元素
CopyOnWriteArrayList
数据结构同 ArrayList，数组 Array
写时加锁复制：ReentrantLock 保证线程安全，修改数组之前先将数组拷贝一份，操作新数组，并赋值给 array，旧数组丢弃
读操作无锁
写不会阻塞读，读写分离
弱一致性：写操作会生成新的数组，读的数据可能已经被修改，迭代器也是弱一致性，读的是快照
Set
HashSet
底层使用 HashMap 存储数据，用 map 的 key 存储元素
元素不可重复，key 不能重复
元素是无序的，key 是无序的
元素允许一个 null 值，key 允许一个 null 值
非线程安全，没有 get() 方法
虚拟对象 PRESENT，存 map 时，value 固定为此值
LinkedHashSet
没有成员变量及 api，全部使用 LinkedHashMap 替代
TreeSet
底层使用 NavigableMap 存储元素，实际上大部分情况都是 TreeMap
CopyOnWriteArraySet
底层使用 CopyOnWriteArrayList
调 addIfAbsent 方法保证元素的不可重复
ConcurrentSkipListSet
底层使用 ConcurrentSkipListMap
Map
HashMap 线程不安全
数据结构：数组 + 链表
jdk8 开始链表高度到8、数组长度超过64，链表转变为红黑树
构造红黑树必构造链表辅助，在链表的节点不多的时候，从整体的性能看来，数组+链表+红黑树的结构不一定必数组 + 链表的结构性能高
频繁的扩容，会造成底部红黑树不断的进行拆分和重组，这是非常耗时的。因此，也就是链表长度比较长的时候转变成红黑树才会显著提高效率
元素以内部类 Node 节点存在
元素存储
计算 key 的 hash 值，二次 hash 然后对数组长度进行取模，对应到数组下标
如果没有产生 hash 冲突（下标位置没有元素），则直接创建 Node 存入数组
如果产生 hash 冲突，先进行 equal 比较
相同则取代该元素
不同，则判断链表高度插入链表。链表高度达到8，同时数组长度到64则转变为红黑树，长度低于6则将红黑树转回链表
key 为 null，存在下标为 0 的位置
扩容
元素个数达到阈值 threshold，扩容 2 倍，新建数组
旧数组的数据移到新数组
遍历旧数组
重新计算每个元素的存储位置(原下标或者原下标 + 旧数组长度)
逐个转移数据
jdk7头插法
迁移链表，会导致元素顺序变成倒序，并发时可能导致环形链表，产生死锁
元素 A、B，线程1执行Entry<K, V> next = e.next; A.next = B, 线程挂起(e是全局变量table的迭代变量)
线程2也扩容，并完成扩容，新链表中顺序B、A，此时线程1执行，形成环形链表，进入死循环
jdk8尾插法
解决了死循环的问题
新数组引用到全局变量 table
重新设置阈值 threshold
初始容量
可以入参指定，官方要求输入 2的N次方的值，如果不是则取最近的一个2的N次方值
负载因子 loadFactor
扩容时的阈值，默认0.75
hashCode 定位下标，equal 定位节点元素
迭代器：fail-fast
HashTable 线程安全
数据结构同 HashMap(同 jdk7，没有红黑树)，操作也一致
synchronize 保证线程安全
CurrentHashMap 线程安全
jdk 7
数据结构：ReentrantLock + Segment + HashEntry，一个 Segment 中包含一个 HashEntry 数组，每个 HashEntry 又是一个链表结构
元素查询
第一次 Hash 定位到 Segment
第二次 Hash 定位到元素所在的链表的头部
锁：Segment 分段锁
Segment 继承 ReentrantLock
锁定操作的 Segment，其他的 Segment 不受影响
并发度为 Segment 个数，可以通过构造器函数指定
数组扩容不会影响到其他的 Segment
get 方法无需加锁
jdk 8
数据结构：synchronize + CAS + 红黑树
Node 的 val 和 next 都用 volatile 修饰，保证可见性
查找，替换，赋值操作都使用 CAS
锁：锁链表的 head 节点
不影响其他元素的读写，锁粒度更细，效率更高
扩容时，阻塞所有的读写操作
并发扩容
一个线程发起扩容时，就会通过 CAS 设置 sizeCtl 属性(volatile 修饰)，告知其他线程扩容状态变更。创建一个两倍容量的新数组 nextTable，单线程完成。
扩容时会判断这个值(sizeCtl 属性)，如果超过阈值则需要扩容
首先根据运算得到需要遍历的次数 i，然后利用 tabAt 方法获得 i 位置的元素 f
初始化一个 forwardNode 实例 fwd，如果 f == null，则在 table 中的 i 位置放入 fwd
否则采用头插法的方式把当前旧 table 数组的指定任务范围的数据给迁移到新的数组，然后给旧 table 原位置赋值 fwd
迁移数据至少每次获取 16 个迁移任务，transferIndex 扩容索引，迁移数据前先 CAS 操作该变量，相当于任务头指针
查到遍历过所有的节点以后就完成了复制工作，把 table 指向 nextTable ，并更新 sizeCtl 为新数组大小的 0.75 倍，
ForwardingNode 节点
标记作用，表示其他线程正在扩容，并且此节点已经扩容完毕
关联了 nextTable，扩容期间可以通过 find 方法，访问已经迁移到了 nextTable 中的数据
如果遍历到的节点是 forward 节点，就向后继续遍历，再加上给节点上锁的机制，就完成了多线程的控制。多线程遍历节点，处理了一个节点，就把对应点的值 set 为 forward，另外一个线程看到 forward，就向后遍历。这样交叉就完成了复制工作。
读操作无锁
Node 的 val 和 next 使用 volatile 修饰，读写线程对该变量互相可见
数组用 volatile 实现，保证扩容时倍读线程感知
TreeMap
红黑树实现
LinkedHashMap
继承 HashMap
顺序
accessOrder 为 false
插入顺序保存
accessOrder 为 true
访问顺序保存，访问会导致顺序变动
最近访问的元素在最后面
可以利用这个特性实现 LRU(缓存淘汰)
双向链表
元素直接有指针双向链接
Properties
以 key = value 的键值对的形式进行存储值。 key 不能重复
xml 和 properties 文件相互转化
0 条评论
下一页
