1、完整的容器分类法

容器关系

2、填充容器

• Collections.fill()
• Map.Entry对象之存储了它的索引而不是实际键和值。

3、Collection的功能方法

Collection的功能方法

4、可选操作

• Arrays.asList()会生成一个List，它基于一个固定大小的数，仅支持哪些不会改变数组大小的操作。
• 应该把Arrays.asList()结果作为构造器的参数传递给任何Collection，这样可以生成允许使用所有方法的普通容器。

5、Set和存储顺序

Set

• 对于没有重新定义hashCode()方法的setType或TreeType，如果将它们放置到任何散列实现中都会产生重复值。

SortedSet

• 可以保证元素处于排序状态

6、队列

优先队列

• 默认是小顶堆
• 但可以自己实现Comparable

class ToDoList extends PriorityQueue<ToDoList.ToDoItem> {
  static class ToDoItem implements Comparable<ToDoItem> {
    private char primary;
    private int secondary;
    private String item;
    public ToDoItem(String td, char pri, int sec) {
      primary = pri;
      secondary = sec;
      item = td;
    }
    public int compareTo(ToDoItem arg) {
      if(primary > arg.primary)
        return +1;
      if(primary == arg.primary)
        if(secondary > arg.secondary)
          return +1;
        else if(secondary == arg.secondary)
          return 0;
      return -1;
    }
    public String toString() {
      return Character.toString(primary) +
        secondary + ": " + item;
    }
  }
  public void add(String td, char pri, int sec) {
    super.add(new ToDoItem(td, pri, sec));
  }
  public static void main(String[] args) {
    ToDoList toDoList = new ToDoList();
    toDoList.add("Empty trash", 'C', 4);
    toDoList.add("Feed dog", 'A', 2);
    toDoList.add("Feed bird", 'B', 7);
    toDoList.add("Mow lawn", 'C', 3);
    toDoList.add("Water lawn", 'A', 1);
    toDoList.add("Feed cat", 'B', 1);
    while(!toDoList.isEmpty())
      System.out.println(toDoList.remove());
  }
} /* Output:
A1: Water lawn
A2: Feed dog
B1: Feed cat
B7: Feed bird
C3: Mow lawn
C4: Empty trash
*///:~

双向队列

• 在LinkedList中包含支持双向队列的方法。

public class Deque<T> {
  private LinkedList<T> deque = new LinkedList<T>();
  public void addFirst(T e) { deque.addFirst(e); }
  public void addLast(T e) { deque.addLast(e); }
  public T getFirst() { return deque.getFirst(); }
  public T getLast() { return deque.getLast(); }
  public T removeFirst() { return deque.removeFirst(); }
  public T removeLast() { return deque.removeLast(); }
  public int size() { return deque.size(); }
  public String toString() { return deque.toString(); }
  // And other methods as necessary...
} ///:~

7、理解Map

• 一个简单的模仿实现

public class AssociativeArray<K,V> {
  private Object[][] pairs;
  private int index;
  public AssociativeArray(int length) {
    pairs = new Object[length][2];
  }
  public void put(K key, V value) {
    if(index >= pairs.length)
      throw new ArrayIndexOutOfBoundsException();
    pairs[index++] = new Object[]{ key, value };
  }
  @SuppressWarnings("unchecked")
  public V get(K key) {
    for(int i = 0; i < index; i++)
      if(key.equals(pairs[i][0]))
        return (V)pairs[i][1];
    return null; // Did not find key
  }
  public String toString() {
    StringBuilder result = new StringBuilder();
    for(int i = 0; i < index; i++) {
      result.append(pairs[i][0].toString());
      result.append(" : ");
      result.append(pairs[i][1].toString());
      if(i < index - 1)
        result.append("\n");
    }
    return result.toString();
  }
  public static void main(String[] args) {
    AssociativeArray<String,String> map =
      new AssociativeArray<String,String>(6);
    map.put("sky", "blue");
    map.put("grass", "green");
    map.put("ocean", "dancing");
    map.put("tree", "tall");
    map.put("earth", "brown");
    map.put("sun", "warm");
    try {
      map.put("extra", "object"); // Past the end
    } catch(ArrayIndexOutOfBoundsException e) {
      print("Too many objects!");
    }
    print(map);
    print(map.get("ocean"));
  }
} /* Output:
Too many objects!
sky : blue
grass : green
ocean : dancing
tree : tall
earth : brown
sun : warm
dancing
*///:~

性能

• 当在get中使用线性搜索时，执行速度会很慢。
• HashMap使用了散列码来取代对键的缓慢搜索。散列码是相对唯一的，用以代表对象的int值。

各种map

SortedMap

• 确保键处于排序状态

LinkedHashMap

• 在遍历键值对时，以元素的插入顺序返回键值对。
• 可以在构造器中设定LinkedHashMap，使之采用基于最近最少使用算法，没被访问的元素就会出现在队列前面。

8、散列与散列码

理解hashCode()

• 如果不正确地覆盖hashCode()和equals，那么使用散列的数据结构就无法正确处理你的键。
• 散列的目的是用一个对象来查找另一个对象。
• Map.EntrySet()必须产生一个Map.Entry对象集。Map.Entry是一个接口，用来描述依赖于实现的结构。

public class MapEntry<K,V> implements Map.Entry<K,V> {
  private K key;
  private V value;
  public MapEntry(K key, V value) {
    this.key = key;
    this.value = value;
  }
  public K getKey() { return key; }
  public V getValue() { return value; }
  public V setValue(V v) {
    V result = value;
    value = v;
    return result;
  }
  public int hashCode() {
    return (key==null ? 0 : key.hashCode()) ^
      (value==null ? 0 : value.hashCode());
  }
  public boolean equals(Object o) {
    if(!(o instanceof MapEntry)) return false;
    MapEntry me = (MapEntry)o;
    return
      (key == null ?
       me.getKey() == null : key.equals(me.getKey())) &&
      (value == null ?
       me.getValue()== null : value.equals(me.getValue()));
  }
  public String toString() { return key + "=" + value; }
} ///:~

为速度而散列

• 存储一组元素最快的数据结构是数组
• 数组不保存键本身，而是通过键对象生成一个数字，将其作为数组的下标，这个下标就是散列码。
• 于是查询一个值的过程首先就是计算散列码，然后使用散列码查询数组。
• 数组不直接保存值，而是保存值list。

public class SimpleHashMap<K,V> extends AbstractMap<K,V> {
  // Choose a prime number for the hash table
  // size, to achieve a uniform distribution:
  static final int SIZE = 997;
  // You can't have a physical array of generics,
  // but you can upcast to one:
  @SuppressWarnings("unchecked")
  LinkedList<MapEntry<K,V>>[] buckets =
    new LinkedList[SIZE];
  public V put(K key, V value) {
    V oldValue = null;
    int index = Math.abs(key.hashCode()) % SIZE;
    if(buckets[index] == null)
      buckets[index] = new LinkedList<MapEntry<K,V>>();
    LinkedList<MapEntry<K,V>> bucket = buckets[index];
    MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
    boolean found = false;
    ListIterator<MapEntry<K,V>> it = bucket.listIterator();
    while(it.hasNext()) {
      MapEntry<K,V> iPair = it.next();
      if(iPair.getKey().equals(key)) {
        oldValue = iPair.getValue();
        it.set(pair); // Replace old with new
        found = true;
        break;
      }
    }
    if(!found)
      buckets[index].add(pair);
    return oldValue;
  }
  public V get(Object key) {
    int index = Math.abs(key.hashCode()) % SIZE;
    if(buckets[index] == null) return null;
    for(MapEntry<K,V> iPair : buckets[index])
      if(iPair.getKey().equals(key))
        return iPair.getValue();
    return null;
  }
  public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
    for(LinkedList<MapEntry<K,V>> bucket : buckets) {
      if(bucket == null) continue;
      for(MapEntry<K,V> mpair : bucket)
        set.add(mpair);
    }
    return set;
  }
  public static void main(String[] args) {
    SimpleHashMap<String,String> m =
      new SimpleHashMap<String,String>();
    m.putAll(Countries.capitals(25));
    System.out.println(m);
    System.out.println(m.get("ERITREA"));
    System.out.println(m.entrySet());
  }
} /* Output:
{CAMEROON=Yaounde, CONGO=Brazzaville, CHAD=N'djamena, COTE D'IVOIR (IVORY COAST)=Yamoussoukro, CENTRAL AFRICAN REPUBLIC=Bangui, GUINEA=Conakry, BOTSWANA=Gaberone, BISSAU=Bissau, EGYPT=Cairo, ANGOLA=Luanda, BURKINA FASO=Ouagadougou, ERITREA=Asmara, THE GAMBIA=Banjul, KENYA=Nairobi, GABON=Libreville, CAPE VERDE=Praia, ALGERIA=Algiers, COMOROS=Moroni, EQUATORIAL GUINEA=Malabo, BURUNDI=Bujumbura, BENIN=Porto-Novo, BULGARIA=Sofia, GHANA=Accra, DJIBOUTI=Dijibouti, ETHIOPIA=Addis Ababa}
Asmara
[CAMEROON=Yaounde, CONGO=Brazzaville, CHAD=N'djamena, COTE D'IVOIR (IVORY COAST)=Yamoussoukro, CENTRAL AFRICAN REPUBLIC=Bangui, GUINEA=Conakry, BOTSWANA=Gaberone, BISSAU=Bissau, EGYPT=Cairo, ANGOLA=Luanda, BURKINA FASO=Ouagadougou, ERITREA=Asmara, THE GAMBIA=Banjul, KENYA=Nairobi, GABON=Libreville, CAPE VERDE=Praia, ALGERIA=Algiers, COMOROS=Moroni, EQUATORIAL GUINEA=Malabo, BURUNDI=Bujumbura, BENIN=Porto-Novo, BULGARIA=Sofia, GHANA=Accra, DJIBOUTI=Dijibouti, ETHIOPIA=Addis Ababa]
*///:~

覆盖hashcode

• 设计hashCode()时最重要的因素就是，无论何时，对同一个对象调用hashCode()都应该产生同样的值。
• String 如果值相同，那么这些String对象都映射到同一块内存区域，hashCode生成同样同样的结果。
• 一个设计hashCode的指导。

hashCode

9、选择接口的不同实现

• 容器之间的区别通常归结为由什么在背后支持他们。
• 对于List，ArrayList通常是访问最快的，LinkedList在表大小较大时将会有明显的访问时间增加。但是对于插入ArrayList支持不如LinkedList。
• 对于Set，HashSet的性能基本上总是比TreeSet好，特别是在添加和查询元素时。LinkedHashSet比HashSet多维护链表，插入代价更高。
• 对于Map，所有Map插入都会随Map尺寸变大而变慢，除了IdentityHashMap。TreeMap通常比HashMap慢。LinkedHashMap在插入时比HashMap慢一点，额外维护的链表。IdentityHashMap因为使用==而不是equals所以在get上快。
• HashMap的性能因子：容量，表中的桶位数，初识容量，表再创建时拥有的桶位数；尺寸，表中当前存储的项数；负载因子，尺寸、容量。默认的负载因子是0.75，达到了负载因子会再散列。

10、实用方法

singleton

快速报错

• Java容器有保护机制，能够防止多个进程同时修改同一个容器内容。如果在迭代遍历某个容器过程中，另一个进程接入其中，修改对象就会出现问题。

public class FailFast {
  public static void main(String[] args) {
    Collection<String> c = new ArrayList<String>();
    Iterator<String> it = c.iterator();
    c.add("An object");
    try {
      String s = it.next();
    } catch(ConcurrentModificationException e) {
      System.out.println(e);
    }
  }
} /* Output:
java.util.ConcurrentModificationException
*///:~

11、持有引用

• 对象是可获得的，是指此对象可在程序中的某处找到。
• 你在栈中有一个普通的引用，而它正指向此对象，也可能是你的引用指向某个对象，而那个对象含有另一个引用指向正在讨论的对象；也可能有更多中间链接。
• 如果一个对象是可获得的，垃圾回收器就不能释放他。
• 如果想继续持有某个对象引用，但也希望允许垃圾回收器释放，就应该使用Reference对象，内存耗尽时允许释放对象。
• 以Reference对象作为与普通引用之间的媒介。
• SoftReference、WeakReference、PhantomReference由强到弱排列，对应不同级别的可获得性。
• WeakHashMap，在这种映射中，每个值值保存一份实例以节省存储空间。当程序需要哪个值的时候，便在映射中查找现有对象，然后使用它。WeakHashMap允许垃圾回收器自动清理键和值。

class Element {
  private String ident;
  public Element(String id) { ident = id; }
  public String toString() { return ident; }
  public int hashCode() { return ident.hashCode(); }
  public boolean equals(Object r) {
    return r instanceof Element &&
      ident.equals(((Element)r).ident);
  }
  protected void finalize() {
    System.out.println("Finalizing " +
      getClass().getSimpleName() + " " + ident);
  }
}

class Key extends Element {
  public Key(String id) { super(id); }
}

class Value extends Element {
  public Value(String id) { super(id); }
}

public class CanonicalMapping {
  public static void main(String[] args) {
    int size = 1000;
    // Or, choose size via the command line:
    if(args.length > 0)
      size = new Integer(args[0]);
    Key[] keys = new Key[size];
    WeakHashMap<Key,Value> map =
      new WeakHashMap<Key,Value>();
    for(int i = 0; i < size; i++) {
      Key k = new Key(Integer.toString(i));
      Value v = new Value(Integer.toString(i));
      if(i % 3 == 0)
        keys[i] = k; // Save as "real" references
      map.put(k, v);
    }
    System.gc();
  }
} /* (Execute to see output) *///:~