Thinking in Java——容器篇学习笔记

写在前面：
这是一篇菜鸟的学习笔记。

容器的简图

不包含抽象类和遗留构件

容器的简单分类.png

• Java 容器类类库的用途是“保存对象”。

• Java 容器类都可以自动地调整自己的尺寸。

• Java 容器可划分为两个不同的概念： Collection 与 Map。
  1.Collection里面的接口有些是可选的（为了防止接口爆炸的情况），并且未获支持的操作只有在运行时才能探测到，因此有可能调用接口时会获取到UnsupportedOperationException。

List

1.List 接口在 Collection 的基础上添加了大量的方法。

• ArrayList
  1.底层是数组

• LinkedList
  1.底层是链表
  2.各种Queue和栈的行为由LinkedList提供支持。
  3.一些方法需要注意：

// 不移除
getFirst()、element()// 返回列表的头，如果List为空抛出NoSuchElemetException。
peek() // 返回列表的头，如果List为空返回null。
// 移除
removeFirst()、remove()// 移除并返回列表的头，如果List为空抛出NoSushElementException。
poll()// 移除并返回列表的头，如果List为空返回null。

Stack

如果你只需要栈的行为，那么使用继承LinkedList就不合适了，因为这样会产生具有LinkedList的其他所有方法的类（Java1.0的设计者在创建java.util.Stack时，就犯了这个错误）。因此不使用Java原生态的Stack类，而简单封装LinkedList来实现栈即可。

public class Stack<T>{
    private LinkedList<T> storage = new LinkedList<T>();
    public void push(T v) {
        storage.addFirst(v);
    }
    public T peek() {
        return storage.getFirst();
    }
    public T pop() { 
        return storage.removeFirst();
    }
    public boolean empty() {
        return storage.isEmpty();
    }
    public String toString() {
        return storage.toString();
    }
}

Set

1.Set 具有与Collecion完全一样的接口，因此没有任何额外的功能，两者只是行为不同而已。
2.Set 不保存重复的元素。

• HashSet
  1.随机查找最快
  2.存储的顺序并无意义
  3.元素必须定义hashCode()方法

• TreeSet
  1.按照比较结果的升序保存对象
  2.底层是红-黑树
  3.元素必须实现Comparable接口

• LinkedHashSet
  1.按照被添加的顺序保存对象
  2.保留HashSet的查询速度
  3.元素必须定义hashCode()方法

注：
1.此外，你必须为散列存储和树型存储都创建一个equals()方法，因为Set容器需要通过该方法判断元素是否重复。
2.对于良好的编程风格而言，你应该在覆盖equals()方法时，总是同时覆盖hashCode()方法。

Queue

• LinkedList 提供了方法以支持队列的行为，并且它实现了Queue接口，因此LinkedList可以用作Queue的一种实现。通过将LinkedList向上转型为Queue：

Queue queue = new LinkedList();

事实上Queue接口窄化了对LinkedList的方法的访问权限以“专心”当作队列使用。

• PriorityQueue
  1.排序是通过Comparable进行控制的（添加到队列中的元素实现Comparable接口）

• 双向队列
  1.Java标准类库中没有任何显式的用于双向队列的接口。但是可以和Stack一样，通过组合LinkedList来实现一个Deque类。

Map

Map和Collection之间的唯一重叠就是Map可以使用entrySet()、values()方法来产生Collection

• HashMap
  1.提供最快的查找技术
  2.没有明显的顺序

• TreeMap
  1.按照比较结果的升序保存键
  2.唯一有subMap()方法的Map

• LinkedHashMap
  1.按照插入顺序保存键
  2.保留了HashMap的查询速度
  3.可以在构造器中设定LinkedHashMap实现最近最少使用算法，于是没有使用过得元素就会出现在队列的前面。

LinkedHashMap linkedHashMap = new LinkedHashMap(16,0.75f,true);

• WeakHashMap（弱键映射）
  1.如果映射之外没有引用指向某个“键”，则此“键”可以被垃圾收集器回收

• ConcurrentHashMap
  1.一种线程安全的Map

• IdentityHashMao
  1.使用==代替equals()对“键”进行比较的散列映射。专门解决特殊问题而设计的

注：
对Map中使用的键的要求与对Set中的元素的要求一样，都必须有一个equals()方法。如果键被用于散列还需要hashCode()，如果键被用于TreeMap，那么它必须实现Comparable。

迭代器

迭代器是一个对象，他的工作是遍历并选择序列中的对象，统一了对容器的访问方式。属于轻量级对象。

1.如果你只是向前遍历List，并不打算修改List对象本身，那么你可以使用foreach语法更简洁。
2.如果对List要执行一个remove等会影响容器元素个数的操作，则使用迭代器或者for()循环。因为使用foreach()时会出现错误。

• Iterator
  1.使用方法iterator()要去容器返回一个Iterator。
  2.使用next()获取序列中的下一个元素。
  3.使用hasNext()检查序列中是否还有元素。
  4.使用remove()将迭代器新近返回的元素删除。

• ListIterator
  1它是更加强大的IIterator，但是只能用于各种List类的访问。
  2.它可以双向移动。
  3.可以使用set()方法替换访问过得最后一个元素。
  4.hasPrevious()、privious()方法对应hasNext()、next()方法。

注：
1.Map 没有iterator()方法，但是可以通过如下方法遍历：

for(Map.Entry e: m.entrySet()){
  e.getKey();
  e.getValue();
}

Collection 与 Iterator

• 使用接口描述的一个理由是它可以使我们能够创建更通用的代码。
• 用迭代器而不是Collection来表示容器之间的共性。

但是Java中将这两种方法绑定到了一起，实现Collection就意味着需要提供iterator()方法。

设想这种情况：
如果你的类已经继承了其他的类，那么你就不再继承AbstractCollection了。在这种情况下，要实现Collection，就必须实现该接口中的所以方法。此时，继承并提供创建迭代器的能力就会显得容易得多了。

Foreach与迭代器

foreach语法主要用于数组，但是它也可以应用于任何Collection对象。之所以Collection对象能够使用于foreach，是因为Iterable接口。因此任何实现Iterable的类都可以将它用于foreach语句中。

• 不存在任何从数组到Iterator的自动转换，因此必须手工执行转换:

String[] strings;
Arrays.asList(strings);

其他一些记录

• Arrays.asList()产生的List对象会使用底层数组作为其物理实现，不能对数组尝试改变长度的操作。如果你执行的操作会修改这个List，并且你不想原来的数组被修改，那么就应该在另一个容器中创建副本。

• 打乱Collection元素顺序

Collections.shuffle(list,rand);

• 数据传输对象（或信使）写法：

// 将域定义为public、final即可
public final K key;
public final V value;

• 正确的equals()方法必须满足下列5个条件：
  1.自反性
  2.对称性
  3.传递性
  4.一致性
  5对任何不适null的x，x.equals(null)一定返回false

• hashCode生成方法：
  1.给int变量result赋予某个非零参量
  2.为对象内每个有意义的域计算出一个int散列码c
  3.合并计算得到散列吗

result = 37 * result + c;

4.返回result
5.检查hashCode()最后的生成结果
6.例如：

int result = 17;
result = 37 * result + s.hashCode();
result = 37 * result + id;
return result;