Java集合（复习整理）
概念
- 围绕一组标准接口设计，是一个用来代表和操作集合的统一架构
包含内容
接口
- 操纵独立的集合代表细节
实现(类)
- 实现接口，可重复使用
算法
- 多态，不同的集合相同的方法(插入，排序等)有着不同的实现
图
image
image
接口
Collection
-
List
- 继承Collection 和一个 List 实例存储一个有序集合的元素
-
Set
-
不包含重复元素的集合
-
SortedSet
- 继承Set，保存有序的集合
-
-
Queue
Map
-
将唯一的键映射到值(键/值对)
-
SortedMap
- 继承于Map，使Key保持在升序排列
Iterator
集合类
Java提供了一套实现Collection接口的标准集合类
List
-
LinkedList
-
继承于AbstractSequentialList(继承于 AbstractList)，实现一个链表
- 实现List接口
- 实现双向链表(Deque)结构，方便头尾插入数据
- 实现队列(Queue)接口，先进先出
-
默认大小是10，每次1.5倍
-
-
ArrayList
-
继承于AbstractList，实现动态数组
-
解决数组的局限性
-
常用方法
-
add
-
remove
-
size
- 大小
-
-
ArrayList实现List接口，常见写法会把引用声明为List类型
-
指明泛型，只能存储指定的元素及其子类；不指明可以存放任何类型
-
遍历
- for
- iterator
- 增强型for循环
-
数组构建
-
-
-
区别
-
ArrayList
- 插入，删除慢，查询快（顺序结构）
-
LinkedList
- 插入，删除快，查询慢（链表结构）
-
-
stack
-
vector
Set
-
HashSet
-
继承于AbstractSet，并且使用一个哈希表
-
元素不能重复
-
元素插入无顺序
-
遍历
- 迭代器
- 增强型for循环
-
与HashMap关系
- 内部封装了一个Map
-
-
-
LinkedHashSet
- 继承于HashSet
- 具有可预知迭代顺序的Set接口的哈希表和链接列表实现
-
TreeSet
- 继承了AbstractSet，使用元素的自然顺序对元素进行排序
- TreeSet可以确保集合元素处于排序状态
CopyonWriteArrayList和CopyOnWriteArraySet
-
原理：读写分离，读支持高并发，写需要加锁
-
问题
- 内存占用
- 数据一致性问题，支持最终一致性，不支持实时一致性
Map
-
HashMap
-
存储数据方式
-
键值对
- key唯一，不可重复，值可重复
-
-
继承了HashMap，并且使用了哈希表
-
非线程安全类
-
JDK7：数组+链表
-
JDK8：数组+链表+红黑树
-
HashMap1.7为什么使用的是头插法，1.8后使用尾插法，这个改变有什么作用吗
-
jdk8之前hashmap这种插入方法在并发场景下如果多个线程同时扩容会出现循环列表
-
HashMap在jdk1.8之后引入了红黑树的概念，
表示若桶中链表元素超过8时，会自动转化成红黑树；
若桶中元素小于等于6时，树结构还原成链表形式。-
选择6和8的原因
- 中间有个差值7可以防止链表和树之间频繁的转换
-
-
不安全主要发生在扩容时，容易产生循环链表
-
-
ConcurrentHashMap
-
1.7与1.8的区别
-
1.8使用Unsafe类的CAS自旋赋值+synchronized同步+
LockSupport阻塞等手段实现的高效并发- 采用头插法
-
-
-
-
LinkedHashMap
- 继承于HashMap，使用元素的自然顺序对元素进行排序
-
HashTable
- 线程安全类
-
TreeMap
- 继承了AbstractMap，并且使用了一棵树
二叉树
结构
- 根结点，每个根节点都有左子节点，右子节点
排序
-
左序
- 根左右
-
中序
- 左根右
-
右序
- 左右根
