thinking in java笔记 17 容器深入研究

***Collections类

public static <T> List<T> nCopies( int n, T o)

用单个对象的引用填充Collection

public static <T> void fill (List<? super T> list, T obj) {

替换已经在list中存在的元素，不能添加新的元素。

***填充容器

所有Collection子类型都有接受另一个Collection对象的构造器，用接受对象中的元素来填充新的容器。

***可选操作

执行各种不同的添加和移除的方法在Collection接口中都是可选操作，这意味着实现类并不需要为这些方法提供功能定义。

可选操作声明调用某些方法将不会执行有意义的行为，反而会抛出异常。

定义可选操作的目的：防治在设计中出现接口爆炸的情况。它使Java容器类库能达到易学易用的目标。未获支持的操作是一种特例，可以延时到需要的时候再实现。但为了能使这种方式工作：

1 UnsupportedOperationException必须是一种罕见事件。

2 若一个操作是未获支持的，那么在实现接口的时候可能就会导致UnsupportedOperationException，而不是将产品程序交给客户以后才出现。因为它表示了编程上有错误：使用了不正确的接口实现。

最常见的未获支持的操作，都来源于背后由固定尺寸的数据结构支持的容器。

1 使用Arrays. asList将数组转换为List时

2 Collections. unmodifiableList ( new ArrayList<String>())创建的不可修改的容器

对于将容器作为参数接受的方法，其文档应该指定哪些可选方法必须实现。

***List的功能方法

常用：add 添加对象， get一次取出一个元素， iterator获取用于该序列的iterator

***Set

Set接口：元素唯一，不保证维护元素次序

HashSet:查找速度快，存入元素必须定义hashCode()

TreeSet:保持次序，底层为树结构。使用它可以从Set中提取有序的序列。元素必须实现Comparable接口

LinkedHashSet:具有HashSet的速度，且内部使用链表维护元素的顺序（插入的次序），必须定义hashCode()

SortedSet:按对象的比较函数对元素排序

***队列

除并发外，Queue实现包括LinkedList,PriorityQueue.其差异在于排序行为而不是性能。可以将元素从队列的一段插入，另一端取出。除了优先级队列，Queue都为FIFO。

优先级队列：可通过存储实现了Comparable接口的对象，按照compareTo()确定对象的优先级实现控制元素存储顺序。

双向队列：可以在任一段添加移除元素。Java类库中无用于双向队列的接口。但LinkedList包含支持双向队列的方法，可使用组合方式利用其来实现Deque<T>类，但不常用。

***Map

映射表(关联数组)的基本思想是它维护的是键值关联，因此可以用键来查找值。在映射表中执行线性搜索速度很慢。

HashMap使用了散列码进行快速查询，散列码是每个对象都有的int值（Object类中的hashCode()）。 Map基于散列表的实现。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量capacity和负载因子load factor，以调整容器的性能。

     LinkedHashMap:类似于HashMap，但是迭代遍历它时，取得“键值对”的顺序是其插入次序，或者是最近最少使用(LRU)的次序。只比HashMap慢一点。而在迭代访问时发而更快，因为它使用链表维护内部次序。

     TreeMap:基于红黑树数据结构的实现。查看“键”或“键值对”时，它们会被排序（次序由Comparabel或Comparator决定）。TreeMap的特点在于，你得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map，它可以返回一个子树。

     WeakHashMap : 弱键(weak key)Map，Map中使用的对象也被允许释放:这是为解决特殊问题设计的。如果没有map之外的引用指向某个“键”，则此“键”可以被垃圾收集器回收。
     IdentifyHashMap : 使用==代替equals()对“键”作比较的hash map。专为解决特殊问题而设计。
   任何键都必须有equals()，如果键被用于散列Map，那么它必须具备恰当的hashCode()，如果键被用于TreeMap，那么它必须实现Comparable。

***散列与散列码

   默认的Object.equals()只是比较对象的地址，默认的hashCode()使用对象的地址计算散列码，所以一个Groundhog(3)并不等于另一个Groundhog(3)。因此，若想使用自己的类作为HashMap的键，必须同时重载hashCode()和equals().

   正确的equals()必须满足以下条件：

   1 自反性。对任意x，x.equals(x)一定返回true

   2 对称性。对任意x,y. 如果x.equals(y)==true,那么y.equals(x)==true

   3 传递性。对任意x,y,z.若x.equals(y)==true，y.equals(z)==true那么x.equals(z)==true

   4 一致性。对任意x,y.若对象中用于等价比较的信息没有改变，那么无论调用多少次x.equals(y)，结果应该一致。

   5 对任何不是null的x，x.equals(null)返回false

   使用散列的目的在于：使用一个对象来查找另一个对象。其关键点在于速度，而提高速度必须快速的查找到键。Hashing的目的在于将key存放到一个能快速查找到的地方。它使用一个array来存放index值（因为array尺寸固定，不能直接存放数据，已不能直接存放hashcode，因此使用固定大小的array存放索引值，hashcode % size = index），每个index值对应一个list，键和值被存储到这个list中。应用时，首先找到index值，然后对对应的list进行线性查询，这个过程是慢的，但好的哈希算法会使值均匀分布在list中。

   自定义hashCode（）：

      重要的原则是不论hashCode()何时被调用，特定对象都会产生特定的hashCode值，否则put()和get()时hashCode不同，则无法找到对象。我们有时不想每个新对象都会产生不同的hashCode(默认是Object产生的)，而是想通过对象中的值是否相同来决定是否产生新hashCode,因此需要自定义方法.

***选择合适的容器

   List：默认情况下应选择ArrayList.当存在大量的插入删除操作并影响性能时，可考虑使用 LinkedList（实现了双向链表，每个对象都包含List中上一个对象和下一个对象的引用，因此适合在列表中做插入删除操作）。如果元素个数固定，可以使用Arrays.asList()得到固定大小的List，或者直接使用Array。

   Set：默认选择HashSet,其add()和contains()速度快.当需要排序的set时，才选择TreeSet(其iterate()速度较快)。LinkedHashSet add()耗时比HashSet多，因为其维持列表与hash容器一致有额外的花费.

   Map:首选HashMap，因此速度快。当需要频繁排序时，选择TreeMap。除IdentityHashMap外其余map插入操作会随map变大而变慢。Hashtable和Hashmap速度相同，因HashMap要替代Hashtable，所以底层实现原理相同。LinkedHashMap插入速度稍慢，因其要保留插入顺序，因此其iteration速度快。

   HashMap参数：

          Initial capacity：初始化容量。如果会存储很多条目，应调大初始化容量，避免频繁的rehash。

        Load factor：到达此阈值后，capacity会加倍，并进行rehash。0.75是比较折中的值。



   List的排序和查找：

      对array排序时若使用Comparator，则在查找时必须使用相同的Comparator进行查找。

   只读的Collections Map

          List<String> a = Collections.unmodifiableList(

        new ArrayList<String>( data ));

       unmodifiableCollection

       unmodifiableSet

       unmodifiableSortedSet

       unmodifiableMap

       unmodifiableSortedMap

      通过这些方法，可以在类内部提供private可写的容器，而对外提供只读的容器。



    同步的Collections Map，语法同上

      Collection<String> c =

      Collections.synchronizedCollection(

        new ArrayList<String>());

   Fail fast：

      java容器有Fail fast机制，以防止多个地方同时对容器进行操作。如果使用过程中检测到其他人修改容器，则会抛出异常：ConcurrentModification- Exception.

     The ConcurrentHashMap, CopyOnWriteArrayList, and CopyOnWriteArraySet use  techniques that avoid ConcurrentModificationExceptions

   Reference:

      在 java.lang.ref库中，使gc更为灵活。如想保持对一个对象的引用，但又允许其被gc回收，可使用Reference对对象进行引用，包含 SoftReference, WeakReference, and PhantomReference。SoftReference用于内存敏感的高速缓存。   SoftReference        的原理是：在保持对对象的引用时保证在 JVM 报告内存不足情况之前将清除所有的软引用。 WeakReference   类的一个典型用途就是规范化映射（canonicalized mapping）。另外，对于那些生存期相对较长而且重新创建的开销也不高的对象来说，弱引用也比较有用，不管当前内存空间足够与否，都会回收它的内存。 PhantomReference  类只能用于跟踪对被引用对象即将进行的收集。虚引用”顾名思义，就是形同虚设，与其他几种引用都不同，虚引用并不会决定对象的生命周期。如果一个对象仅持有虚引用，那么它就和没有任何引用一样，在任何时候都可能被垃圾回收器回收。