集合

• 概念：对象的容器，定义了对多个对象进行操作的常用方法。可实现数组的功能。
• 和数组的区别：
  1. 数组长度固定，集合长度不固定。
  2. 数组可以存储基本类型和引用类型，集合只能存储引用类型。
• 位置： java.util.*;

1. Collection体系集合

2. 集合框架

• 集合

  • Collection
    • List（有序可重复）（常用）
      • ArrayList
        • add()
        • remove()
        • contains()
        • size()
      • LinkedList（常用）
        • getFirst()
        • removeFirst()
        • addFirst()
        • getLast()
        • ...
        • 单向链表
        • 双向链表
      • Vector（比较少用）
        • Stack
    • Set（无序不可重复）
      • HashSet（常用）
      • TreeSet
  • Map
    • HashMap（重点，高频）
      • JDK1.7：hash表=数组+链表
      • JDK1.8：hash表=数组+链表+红黑树
        1. 先按照数组的index存储，index相同会存储给index下的链表，链表个数大于等于8后会转成红黑树进行存储。
        2. 红黑树是一颗接近于平衡的二叉树，查询的时间复杂度为O(logn)，比链表的查询效率高。
        3. 数组长度必须是2的指数次幂，因为需要进行位运算，如不是2的指数次幂会造成空间闲置。
        4. 加载因子必须是0.75.
           1. 最大值1，最小值0.5.
           2. 加载因子为最大值的时候，只有当元素填满数组长度才会扩容。可以最大提高空间效率，但查询效率低下。
           3. 加载因子为最小值的时候，达到数组空间一般就会扩容，可以最大可能减小hash冲突，链表长度也会减小，但是会造成空间浪费。
    • TreeMap

• Collections工具类

• 泛型<> 约束，避免类型转换之间的问题
• Inerator：迭代器