集合框架

1 Java类库 也将 接口 与实现 相分离
2 如 队列 接口 (先进先出) 有两种实现方式 ： 循环数组ArrayDeque 和 链表LinkedList
public interface Queue{}
3 一旦构建了集合就不需要知道究竟使用了哪种实现
4 如果队列的数量有上限 用循环数组效率更高， 否则 用 链表实现 效率更高
5 类库中有 类似于 AbstractQueue类，如果要自己实现Queue 扩展AbastractQueue 会更简单，因为其中定义了一些默认实现
6 java 类库中 集合的基本接口是 Collection 接口

  1. public interface Collection<E>{
  2.     boolean add(E e);   //用于在集合内添加元素
  3.     Iterator<E> iterator(); //返回迭代器，利用迭代器可以依次访问元素
  4. }
  6. public interface Iterator<E>{
  7.     E next();  //如果到达集合末尾 抛出异常
  8.     boolean hasNext();
  9.     void remove();  // 删除 上次 next 返回的值 （不能连续两次 remove  必须一次next 一次remove 才合法）
  10.     default void forEachRemaning(Consumer<? super E> action); //对迭代器的每个元素 都调用lambda表达式，
  11. }
  13. public interface Iterable<E>{
  14.     Iterator<E> iterator();
  15. }

7 迭代器循环可以简化为for each 循环，for each可以与 任何实现了Iterable接口的对象 工作 （以及数组）,由于Collection扩展了Iterable接口，所以类库中的集合都能用 for each
8 next的顺序根据集合类型不同而变化，如 ArrayList 就从0开始， hashset就以某种随机的方式遍历完所有的数据
9 由于Collection和Iterator都是泛型接口，可以编写操作任何类型集合的方法

  1. boolean isEmpty();
  2. boolean contains(object o);
  3. boolean containsAll(Collection<?> c);
  4. boolean equals(obejct o);
  5. boolean addAll(Collection<? extends E> from);
  6. boolean remove(Object o);
  7. boolean removeAll(Collection<?> c);
  8. void clear();
  9. boolean retainall(Collection<?> c);
  10. Object[] toArray();
  11. <T> T toArray(T[] arrayToFill);

同理 有 AbstractCollection抽象类 提供部分默认的实现
10 Java集合框架中定义了 大量的接口
image.png
对于Map接口而言，由于映射包含 键/值对 增删元素略有不同

  1. V put(K key,V value);
  2. V get(K key);

11 List 是一个有序的集合，有序指的是 先插入的在前面， 后插入的 在后面 TreeSet TreeMap 有序 而hashSet hashMap则序
12 List除了迭代器外 还能通过 add(index, e) remove(index), get(index) 和 set(index,e) 进行随机访问，不过ArrayList随机访问快，而LinkedList 很慢
13 Set集合 等同于Collection 不过为了突出集的概念，更严格，不允许添加重复元素，定义集的equals方法（不要求对应位置相等）
14 NavigableSet和NavigableMap接口 包含了一些 搜索 和遍历 有序集和映射的方法，TreeSet 和 TreeMap实现了这些接口

具体的集合

1 ArrayList在中间增删元素消耗很大，LinkedList就可以解决这个问题，Java中所有的链表都是 双向 链表
2 对于List而言，可以通过迭代器 ListIterator 在 集合中间增删改查元素

  1. interface ListIterator<E> extends Iteraor<E>{
  2.     void add(E e);  //在迭代器当前位置 插入 一个对象
  3.     void remove();
  4.     void set(E e);
  5.     E previous();
  6.     boolean hasPrevious();
  7. }

3 ArrayList封装了一个动态再分配的对象数组。如果要使用线程安全的可以使用Vector对象
4 散列表 可以快速地查找所需要的对象，缺点在于无法确定元素插入的顺序
只需要计算元素的hashCode 并分配到不同的桶中，冲突了就用链表，标准库默认初始桶为16个，可以在创建的时候指定初始容量，插入过程中如果百分之75的桶有元素 就会重hash，桶数翻倍
5 HashSet 就是利用了 散列表， 插入前先查找是否已存在，可以通过散列进行快速的查找
6 TreeSet是一个有序集合，在对集合进行遍历时，每个值将自动地按照排序后的顺序呈现 ，其底层是 红黑树
7 TreeSet检查已存在的对象 的时间复杂度为 log n ，比散列慢
8 Deque接口用于 实现双端 队列，并有 ArrayDeque 和 LinkedList 实现
9 优先级队列中的元素可以按照任意顺序插入，然后总能将优先级最小的置于队列顶部，其顶层用了 堆来实现 可以让最小的元素移动到根
PrioriyQueue 是一个类，扩展了AbstractQueue，简介实现了Queue的接口.

映射

1 映射有两个通用的实现 TreeMap 和 HashMap，散列更快，如果不要求按顺序，就用散列
2 get方法可能会返回null， 用 getOrDefault方法更合适
3 Map对象 有一个 ForEach 方法，接收一个lambda， 每一项会依次调用
4 可以通过remove(key) 删除Map 的元素，用put方法 插入或者更新key对应的value
5 集合框架 不认为map 本身是一个集合，可以通过map得到map的 视图 ，视图是实现了Collection的集合，所以可以用 for each 循环（直接用map的 forEach方法更方便）
如 map.keySet() 返回 Set
map.values() 返回 Collection
map.entrySet() 返回 Set>
在上述视图中 可以删除 但不能增加
6 WeakHashMap 由于解决 如果键的对象 只有一个来自散列表的 引用时 就将其回收
7 LinkedHashSet和LinkedHashMap类用来记住插入元素项的顺序，在表中的同时 用双向链表 按最近访问的顺序 连接， 访问顺序对于实现高速缓存的“最近最少使用”原则十分重要
8 EnumSet是一个枚举类型元素集的高效实现
9 EnumMap是一个键类型为枚举类型的映射
10 IdentityHashMap有特殊的作用 ，不用hashCode来区分对象是否相同 而直接用 == 所以如果地址不同，即使内容相同，也被视为不同的对象

视图和包装器

1 通过视图技术 可以 修改原来的集合状态
2 Arrays的静态asList 方法就返回了 包装了普通Java数组的 List 包装器
返回的对象并不是 ArrayList 而是一个视图对象， 该对象 带有访问 底层数组的 get 和 set方法，改变大小的方法会抛出异常
asList 方法 可以接收 可变数目的 参数

算法

1 泛型集合接口有一个很大的优点，即算法只需要实现一次
2 Collection.sort(staff) 可以实现对List接口的排序，并且可以传递一个comparator对象
或者 list 对象 调用sort 方法即可
对list排序 的过程 ：直接将所有元素转入一个数组，对数组进行排序，然后，再将排序后的序列复制回列表 （用的是归并排序，虽然较快排 慢 ，但是属于稳定排序）
要求传入的list 必须是 可修改的 不必是 可改变大小的， 所以视图的list也可以进行排序
（能set 就是 可修改， 能add 或remove 就是可改变大小）
treeSet自动排序，hashSet不需要排序
3 Collections.shuffle(staff) 会随机打乱List
4 Collections.binarySearch（） 可以实现二分查找，必须是 排序的 List
5 Collections还有一些简单的算法，如 min max 等
6 集合转为 数组， 可以用 toArray() 但会变成 Object[] 且不能类型转换
所以可以使用toArray的变体 toArray(new String[]) 用来保存对象
7 数组变为集合 可以 使用asList 作为包装器类，注意 不能add

遗留集合

1 Hashtable 线程安全的 ，但一般用ConcurrentHashMap
2 Enumeration，很少用
3 属性映射 Property map
键 值 都是字符串
可以保存到文件，也可以从文件读取
API
Properties()
String getPropertity(String key)
void load(Inpustream in)
4 Stack扩展自 Vector
API
push / pop /peek
5 BieSet 位集 用于存储一个位序列
API
get(i) set(i) clear(i)