集合

Collection(单列集合)

List(有序,可重复)

• ArrayList
  • 底层数据结构是数组,查询快,增删慢
  • 线程不安全,效率高
• Vector
  • 底层数据结构是数组,查询快,增删慢
  • 线程安全,效率低
• LinkedList
  • 底层数据结构是链表,查询慢,增删快
  • 线程不安全,效率高

Set(无序,唯一)

• HashSet
  • 底层数据结构是哈希表，哈希表依赖两个方法：hashCode()和equals()
  • 执行顺序：首先判断hashCode()值是否相同
    • 是：继续执行equals(),看其返回值；是true:说明元素重复，不添加；是false:就直接添加到集合
    • 否：就直接添加到集合
  • LinkedHashSet
    • 底层数据结构由链表和哈希表组成。
    • 由链表保证元素有序。
    • 由哈希表保证元素唯一。
• TreeSet
  • 底层数据结构是红黑树。(是一种自平衡的二叉树)
  • 如何保证元素唯一性呢? 根据比较的返回值是否是0来决定
  • 如何保证元素的排序呢?
    • 自然排序(元素具备比较性) 让元素所属的类实现Comparable接口
    • 比较器排序(集合具备比较性) 让集合接收一个Comparator的实现类对象

Map(双列集合)

Map集合的数据结构仅仅针对键有效，与值无关。

存储的是键值对形式的元素，键唯一，值可重复。

HashMap

• 底层数据结构是哈希表。线程不安全，效率高

• 哈希表依赖两个方法：hashCode()和equals()
  • 首先判断hashCode()值是否相同
    • 是：继续执行equals(),看其返回值；是true:说明元素重复，不添加；是false:就直接添加到集合
    • 否：就直接添加到集合
• LinkedHashMap
  • 底层数据结构由链表和哈希表组成。
  • 由链表保证元素有序。
  • 由哈希表保证元素唯一。

HashTable

• 底层数据结构是哈希表。线程安全，效率低

TreeMap

• 底层数据结构是红黑树。(是一种自平衡的二叉树)
• 如何保证元素唯一性呢? 根据比较的返回值是否是0来决定
• 如何保证元素的排序呢?
  • 自然排序(元素具备比较性) 让元素所属的类实现Comparable接口
  • 比较器排序(集合具备比较性) 让集合接收一个Comparator的实现类对象

如何选用集合

是否是键值对象形式:

• 是：Map
  • 键是否需要排序:
    • 是：TreeMap
    • 否：HashMap
    • 不知道，就使用HashMap。
• 否：Collection
  • 元素是否唯一:
    • 是：Set 元素是否需要排序？
      • 是：TreeSet
      • 否：HashSet
      • 不知道，就使用HashSet
    • 否：List 要安全吗？
      • 是：Vector
      • 否：ArrayList或者LinkedList
        • 增删多：LinkedList
        • 查询多：ArrayList
        • 不知道，就使用ArrayList
  • 不知道，就使用ArrayList

在集合中常见的数据结构

ArrayXxx:底层数据结构是数组，查询快，增删慢 LinkedXxx:底层数据结构是链表，查询慢，增删快 HashXxx:底层数据结构是哈希表。依赖两个方法：hashCode()和equals() TreeXxx:底层数据结构是二叉树。两种方式排序：自然排序和比较器排序

集合的常见方法及遍历方式

Collection

• add()
• remove()
• contains()
• iterator()
• size()
• 遍历：
  • 增强for
  • 迭代器

Map

• put()
• remove()
• containskey(),containsValue()
• keySet()
• get()
• value()
• entrySet()

• size()

• 遍历：
  • 根据键找值
  • 根据键值对对象分别找键和值