java中的集合有list、set、map、queue这三种，它们都基于collection接口实现。

# 常用集合

# list

list的实现类有ArrayList、LinkedList三种 ArrayList由数组实现，内部记录当前容量 添加元素：使用数组偏移量定位存放位置，当容量超过现有容量时会进行扩容，每次扩容增加原来容量的1/2 插入元素：对数组中插入偏移量之后的内容进行批量后移 删除元素：对数组中删除偏移量之后的内容进行批量前移 查找元素：使用数组偏移量进行查找 LinkedList由双向链表实现，增删查改操作同链表 ArrayList和LinkedList都不是线程安全的，如果需要保证线程安全，可以使用Collection.synchronize方法进行包装

# Map

map的实现类主要有HashMap，TreeMap，LinkedHashMap。 Hashmap使用数组存储元素，当发送hash冲突时使用链表解决冲突，当链表长度超过8时使用红黑树 无冲突时添加/取元素时间复杂度：O(1) 冲突时添加元素/取时间复杂度：O(logn)，n为链表长度 TreeMap与HashMap相同，且其中元素有序（按照添加顺序） Treemap使用红黑树来使得元素有序，读、写时间复杂度都为O(logn) LinkedHashMap与HashMap相同，常用来实现LRU队列

# Set

set的实现类主要是HashSet，TreeSet两种，实现方式同HashMap|TreeMap

# Queue

Queue的实现类为ArrayQueue，使用数组实现，并且添加了头尾指针