框架
概述
如果一个程序只包含固定数量且生命期都是已知的对象，那么这是一个非常简单的程序
通常程序总是根据运行时才知道的某些条件去创建新对象，对象的类型、数量并不能提前确定，就不能依靠创建命名的引用来持有每一个对象：MyType aReference;

java有多种方式保存对象（的引用）
数组是保存一组对象的最有效的方式，但太受限于尺寸固定

所以，容器类 登场。用途：保存对象。
容器提供了完善的方法来保存对象，可以解决数量惊人的问题
可以显著增强你的编程能力

本章聚焦于你在日复一日的编程工作中将会用到的那些容器

分类（接口）
将容器类划分为两个不同的概念：
Collection：单列，不同子接口有不同规则
List：按照插入顺序保存
Set：不能有重复元素
Queue：按照排队规则来确定对象产生的顺序
（通常与他们被插入的顺序相同）
只允许在一端插入对象，从另一端移除对象？？

Map：双列，“映射表”，“关联数组”，“字典”（但key和value成对出现，key不能重复，value可以）
允许我们使用一个对象（key）来查找另一个对象（value）
（像在使用数组下标；所以key不能重复）
（就像一个简单的数据库）
(数据结构仅作用于key)
重新理解V put(K key, V value)方法：
增加一个值（你想要增加的对象）
并将它与某个键（你用来查找这个值的对象）关联起来
（这个键之前可能存在或者不存在）
是强大的编程工具

（理想情况下，我们大部分代码都是在与这些接口打交道）
会这样写：List<Apple> apples = new ArrayList<Apple>();
在其余代码中都使用这个接口
目的在于如果你决定去修改你的实现，只需要在创建处修改一下
（不能使用ArrayList的特有方法）

Set
与Collection拥有完全一样的接口
Set就是Collection,只是行为不同??
(接口继承接口, 还不扩充接口, 两个接口就是一样的内容)

特点是元素不重复
(可以用来去重)(非常有用的功能)

最常被使用的是测试归属性
(某对象是否存在于其中)
(是基于对象的值来确定归属性的??)
(因为它能去重,去重后总量变少,适于测试归属性??)
(如何判断元素相同??)

所以查找是Set中最重要的操作
(测试归属性依靠查找操作)
contains()  containsAll()等继承自Collection的方法

因此你通常会选择一个HashSet的实现
(因它专门为快速查找进行了优化)
(TreeSet有序; LinkedHashSet有序 且 查找快)

Map
“将对象映射到其他对象的能力是一种解决编程问题的杀手锏”
V get(Object key)
返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null
(也有可能是: 值就为null)
(区分这个null代表什么, 可以用下面的containsKe方法测试)

boolean containsKey(Object key)
如果此映射包含指定键的映射关系，则返回 true。
boolean containsValue(Object value)
如果此映射将一个或多个键映射到指定值，则返回 true。

Map可以返回:
它的键的Set
Set<K> keySet()
它的值的Collection
Collection<V> values()
它的键值对的Set
Set<Map.Entry<K,V>> entrySet()

和其他Collection一样, 可以很容易地扩展到多维
只需将其值设置为(其他容器, 甚至是其他Map)
容器组合起来, 生成强大的数据结构-------------->数据结构??
(例如: Map<Person, List<Pet>>)

Queue
典型的先进先出(FIFO)的容器
从容器的一端放入事物, 从另一端取出
(是一种可靠的将对象从程序的某个区域传输到另一个区域的途径)
(在并发编程中特别重要, 将对象从一个任务传输给另一个任务??)

linkedList实现了Queue接口, 可以用作Queue的一种实现
Queue<Integer> q = new LinkedList<Integer>();
q.offer(); 加到队尾
q.peek();和elemen() 返回头部元素, 但不移除
q.pull();和q.remove(); 返回头部元素并移除它
(上述方法都是Queue接口自己定义的, 提供了完整独立的队列功能)

队列规则:
规定了队列中哪一个元素是下一个弹出队列的元素

先进先出规则:
下一个弹出队列的元素是队列中”资历”最深的那个

优先级队列的规则:
下一个弹出的元素是最需要的那个

PriorityQueue优先队列
用offer插入一个对象时, 这个对象会在队列中被排序(默认自然顺序)
(维护一个堆)(堆和队列??)
(也可以有其他实现: 在获取时选择最重要的)
确保调用peek, poll, remove时, 获取的元素是队列中优先级最高的元素

可以提供自己的Comparator对象(比较器)来改变排序
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器对元素进行排序
static <T> Comparator<T> reverseOrder()
返回一个比较器
它的比较方式是逆转对象在中collection 的自然顺序
自然顺序是通过对象自身的 compareTo 方法强行排序的
(对象要实现Comparable接口)

实现Comparable接口的类, 对象之间可以相互比较, 就能排序
(该类对象能放到自然顺序队列中??, 其他对象不行)

实现Comparator接口的类
重写int compare(T o1, T o2)
其对象能比较两个参数的”大小”, 是比较器

Collection
描述所有序列容器共性的根接口
可能会被认为是一个”附属接口”
(因为要表示其他若干接口的共性而出现的接口)

C++中容器没有公共基类
容器之间的所有共性都是通过迭代器达成的??
(迭代器统一了对容器的访问方式)
(所以它本身就表达着容器的共性)
java用Collection接口描述容器共性
也利用了这一点
因为实现Collection接口, 必须实现其iterator()方法
(其他抽象方法, 就是其他共性, 是补充??)

假设有一个方法(功能是展示集合元素)的参数是Collection接口对象
另一个重载版本的参数是迭代器对象
(传一个集合对象或者该对象的迭代器进去, 都能遍历它)
该方法是针对所有集合的共性来编写代码
(Collection接口和迭代器都体现了共性)
(都可以将该方法与底层容器的特定实现解耦)

自定义一个”集合类”
(就要获取集合类的共性)
(两种方法)
可以通过实现Collection接口(或继承抽象类AbstractCollection)
(前者意味着要实现所有抽象方法, 不管是否需要)
(后者也要强制实现其中的抽象方法iterator()和size(),AbstractCollection中的其他方法会用到)
可以在类中写一个方法, 返回遍历自己元素的迭代器对象
(这种方法更灵活, 限制较少)
(是耦合度最小的方式)
(前提是类中持有很多对象, 这是集合的功能)
(可以让一个数组成员对象来实现)

AbstractCollection类(抽象类)提供了Collection的默认实现
(我们使用的Collection实现类多是继承, 或间接继承自AbstractCollection??)
(我们自定义”集合类”时, 可以继承AbstractCollection, 就不必自己写实现了)
底层不同实现方式
ArrayList 易查询
LinkedList 易增删，包含的操作也更多？？

HashSet 实现了最快获取元素
(存储方式: 散列函数)
TreeSet 按照比较结果升序保存
(存储方式: 红-黑树数据结构)
LinkedHashSet 按照被添加的顺序保存，（保留了HashSet的查询速度）
(也使用了散列; 用链表来维护元素的插入顺序)
（通常只关心某事物是否是一个set的成员，不关心它出现的顺序）

（同上）
HashMap
(通过散列码为key排序)
TreeMap
LinkedHashMap
(通过链表, 维护key的顺序: 按照添加顺序保存)
总结
类型
数组保存类型明确(包括基本类型)的对象
集合可以通过指定泛型来明确类型,不能放基本类型,但可以放包装类对象

容量
数组容量不可变
集合可变

索引
数组和List是数字索引
Map是”对象”索引

顺序
数组, List, LinkedHashMap/Set----->插入顺序
TreeMap/Set----->升序排列

去重
Set

访问
ArrayList快(常用)
HashMap/Set最快

增删
LinkdedList快

LinkedList支持栈和队列的行为

容器可以是多维的(容器里面装容器)

新程序中避免使用过时的Vector, Hashtable和Stack

容器只有4种: List, Set, Map, Queue. 各有两三个实现版本

Collection
|
|---------------------->List----------->ArrayList
|                                |
|------>Queue--------|--------->LinkedList
|                |
|                |----------->PriorityQueue
|
|--------->Set------>HashSet------>LinkedHashSet
                        |
|-------->TreeSet

Map-------->HashMap------>LinkedHashMap
  |
  |----------->TreeMap
迭代器
复习迭代器模式:
内部类实现迭代器接口
定义了迭代外部类元素的方式
一个方法返回内部类对象(迭代器)

迭代器接口:
Iterator接口
ListIterator接口(继承自Iterator)

Collection接口有Iterator()方法
List接口有ListIterator()方法

迭代器对象的工作是遍历并选择序列中的对象, 客户端程序员不必关心该序列底层的结构
(迭代器有办法, 一个迭代器和产生它的那个序列是一对一关联的)
从而可以办到”接受对象容器,并传递它,然后在每个对象上都执行操作”
(得到容器,不知道容器类型,不知道元素个数,都能操作其中对象)
“迭代器统一了对容器的访问方式”
序列指Collection??
(前文:Collection接口概括了序列的概念---一种存放一组对象的方式)

迭代器通常被称为”轻量级对象”(创建它的代价小??),
因此对迭代器功能有些限制:
Iterator只能单向移动(游标)
方法:
向后遍历:
next()
hasNext()
remove()
删除元素:
remove()

ListIterator 可以双向移动
增加了方法:(执行时也是根据游标位置操作的)
向前遍历:
previous()
hasPrevious()
得到索引:
nextIndex()
previousIndex()
添加元素
add(新元素)
替换元素:
set(新元素)

Tips：
1
把ArrayList当做“可以自动扩充自身尺寸的数组”
（下面有反例- -）
2注解
@开头，可以接收参数
例如：@SuppressWarnings(“unchecked”)
表示：只有有关“不受检查的异常”的警告信息应该被抑制
class Apple {
        private static long counter;
        private final long id = counter++;

        public long id() {
                return id;
        }
}

class Orange {
}

public class ApplesAndOrangesWithoutGenerics {
//注解在这里
//如果不写会给一个警告：ApplesAndOrangesWithoutGenerics.java使用了未经检查或不安全的操作，但仍可以编译通过
        @SuppressWarnings("unchecked")
        public static void main(String[] args) {
                ArrayList apples = new ArrayList();
                for (int i = 0; i < 3; i++)
                        apples.add(new Apple());//不加元素的话，不给警告
                apples.add(new Orange());
                for (int i = 0; i < apples.size(); i++)
                        ((Apple) apples.get(i)).id();//运行时这句会报异常：ClassCastException(RuntimeException)
                // Orange is detected only at run time//RTTI
//如果使用泛型，加入Orange元素就无法通过编译（提示“找不到合适的方法”，是逻辑错误，不是异常）；这里不使用泛型，到运行时才报异常
        }
}

框架
概述
如果一个程序只包含固定数量且生命期都是已知的对象，那么这是一个非常简单的程序
通常程序总是根据运行时才知道的某些条件去创建新对象，对象的类型、数量并不能提前确定，就不能依靠创建命名的引用来持有每一个对象：MyType aReference;

java有多种方式保存对象（的引用）
数组是保存一组对象的最有效的方式，但太受限于尺寸固定

所以，容器类 登场。用途：保存对象。
容器提供了完善的方法来保存对象，可以解决数量惊人的问题
可以显著增强你的编程能力

本章聚焦于你在日复一日的编程工作中将会用到的那些容器

分类（接口）
将容器类划分为两个不同的概念：
Collection：单列，不同子接口有不同规则
List：按照插入顺序保存
Set：不能有重复元素
Queue：按照排队规则来确定对象产生的顺序
（通常与他们被插入的顺序相同）
只允许在一端插入对象，从另一端移除对象？？

Map：双列，“映射表”，“关联数组”，“字典”（但key和value成对出现，key不能重复，value可以）
允许我们使用一个对象（key）来查找另一个对象（value）
（像在使用数组下标；所以key不能重复）
（就像一个简单的数据库）
(数据结构仅作用于key)
重新理解V put(K key, V value)方法：
增加一个值（你想要增加的对象）
并将它与某个键（你用来查找这个值的对象）关联起来
（这个键之前可能存在或者不存在）
是强大的编程工具

（理想情况下，我们大部分代码都是在与这些接口打交道）
会这样写：List<Apple> apples = new ArrayList<Apple>();
在其余代码中都使用这个接口
目的在于如果你决定去修改你的实现，只需要在创建处修改一下
（不能使用ArrayList的特有方法）

Set
与Collection拥有完全一样的接口
Set就是Collection,只是行为不同??
(接口继承接口, 还不扩充接口, 两个接口就是一样的内容)

特点是元素不重复
(可以用来去重)(非常有用的功能)

最常被使用的是测试归属性
(某对象是否存在于其中)
(是基于对象的值来确定归属性的??)
(因为它能去重,去重后总量变少,适于测试归属性??)
(如何判断元素相同??)

所以查找是Set中最重要的操作
(测试归属性依靠查找操作)
contains()  containsAll()等继承自Collection的方法

因此你通常会选择一个HashSet的实现
(因它专门为快速查找进行了优化)
(TreeSet有序; LinkedHashSet有序 且 查找快)

Map
“将对象映射到其他对象的能力是一种解决编程问题的杀手锏”
V get(Object key)
返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null
(也有可能是: 值就为null)
(区分这个null代表什么, 可以用下面的containsKe方法测试)

boolean containsKey(Object key)
如果此映射包含指定键的映射关系，则返回 true。
boolean containsValue(Object value)
如果此映射将一个或多个键映射到指定值，则返回 true。

Map可以返回:
它的键的Set
Set<K> keySet()
它的值的Collection
Collection<V> values()
它的键值对的Set
Set<Map.Entry<K,V>> entrySet()

和其他Collection一样, 可以很容易地扩展到多维
只需将其值设置为(其他容器, 甚至是其他Map)
容器组合起来, 生成强大的数据结构-------------->数据结构??
(例如: Map<Person, List<Pet>>)

Queue
典型的先进先出(FIFO)的容器
从容器的一端放入事物, 从另一端取出
(是一种可靠的将对象从程序的某个区域传输到另一个区域的途径)
(在并发编程中特别重要, 将对象从一个任务传输给另一个任务??)

linkedList实现了Queue接口, 可以用作Queue的一种实现
Queue<Integer> q = new LinkedList<Integer>();
q.offer(); 加到队尾
q.peek();和elemen() 返回头部元素, 但不移除
q.pull();和q.remove(); 返回头部元素并移除它
(上述方法都是Queue接口自己定义的, 提供了完整独立的队列功能)

队列规则:
规定了队列中哪一个元素是下一个弹出队列的元素

先进先出规则:
下一个弹出队列的元素是队列中”资历”最深的那个

优先级队列的规则:
下一个弹出的元素是最需要的那个

PriorityQueue优先队列
用offer插入一个对象时, 这个对象会在队列中被排序(默认自然顺序)
(维护一个堆)(堆和队列??)
(也可以有其他实现: 在获取时选择最重要的)
确保调用peek, poll, remove时, 获取的元素是队列中优先级最高的元素

可以提供自己的Comparator对象(比较器)来改变排序
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器对元素进行排序
static <T> Comparator<T> reverseOrder()
返回一个比较器
它的比较方式是逆转对象在中collection 的自然顺序
自然顺序是通过对象自身的 compareTo 方法强行排序的
(对象要实现Comparable接口)

实现Comparable接口的类, 对象之间可以相互比较, 就能排序
(该类对象能放到自然顺序队列中??, 其他对象不行)

实现Comparator接口的类
重写int compare(T o1, T o2)
其对象能比较两个参数的”大小”, 是比较器

Collection
描述所有序列容器共性的根接口
可能会被认为是一个”附属接口”
(因为要表示其他若干接口的共性而出现的接口)

C++中容器没有公共基类
容器之间的所有共性都是通过迭代器达成的??
(迭代器统一了对容器的访问方式)
(所以它本身就表达着容器的共性)
java用Collection接口描述容器共性
也利用了这一点
因为实现Collection接口, 必须实现其iterator()方法
(其他抽象方法, 就是其他共性, 是补充??)

假设有一个方法(功能是展示集合元素)的参数是Collection接口对象
另一个重载版本的参数是迭代器对象
(传一个集合对象或者该对象的迭代器进去, 都能遍历它)
该方法是针对所有集合的共性来编写代码
(Collection接口和迭代器都体现了共性)
(都可以将该方法与底层容器的特定实现解耦)

自定义一个”集合类”
(就要获取集合类的共性)
(两种方法)
可以通过实现Collection接口(或继承抽象类AbstractCollection)
(前者意味着要实现所有抽象方法, 不管是否需要)
(后者也要强制实现其中的抽象方法iterator()和size(),AbstractCollection中的其他方法会用到)
可以在类中写一个方法, 返回遍历自己元素的迭代器对象
(这种方法更灵活, 限制较少)
(是耦合度最小的方式)
(前提是类中持有很多对象, 这是集合的功能)
(可以让一个数组成员对象来实现)

AbstractCollection类(抽象类)提供了Collection的默认实现
(我们使用的Collection实现类多是继承, 或间接继承自AbstractCollection??)
(我们自定义”集合类”时, 可以继承AbstractCollection, 就不必自己写实现了)
底层不同实现方式
ArrayList 易查询
LinkedList 易增删，包含的操作也更多？？

HashSet 实现了最快获取元素
(存储方式: 散列函数)
TreeSet 按照比较结果升序保存
(存储方式: 红-黑树数据结构)
LinkedHashSet 按照被添加的顺序保存，（保留了HashSet的查询速度）
(也使用了散列; 用链表来维护元素的插入顺序)
（通常只关心某事物是否是一个set的成员，不关心它出现的顺序）

（同上）
HashMap
(通过散列码为key排序)
TreeMap
LinkedHashMap
(通过链表, 维护key的顺序: 按照添加顺序保存)
总结
类型
数组保存类型明确(包括基本类型)的对象
集合可以通过指定泛型来明确类型,不能放基本类型,但可以放包装类对象

容量
数组容量不可变
集合可变

索引
数组和List是数字索引
Map是”对象”索引

顺序
数组, List, LinkedHashMap/Set----->插入顺序
TreeMap/Set----->升序排列

去重
Set

访问
ArrayList快(常用)
HashMap/Set最快

增删
LinkdedList快

LinkedList支持栈和队列的行为

容器可以是多维的(容器里面装容器)

新程序中避免使用过时的Vector, Hashtable和Stack

容器只有4种: List, Set, Map, Queue. 各有两三个实现版本

Collection
|
|---------------------->List----------->ArrayList
|                                |
|------>Queue--------|--------->LinkedList
|                |
|                |----------->PriorityQueue
|
|--------->Set------>HashSet------>LinkedHashSet
                        |
|-------->TreeSet

Map-------->HashMap------>LinkedHashMap
  |
  |----------->TreeMap
迭代器
复习迭代器模式:
内部类实现迭代器接口
定义了迭代外部类元素的方式
一个方法返回内部类对象(迭代器)

迭代器接口:
Iterator接口
ListIterator接口(继承自Iterator)

Collection接口有Iterator()方法
List接口有ListIterator()方法

迭代器对象的工作是遍历并选择序列中的对象, 客户端程序员不必关心该序列底层的结构
(迭代器有办法, 一个迭代器和产生它的那个序列是一对一关联的)
从而可以办到”接受对象容器,并传递它,然后在每个对象上都执行操作”
(得到容器,不知道容器类型,不知道元素个数,都能操作其中对象)
“迭代器统一了对容器的访问方式”
序列指Collection??
(前文:Collection接口概括了序列的概念---一种存放一组对象的方式)

迭代器通常被称为”轻量级对象”(创建它的代价小??),
因此对迭代器功能有些限制:
Iterator只能单向移动(游标)
方法:
向后遍历:
next()
hasNext()
remove()
删除元素:
remove()

ListIterator 可以双向移动
增加了方法:(执行时也是根据游标位置操作的)
向前遍历:
previous()
hasPrevious()
得到索引:
nextIndex()
previousIndex()
添加元素
add(新元素)
替换元素:
set(新元素)

Tips：
1
把ArrayList当做“可以自动扩充自身尺寸的数组”
（下面有反例- -）
2注解
@开头，可以接收参数
例如：@SuppressWarnings(“unchecked”)
表示：只有有关“不受检查的异常”的警告信息应该被抑制
class Apple {
        private static long counter;
        private final long id = counter++;

        public long id() {
                return id;
        }
}

class Orange {
}

public class ApplesAndOrangesWithoutGenerics {
//注解在这里
//如果不写会给一个警告：ApplesAndOrangesWithoutGenerics.java使用了未经检查或不安全的操作，但仍可以编译通过
        @SuppressWarnings("unchecked")
        public static void main(String[] args) {
                ArrayList apples = new ArrayList();
                for (int i = 0; i < 3; i++)
                        apples.add(new Apple());//不加元素的话，不给警告
                apples.add(new Orange());
                for (int i = 0; i < apples.size(); i++)
                        ((Apple) apples.get(i)).id();//运行时这句会报异常：ClassCastException(RuntimeException)
                // Orange is detected only at run time//RTTI
//如果使用泛型，加入Orange元素就无法通过编译（提示“找不到合适的方法”，是逻辑错误，不是异常）；这里不使用泛型，到运行时才报异常
        }
}