集合框架 Collections Framework

集合框架，是用于表示和操作集合的体系结构，集合框架应包含：

• 接口(Interfaces)：表示集合的抽象数据类型。使用接口，允许集合独立于其表示的细节进行操作
• 实现(Implementations)：集合接口的具体实现，包含可重用的数据结构
• 算法(Algorithms)：对集合执行搜索/排序等操作，是可重用的功能

即，Java提供了一套包含，多种集合类型，多种数据结构实现，以及操作处理算法的集合框架。是典型的面向接口编程的体现。

Interfaces

1. Iterable

• java.lang.Iterable< T >
• Iterable接口。实现了此接口类的对象，支持ForEach循环语句
• Java8后，添加基于函数式编程的forEach()方法
• Iterable接口不属于Java集合框架

以及多种不同数据结构的实现类

2. The Collection Interface

2.1 The Collection Interface

• java.util.Collection< E >
• 一个集合，表示一组被称为元素的对象
• Collection接口。用于描述，最具通用性的集合。因此，也包含了最具通用性的集合操作方法
• Collection接口继承自Iterable接口。即，所有集合类型均支持foreach循环语句

1. boolean add(E e)，向集合添加元素。如调用更改了集合返回true，下同
2. boolean addAll(Collection<? extends E> c)，向集合添加一个集合
3. boolean remove(Object o)，从集合移除中指定元素
4. boolean removeAll(Collection<? extends E> c)，从集合移除包含指定集合
5. void clear()，移除集合全部元素
6. boolean contains(Object o)，判断集合是否包含指定元素
7. boolean containsAll(Collection<? extends E> c)，判断是否包含包含指定集合
8. boolean isEmpty()，判断集合是否包含元素
9. int size() ，集合长度
10. T[] toArray(T[] a)，将集合转为指定类型的数组
11. Iterator iterator()，获取迭代器
    ……

2.2 The List Interface

2.2.1 The List Interface

• java.util.List< E >
• List集合。有序的，允许包含重复元素的集合。除从Collection继承的方法外，提供基于位置索引的操作方法

1. void add(int index, E element)，将指定位置元素后移，添加
2. E set(int index, E element)，替换
3. E get(int index)，获取
4. E remove(int index)，移除
   ……

• List集合接口基本实现类，即不同的数据结构

5. java.util.ArrayList< E >类，基于对象数组数据结构的实现
6. java.util.LinkedList< E >类，基于双向链表数据结构的实现

• ArrayList，可快速基于索引访问元素对象；其底层使用Arrays.copyOf()方法实现对象数组的增删，性能损失较小

• LinkedList，当需要极其频繁的在集合头部添加元素时，效率较高。但需要为每一个元素创建两个节点对象，基于索引位置的访问需要线性时间(Positional access requires linear-time)，整体性能开销较大

• 绝大多数情况下，使用ArrayList，或不可变集合(后期讨论)即可

2.2.2 ArrayList构造函数

• ArrayList()，创建空List集合。默认创建0个元素的对象数组
• ArrayList(int initialCapacity)，基于指定长度创建List集合。长度仅初始化集合时使用，后期添加/移除自动容量
• ArrayList(Collection<? extends E> c)，基于指定集合创建List集合

2.2.2 LinkList构造函数

• 基于LinkedList双向链表数据结构的实现
• 会为每个元素创建2个节点，保存前/后元素的地址
  

2.3 The Set Interface

• java.util.Set
• Set集合，不包含重复元素(数学中集合的抽象)
• Set接口，只包含继承自Collection方法，并添加禁止重复元素的限制
• 基本实现类

1. java.util.HashSet，元素无序(底层基于HashMap确定元素是否重复)
2. java.util.LinkedHashSet，元素有序
3. java.util.TreeSet ，元素有序

• 无论使用有序/无序实现，均无基于索引的操作方法

2.4 Iterators

• java.util.Iterator< E >
• Iterator接口。迭代器，允许遍历集合，并根据需求选择性地从集合中移除元素
• 不同的集合类型，的不同数据结构的实现类，有不同的迭代器实现，但仅需面向Iterator接口完成遍历与移除
• Iterator< E > iterator()方法，Collection接口方法，获取集合对象的迭代器
• Iterator通过移动游标遍历集合。初始时，游标位于第一个元素前

1. boolean hasNext()， Iterator中是否有下一个元素
2. E next()，向后移动游标，同时返回游标指向的元素
3. void remove()，从基础集合移除当前游标指向的元素

3. The Map Interface

• java.util.Map<K,V>
• A Map is not a true Collection
  
• Map，用于存放键值对(key-value)
• Map不是集合
• 通过key值 ，保存其对应的value值
• 通过Key值获取对其对应的value值操作。
• Map中key必须是唯一的，且每个key只能对应一个value，但不同key，可以对应同一个value
• 添加key-value时，如果key已经存在，则后一个覆盖前一个
• 通过key的hash值，判断key是否相同*
• 支持以基本数据类型为key/value；支持以任何类型对象为key/value
• 基本实现类

1. java.util.HashMap<K, V>，查询效率与内存占用最平衡，非线程安全
2. java.util.TreeMap <K, V>/HashTable<K, V>

• 常用操作方法

1. V put(K key, V value)，保存键值对
2. V get(K key)，基于key获取对应的value，如果value不存在，返回null
3. default V getOrDefault(Object key, V defaultValue)，获取对应的value，没有则使用默认值
4. V remove(Object key)
5. boolean containsKey(Object key)
6. boolean containsValue(Object value)
7. int size()
8. boolean isEmpty()
9. putAll()/clear()
   ………

• Map没有，基于index索引的操作
• Map没有，继承Iterable接口，不支持foreach语句遍历*

3.1 HashMap

判断key相同的方法：hashcode/equals

• 基于hashCode()方法获计算key的hash值
• 创建Node数组，基于加载因子扩容，平衡内存占用与执行效率
• 创建Node对象，基于key的hash值+算法，计算Node对象在数组中的索引。Node对象中，封装Key/value对象，相同位置以及存在Node对象
• 减少数量小于等于6个，基于单向链表保存
• 增加数量大于等于8个，基于红黑树保存
• 数量改变时，转换数据结构
• 获取时，基于key的hash值+算法，直接在Node数组获取对应的Node对象，基于具体数据结构(单向链表/红黑树)进一步获取value对象

示例代码

https://github.com/bwhyman/java-course/tree/master/java-examples