概览
Java数据结构(容器)主要包含 collection 和 Map两种.
Collection
Set
Set是不允许重复的集合
- TreeSet
- HashSet
- LinkedHashSet
List
List接口可以存储不唯一的有序的对象
- ArrayList
- Vector
- LinkedList
- Vector的子类Stack实现后进先出
Queue
- LinkedList
- PriorityQueue
Map
Map使用键值对，Key不能重复。
- TreeMap
- HashMap
- HashTable
- LinkedHashMap
具体特点
数组支持高效的随机元素访问（根据下标来随机访问）
链表不支持快速随机访问，但是插入删除效率高
ArrayList
底层使用的是Object数组
会预留一部分容量空间
ArrayList的扩容
LinkedList
底层使用的是双向链表
每一个元素都要存放两个指针
Vector
synchronised包裹ArrayList进行同步，是线程安全的
Collections. synchronizedList()
concurrent并发包下的CopyOnWriteArrayList
读写分离
写操作需要加锁,防止并发写入时导致写入数据丢失
写操作结束之后需要把原始数组指向新的复制数组
缺点在于内存占用翻倍,以及数据不一致
HashMap底层数据结构
数组+链表 从1.8开始，因为查找效率，引入了数组+红黑树（链表长度大于阈值默认为8）
二叉树和红黑树
红黑树是一种自平衡二叉树，区别于AVL树