Java系列1 集合

参考：
https://www.jianshu.com/p/b79e267e2264
https://www.jianshu.com/p/b54f1df33f84 (Queue集合)

一.概要

集合简图
集合思维导图

1.Collection 接口

• 最基本的集合接口，代表一组Object。Java不提供直接继承Collection接口的类，只提供其子接口(如List、Set)的实现类。

2.List 接口

• Collection的子接口，有序集合，元素可重复或为空。常见实现类为ArrayList和LinkedList。

3.Set 接口

• 无序集合(除TreeSet)，元素不可重复。常见实现类为HashSet和TreeSet。

4.Map 接口

• 元素为键值对，其中值可以是另外一个键值对，从而可以形成多级映射，键不可重复。常见实现类为HashMap和TreeMap。

二.详述

1.List 列表 (有序/可重复)

• ArrayList
  基于数组(查询快、增删慢)
  容量自动增长
  允许空值
  线程不安全
• LinkedList
  基于双向循环链表(查询慢、增删快)
  基于链表，不存在容量不足问题
  允许空值
  线程不安全
• Vector
  基于数组，与ArrayList相似
  使用synchronized方法同步，线程安全

2.Set 集合（无序/不重复）

• HashSet
  基于HashMap
  允许空键值，但键不可重复
  线程不安全
• TreeSet(有序)
  基于TreeMap
  与HashSet类似

3.Queue/Deque

实现先进先出的集合
Queue只能队尾入队，队头出队
Deque队尾队头均能进/出队

4.Map 映射 (key不可重复)

• HashMap
  基于Hash表
  通过单链表解决冲突问题，容量自动增长
  初始容量和加载因子是影响HashMap性能的重要参数
  键和值均可为空，但键不可重复
  线程不安全
• HashTable
  与HashMap类似
  线程安全
• TreeMap(有序)
  基于红黑树
  允许空键值，但键不可重复
  线程不安全

三.补充

• 集合排序
  Comparable接口的CompareTo()方法——默认排序规则
  Comparator接口的Compare()方法——临时排序规则
• 集合迭代
  Iterator接口
• 线程安全的集合
  Vector(替代ArrayList)
  HashTable(替代HashMap)

四.相关数据结构

• 哈希表
  散列存储结构：建立元素关键码与元素存储地址的对应关系
  优点：查找速度极快 (O(1)) ，查找效率与元素个数无关
  可能产生冲突：经哈希函数变换后，不同关键码可能映射到统一哈希地址

• 双向循环链表

  
  双向循环列表

• 红黑树

  
  image.png

问君何能尔，心远地自偏