《Java编程思想》笔记17-容器深入研究

虚线框表示 abstract 类，Abstract 开头的类是部分实现了特定接口的工具。

可选操作

在 Collection 接口中，以下几个方法，

• retainAll()
• removeAll()
• clear()
• add()
• addAll()
• remove()

它们是可选方法。但仅仅是在官方文档的方法解释后面加了两个字“(optional operation)”而已。

它的实现方式非常隐蔽，当我们用“Arrays.asList()”方法把一个数组转换成一个 List 的时候，看起来返回的数据类型是 ArrayList，但注意这不是 java.util.ArrayList，而是 Arrays 内部一个同名的套嵌类 java.util.Arrays.ArrayList。在这个“山寨” ArrayList 里以上列出来的方法只是假装实现了一下，抛出一个 UnsupportedOperationException 而已。

Set

希望放入 Set 中的元素类型必须先实现一些特定方法：

1. 所有实现Set接口的类，都要求内部元素实现 equals() 方法。为了保证唯一性。对于良好的编程风格而言，你应该在覆盖 eqauls() 方法时，总是同时覆盖 hashCode() 方法。
2. HashSet 要实现 hashCode() 方法。
3. 以 TreeSet 为代表的 SortedSet 系需要内部元素实现 Comparable 接口。也就是实现 compareTo() 方法。

没有实现特定方法，存到 Set 里就会乱套。但编译器不会报错。因为默认的 equals() 和 hashCode() 虽然是错的，但是能运行的。

在 compareTo() 中，我没有使用“简洁明了”的形式 return i – i2，因为这是一个常见的编程错误，它只有在 i 和 i2 都是无符号的 int 时才能正确工作。对于 Jav a的有符号 int，它就会出错，因为 int 不够大，不足以表现两个有符号的 int 的差。例如 i 是很大的正整数，而 j 是很大的负整数， i-j 就会溢出并且返回负值，这就不正确了。return (arg.i < i ? -1 : (arg.i == i ? 0 : 1))

Map

• HashMap(默认选择，速度最快)：Map基于散列表的实现（它取代了 Hashtable）。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量和负载因子，以调整容器的性能。
• LinkedHashMap：类似于 HashMap，但是迭代遍历它时，取得“键值对”的顺序是其插入次序，或者是最近最少使用（LRU）的次序。只比 HashMap 慢一点；而在迭代访问时反而更快，因为它使用链表维护内部次序。
• TreeMap：基于红黑树的实现。查看“键”或“键值对”时，它们会被排序（次序由 Comparable 或 Comparator 决定，必须实现 Comparable）。TreeMap 的特点在于，所得到的结果是经过排序的。TreeMap 是唯一的带有 subMap() 方法的 Map，它可以访问一个子树。
• WeakHashMap：弱键（weak key）映射，允许释放映射所指向的对象；这是为解决某类特殊问题而设计的。如果映射之外没有引用指向某个“键”，则此“键”可以被垃圾回收器回收
• ConcurrentHashMap：一种线程安全的 Map，它不涉及同步加锁。
• IdentityHashMap：使用 == 代替 equals() 对“键”进行比较的散列映射。专为解决特殊问题而设计的。

LinkedHashMap

为了提高速度，LinkedHashSet 散列化所有的元素，但是在遍历键值对时，却又以元素的插入顺序返回键值对。此外，可以在构造器中设定 LinkedHashSet，使之采用基于访问的最少使用（LRU）算法，于是没有被访问过的（可被看作需要删除的）元素就会出现在队列的前面。对于需要定期清理元素以节省空间的程序来说，此功能使得程序很容易得以实现。

public class LinkedHashMapDemo {
  public static void main(String[] args) {
    LinkedHashMap<Integer,String> linkedMap = new LinkedHashMap<Integer,String>(new CountingMapData(9));
    print(linkedMap);

    linkedMap = new LinkedHashMap<Integer,String>(16, 0.75f, true);
    linkedMap.putAll(new CountingMapData(9));
    print(linkedMap);
    for(int i = 0; i < 6; i++)
      linkedMap.get(i);
    print(linkedMap);
    linkedMap.get(0);
    print(linkedMap);
  }
} /* Output:
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}
{6=G0, 7=H0, 8=I0, 0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0}
{6=G0, 7=H0, 8=I0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 0=A0}
*///:~

散列与散列码

数组并不保存键本身。而是通过键对象生成一个数字，将其作为数组的下标。这个数字就是散列码，由定义在 Object 中的、且可能由你的类覆盖的 hashCode() 方法。

数组容量是固定的，所以散列码可能会有冲突，如果没有冲突就是一个完美的散列函数（EnumMap 和 EnumSet）。通常，冲突由外部链接处理：数组不保存值，而是保存值的 list。

HashMap 的性能因子

可以通过手工调整 HashMap 来提高其性能，从而满足我们特定应用的需求。

• 容量：表中的桶位数
• 初始容量：表在创建时所拥有的桶位数。HashMap 和 HashSet 都具有允许你指定初始容量的构造器。
• 尺寸：表中当前存储的项数。
• 负载因子：尺寸/容量。空表的负载因子是 0，而半满表的负载因子是 0.5，依次类推。负载轻的表产生冲突的可能性小，因此对于插入和查找都是最理想的（但是会减慢使用迭代器进行遍历的过程）。HashMap 和 HashSet 都具有允许你指定负载因子的构造器，表示当负载情况达到该负载因子的水平时，容器将自动增加其容量（桶位数），实现方式是使容量大致加倍，并重新将现有对象分布到新的桶位集中（则被称为再散列）

HashMap 使用的默认负载因子是 0.75（只有当表达到四分之三满时，才进行再散列），这个因子在时间和空间代价之间达到了平衡。更高的负载因子可以减低表所需的空间，但是会增加查找代价，这很重要，因为查找是我们在大多数时间里所做的操作（包括 get() 和 put()）。

如果你知道将在 HashMap 中存储多少项，那么创建一个具有恰当大小的初始容量将可以避免自动再散列的开销。

设定 Collection 或 Map 为不可修改

unmodifiableSet() 方法

此方法允许你保留一份可修改的容器，作为类的 private 成员，然后通过某个方法调用返回该容器的“只读”的引用。这样一来，就只有你可以修改容器的内容，而别人只能读取。

HashSet<String> original = new HashSet<String>(data);
Set<String> unmodifiable = Collections.unmodifiableSet(original);
print(unmodifiable); // [BENIN, BURUNDI]
print(original); // [BENIN, BURUNDI]
original.add("one"); //
print(unmodifiable); // [BENIN, one, BURUNDI]
print(original); // [BENIN, one, BURUNDI]
unmodifiable.add("one"); // 报错

Collection 或 Map 的同步控制

synchronizedSet() 方法

持有引用

http://www.ciaoshen.com/java/thinking%20in%20java/data%20structure/2016/09/09/tij4-17.html

关于弱引用方面不错的一篇文章： 《深入探讨 java.lang.ref 包》

四种不同强度 reference 的定义： 1.普通引用：没什么好说的。 2.软引用（SoftReference）：系统资源紧张的时候，系统会删除软引用。优先删除长久没用的引用。 3.弱引用（WeakReference）：GC的时候删除清理弱引用。 4.虚引用（PhantomReference）：通过虚引用无法获得对象。

ReferenceQueue

当软引用，弱引用，虚引用被系统清除以后，如果绑定了 ReferenceQueue，这些引用会被加入 ReferenceQueue。

虚引用（PhantomReference）构造函数必须传入一个 ReferenceQueue 作为参数。

public PhantomReference(T referent, ReferenceQueue<? super T> q) {
    super(referent, q);
}

软引用和弱引用可以选择在构造函数传入 ReferenceQueue 或者不传入。

不同强度引用被加入 ReferenceQueue 的时机不同：

• 当一个对象只维持着 WeakReference，直接被加入 ReferenceQueue。然后等待被GC销毁。
• 当一个对象只维持着 PhantomReference，GC 先销毁对象，然后把这个虚引用加入 ReferenceQueue。

BitSet

如果想要高效率地存储大量“开/关”信息，BitSet 是很好的选择。不过它的效率仅是对空间而言；如果需要高效的访问时间，BitSet 比本地数组稍慢一点。

BitSet 的最小容量是 long:64 位。如果存储的内容比较小，例如 8 位，那么 BitSet 就浪费了一些空间。

如果拥有一个可以命名的固定的标志集合，那么 EnumSet 和 BitSet 相比，通常是一种更好的选择，因为 EnumSet 允许你按照名字而不是数字位的位置进行操作，因此可以减少错误。EnumSet 还可以防止你因不注意而添加新的标志位置，这种行为能够引发严重的、难以发现的缺陷。你应该使用 BitSet 而不是 EnumSet 的理由只包括：只有在运行时才知道需要多少个标志；对标志命名不合理；需要 BitSet 中的某些特殊操作。