Iterable<br><i>interface</i><br>
Collection<br><i>interface</i><br>
List<br><i>interface</i><br>
ArrayList<br>
底层是基于数组来实现容量大小动态变化的。get效率高，非尾部的增删会带来元素的整体移动
插入时会判断数组容量是否足够，不够的话会进行扩容 扩容时重新申请新的内存空间，<br>并把就数组拷贝到新数组上去，非线程安全
int size;
实际元素个数
Object[] elementData;
数组存储 默认是空数组
DEFAULT_CAPACITY = 10;
初始容量大小为 10;一开始是空数组，第一次添加元素时容量扩大至 10 的。
Arrays.copyof() 拷贝数组
int newCapacity = oldCapacity + (oldCapacity >> 1);
可看出扩容因子子1.5
遍历用for 循环，效率高，用迭代器iterator 遍历会非常慢，因为做了很多安全检查但支持边遍历边remove
vector
很少用
线程安全，但性能低
增删改查很多方法都是synchronized 锁对象
扩容因子1
LinkedList
链表存储，不需要扩容
查找慢O{n),add remove 不需要移动节点，相对数组较快
CopyOnWriteArrayList<br>
线程安全 读写分离
volatile Object[] array;
通过volatile 确保可见性和可序性
get，遍历等读操作不会占用锁
ReentrantLock lock = new ReentrantLock();
通过锁确保增删改
add remove 等增删改都是基于内存副本操作，先复制一份副本，在副本进行修改，修改后原数组指针指向副本，<br>确保读操作不会受影响,（此时内存有二份数组，二份数组一个读一个写互不影响）
缺点
占用内存 1 增删改操作都要复制一个数组出来
只能保证数据的最终一致性，不能保证数据的实时一致性。
比如线程A在迭代CopyOnWriteArrayList容器的数据。线程B在线程A迭代的间隙中将CopyOnWriteArrayList部分的数据修改了<br>(已经调用setArray()了)。但是线程A迭代出来的是原有的数据,跟数据库的幻读差不多
MAP(散列表)<br>Interface<br>
HashMap<br>
数据结构
1.7 数组+链表
jdk1.8 数组+链表+红黑树
工作原理
Node<k,v>[K,V] table</k,v>
元素数组
键值对存储 每次读取插入删除会计算KEY的hash值,并通过哈希值计算对应数组的位置
hash 对应数组 位置 公式 (table.length - 1) & hashCode
如何解决哈希冲突
以1.8为例,会以链表或红黑树来保存多个node,<br>如果链表个数超过一定的门限,会转成红黑树存储,<br>如果红黑树的节点数小于门限,会转成链表
如何扩容
threshold
threshold=初始容量*默认填充因子
map的元素个数size > threshold 就会触发扩容 扩容的数组为原来length的2倍
扩容会重新申请新的数组,<br>并且把旧数组上元素<font color="#c41230">重新计算hash值</font> 添加到 新的数组上
如果可以预知要插入的数量,建议通过构造函数指定capacity的大小,<br>避免频繁扩容导致的性能损失
非线程安全
KEY value 允许null值 遍历是<font color="#f15a23"><i><b>无序</b></i></font>的
LinkedHashMap<br>
保存着元素插入的顺序(<font color="#f15a23"><b>插入有序性</b></font>)，并且可以按照我们插入的顺序进行访问
数据结构
数组 + 单链表 + 红黑树 + 双链表
在hashmap的基础上用双链表保存元素之家的先后插入关系
遍历时是根据双链表进行遍历,跟hashmap不一样
IdentityHashMap
基本不用
允许key相同数据插入
HashTable
线程安全
key、value都不可以为null
底层数据结构及扩容原理跟HashTable差不多 扩容不需要2的n次方
增删改也是通过synchronized把整个对象锁住,效率不高
ConcurrentHashMap替代HashTable
ConcurrentHashMap
数据结构跟hashmap及扩容基本一样
数据结构
1.7 数组+链表
jdk1.8 数组+链表+红黑树
线程安全
1.7以前采用的分段锁,把数组切成多个段segment
1.8 采用NODE + CAS + synchronized
TreeMap
数据结构
基于红黑树实现
默认按照keys的自然排序排列
区别
HashMap 无序 LinkedHashMap 插入有序性 TreeMap 按Key自然排序
HashMap ConcurrentHashMap HashTable 数据结构基本一样 HashTable 的KEY,VALUE 不允许null
ConcurrentHashMap HashTable 线程安全,ConcurrentHashMap效率更高
如果只需要存储功能，使用HashMap与LinkedHashMap是一种更好的选择；<br>如果还需要保证统计性能或者需要对Key按照一定规则进行排序，那么使用TreeMap是一种更好的选择。
SET<br>interface<br>
HashSet
哈希表结构(底层HashMap)，主要利用HashMap的key来存储元素
基本就是HashMap的缩水版,因为没有value,只有key
LinkedHashSet
LinkedHashMap的缩水版
