普通集合

✔List

✔ArrayList

特性：

• 内部是一个数组，初始状态容易为10， 数组满了之后扩容（数组复制）， 为capacity+capacity>>1=1.5*capacity

基本方法：

• add(E)：O(1),内部数组扩容的话会是O(N)
• add(int,E)：O(N)
• get(int)：O(N)
• remove(int)：O(N)，会移动数组
• remove(Object)：O(N),会移动数组

使用：

• 尽量在初始化时就指定容量，这样有助于减小数组扩容带来的内存和CPU的损耗

✔LinkedList

特性：

• 一个双向链表，每个元素都有两个指向，一个指向前一个元素，一个指向后一个元素
• 读取某个位置的元素，需要进行遍历；添加元素到列表的头或尾会比较快O(1)

基本方法：

• addFirst(E),addLast(E),add(E)：O(N)
• getFirst(),getLast()：O(1)
• get(int):需要遍历，时间复杂度为O(N)
• removeFirst(),removeLast(),remove()：O(1)
• remove(E),remove(int)：O(N)

✔Map

✔HashMap

特性：

• 用数组来做哈希表，初始大小为16
• 发生hash冲突时，会以列表的形式存储，当冲突超过8个，会以红黑树来存储（jdk1.8新属性）
• 如果HashMap的大小超过负载因子（默认是3/4）,就会resize为原来的2倍
• resize的时候，bucket<<1（原来的2倍），冲突的元素要么在原来的位置，要么是原来移动2次幂（ 减少重新计算hash值 ）

使用：

• 尽量在初始化时就指定容量
• 并发环境千万不要用HashMap,会出现死循环，请用并发集合ConcurrentHashMap

✔TreeMap

特性：

• 红黑树实现，是一种自平衡二叉树
• 查询，插入都是LOG(N)

✔Set

✔HashSet

特性：

• 其实就是集成了一个HashMap,key来存东西，value都设置为null

✔完