Java中的集合类（二）

5. 元素的比较

• Comparable和 Comparator
  ??Java 中两个对象相比较的方法通常用在元素排序中，常用的两个接口分别是Comparable和Comparator，前者是自己和自己比，可以看作是自营性质的比较器;后者是第三方比较器，可以看作是自营性质的比较器。从词根上分析,Comparable以-able结尾，表示它有自身具备某种能力的性质，表明Comparable 对象本身是可以与同类型进行比较的，它的比较方法是 compareTo;而Comparator 以-or 结尾，表示自身是比较器的实践者，它的比较方法是compare。
  ??我们经常说的自然排序其实是以人类对常识认知的升序排序，比如数字的1、2、3，字母的a、bc等。我们熟知的Integer和String实现的就是Comparable 的自然排序。而我们在使用某个自定义对象时，可能需要按照自己定义的方式排序，比如在搜索列表对象SearchResut中进行大小比较时，先根据相关度排序，然后再根据浏览数排序,实现这样的自定义Comparable的示例代码如下:

public class SearchResult implements Comparable<SearchResult> {
    int relativeRatio;
    long count;
    int recentOrders;
    public SearchResult(int relativeRatio,long count) {
        this.relativeRatio = relativeRatio;
        this.count = count;
    }
   @Override
   public int compareTo(SearchResult o) {
       // 先比较相关度
         if (this.relativeRatio != o.relativeRatio) {
            return this.relativeRatio > o.relativeRatio 1 :-1;
        }
       // 相关度相等时再比较测览数
        if (this.count != o.count) {
            return this.count > o.count 1 : -1;
        }
        return 0;
    }
    public void setRecentOrders(int recentOrders) {
       this.recentOrders = recentOrders;
    }
}

??实现 Comparable 时，可以加上泛型限定，在编译阶段即可发现传入的参数非SearchResult对象，不需要在运行期进行类型检查和强制转换。如果这个排序的规则不符合业务方的要求，那么就需要修改这个类的比较方法compareTo，然而我们都知道开闭原则，即最好不要对自己已经交付的类进行修改。另外，如果另一个业务方也在使用这个比较方法呢?甚至再极端一点，这个SearchResult 是他人提供的类，我们可能连源码都没有。所以，我们其实需要在外部定义比较器，即 Comparator。
??正因为 Comparator的出现，业务方可以根据需要修改排序规则。如在上面的示例代码中，如果业务方需要在搜索时将最近订单数(recentOrders)的权重调整到相关度与浏览数之间，则使用Comparator 实现的比较器如下所示:

public class SearchResultComparator implements Comparator<SearchResult> {

    @Override
    public int compare(SearchResult o1, SearchResult o2) {
        // 相关度是第一排序准则，更高者排前(避免if-else 嵌套过多使用卫语句来实现)
        if (o1.relativeRatio != o2.relativeRatio) {
            return o1.relativeRatio > o2.relativeRatio 1 : -1;
        }

        //如果相关度一样，则最近订单数多者排前
        if (o1.recentOrders != o2.recentOrders) {
            return o1.recentOrders > o2.recentOrders 1 : -1;
        }
        // 如果相关度和最近订单数都一样，则测览数多者排前
        if (o1.count != o2.count) {
            return o1.count > o2.count 1 : -1;
        }
        return 0;
    }
}

??在JDK 中，Comparator最典型的应用是在Arrays.sort 中作为比较器参数进行排序

    public static <T> void sort(T[] a, Comparator<super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }

??红色的 <super T> 语法为下限通配，也就是将泛型类型参数限制为T或T的某个父类，直到 Object。该语法只能用在形参中来限定实参调用。如果本例中不加限定假定sort 对象是Integer，那么传入 String 时就会编译报错，就是充分利用了多态的向下转型的功能。
??约定俗成，不管是Comparable还是Comparator，小于的情况返回-1，等于的情况返回0，大于的情况返回1。当然，很多代码里只是判断是否大于或小于0，如在集合中使用比较器进行排序时，直接使用正负来判断比较的结果:

result = comparator.compare(key， t.key);
if (result < 0)
    t = t.left;
else if (result > 0)
  t = t.right;
else
  return t;

??我们再回到之前 sort0方法中的TimSort 算法，是归并排序(Merge Sort)与插入排序(Insertion Sort)优化后的排序算法。
??首先回顾一下归并排序的原理。长度为1的数组是排序好的，有n个元素的集合可以看成是n个长度为1的有序子集合;对有序子集合进行两两归并，并保证结果子集合有序，最后得到n/2个长度为 2的有序子集合;重复上一步骤直到所有元素归并成一个长度为”的有序集合。在此排序过程中，主要工作都在归并处理中，如何使归并过程更快，或者如何减少归并次数，成为优化归并排序的重点。
??再回顾插入排序工作的工作原理: 长度为 1的数组是有序的，当有了k个已排序的元素，将第k+1个元素插入已有的人个元素中合适的位置，就会得到一个长度为k+1已排序的数组。假设有n个元素且已经升序排列的数组，并且在数组尾端有等n+1个元素的位置，此时如果想要添加一个新的元素并保持数组有序，根据插入排序可以将新元素放到第n+1 个位置上，然后从后向前两两比较，如果新值较小则交换付置，直到新元素到达正确的位置。
??2002年Tim Peters 结合归并排序和插入排序的优点，实现了 TimSort 排序算法。该算法避免了归并排序和插入排序的缺点，相对传统归并排序，减少了归并次数，相对插入排序，引入了二分排序概念，提升了排序效率。TimSort 算法对于已经部分排序的数组，时间复杂度最优可达 O(m);对于随机排序的数组，时间复杂度为O(nlog)，平均时间复杂度为 O(nlogn)。因此Java在JDK7 中使用TimSort 算法取代了原来的归并排序。它有两个主要优化:
??(1) 归并排序的分段不再从单个元素开始，而是每次先查找当前最大的排序好的数组片段 run，然后对 run 进行扩展并利用二分排序，之后将该 run 与其他已经排序好的 run 进行归并，产生排序好的大 run
??(2) 引入二分排序，即 binarySort。二分排序是对插入排序的优化，在插入排序中不再是从后向前逐个元素对比，而是引入了二分查找的思想，将一次查找新元素合适位置的时间复杂度由 O(n) 降低到 O(logn)。

• hashCode 和 equals
  ??hashCode 和 equals 用来标识对象，两个方法协同工作可用来判断两个对象是否相等。众所周知，根据生成的哈希将数据离散开来，可以使存取元素更快。对象通过调用 Object.hashCode0 生成哈希值;由于不可避免地会存在哈希值冲突的情况，因此当hashCode 相同时，还需要再调用equals 进行一次值的比较，但是，若 hashCode不同，将直接判定 Objects 不同，跳过 equals，这加快了冲突处理效率。object 类定义中对hashCode和equals 要求如下
  ??(1)如果两个对象的 equals 的结果是相等的，则两个对象的 hashCode 的返回结
  果也必须是相同的。
  ??(2)任何时候覆写 equals，都必须同时覆写 hashCode
  ??在Map和 Set 类集合中，用到这两个方法时，首先判断 hashCode 的值，如果hash 相等，则再判断 equals 的结果，HashMap 的 get判断代码如下:

if (e.hash == hash && ((k = e.key) == key 1l (key != null
& key.equals(k))))
return (e = getNode(hash (key)， key)) == null null : e.value;

??if条件表达式中的e.hash=-hash 是先决条件，只有相等才会执行阴影部分。如果不相等，则阴影部分后边的equals 根本不会被执行。equals 不相等时并不强制要求hashCode 也不相等，但是一个优秀的哈希算法应尽可能地让元素均匀分布，降低冲突概率，即在 equals 不相等时尽量使 hashCode也不相等，这样&&或短路操作一旦生效，会极大地提高程序的执行效率。如果自定义对象作为 Map 的键，那么必须覆写 hashCode和equals。此外，因为 Set 存储的是不重复的对象，依据 hashCode和equals 进行判断，所以 Set 存储的自定义对象也必须覆写这两个方法。此时如果覆写了equals，而没有覆写 hashCode，具体会有什么影响，让我们通过如下示例代码深入体会:

public class EqualsObject {
    private int id;
    private String name;

    public EqualsObject(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        //如果引用指向同一个对象，则返回true
        if (this == o) return true;
        //如果为null，或者并非同类，刚直接圾间false(第1处)
        if (o == null || getClass() != o.getClass()) return false;

        EqualsObject temp = (EqualsObject) o;

        // 本示例判断标准是两个属性值相等，逻辑随业务场景不同而不同
        if (temp.getId() == this.id && name.equals(temp.getName())) {
            return true;
        }
        return false;
    }



 //getter and setter....
}

??第1处说明: 首先判断两个对象的类型是否相同，如果不匹配，则直接返回false。此处使用 getClass 的方式，就是严格限制了只有 EqualsObject 对象本身才可以执行equals 操作。
??这里并没有覆写 hashCode，那么把这个对象放置到 Set 集合中去:

Set<EqualsObject> hashSet = new HashSet<>();
EqualsObject a = new EqualsObject(1，"one");
EqualsObject b= new EqualsObject(1，“one");
EqualsObject c= new EqualsObject(1，"one");
hashSet.add(a);
hashSet.add(b);
hashset.add(c);
System.out.println(hashSet.size());

输出的结果是3。虽然这些对象显而易见是相同的，但在 HashSet操作中，应该只剩下一个，为什么结果是3呢?因为如果不覆写 hashCode0，即使equals0相等也毫无意义，Object.hashCode0的实现是默认为每一个对象生成不同的int数值，它本身是native 方法，一般与对象内存地址有关。下面查看 C++的源码实现:

VMENTRY(jint，JVM_IHashCode(INIEnv* env, jobject handle))
  JVMWrapper("JVM IHashCode") :
return handle == NULL 0 : ObjectSynchronizer::FastHashCode
  (THREAD，JNIHandles::resolve non_null(handle));
 VM END

ObjectSynchronizer的核心代码如下，从代码分析角度也印证了 hashCode就是根据对象的地址进行相关计算得到int类型数值的:

mark = monitor->header();
assert (mark->is_neutral()， "ninvariant");
hash = mark->hash();

intptr_t hash() const {
 return mask bits(value() >> hash_shift, hash _mask);
}

因为 EqualsObject没有覆写 hashCode，所以得到的是一个与对象地址相关的唯一值，回到刚才的 HashSet 集合上，如果想存储不重复的元素，那么需要在EqualsObject类中覆写 hashCode0:

@Override
public int hashCode() {
    return id + name.hashCode();
}

EqualsObject的name 属性是 String 类型，String 覆写了 hashCode0，所以可以直接调用。equals0的实现方式与类的具体处理逻辑有关，但又各不相同，因而应尽量分析源码来确定其判断结果。

6. fail-fast机制

??fail-fast 机制是集合世界中比较常见的错误检测机制，通常出现在遍历集合元素的过程中。下面通过校园生活中的一个例子来体会 fail-fast 机制。
??上课前，班长开始点名。刚点到一半，这时从教室外三三两两进来若干同学，同学们起哄:点错了!班长重新开始点名，点到中途，又出去几位同学，同学们又起哄说点错了，班长又需要重新遍历，这就是 fail-fast 机制。它是一种对集合(班级)遍历操作时的错误检测机制，在遍历中途出现意料之外的修改时，通过 unchecked 异常暴力地反馈出来。这种机制经常出现在多线程环境下，当前线程会维护一个计数比较器，即expectedModCount，记录已经修改的次数。在进入遍历前，会把实时修改次数modCount 赋值给expectedModCount，如果这两个数据不相等，则抛出异常。javautil下的所有集合类都是 fail-fast,concurrent包中的集合类都是fail-safe。与fail-fast不同,fail-safe对于刚才点名被频繁打断的情形，相当于班长直接拿出手机快速照相，然后根据照片点名，不再关心同学们的进进出出。
??人的大脑习惯用单线程方式处理日常逻辑，思维在某个时间段或某个深度上具有方向性。多线程的运行逻辑并非自然思维。我们通过ArrayList.subList0方法进-步阐述 fail-fast 这种机制。在某种情况下，需要从一个主列表 master 中获取子列表branch，master 集合元素个数的增加或删除，均会导致子列表的遍历、增加、删除,进而产生 fail-fast 异常。伪代码分析如下:

public class SubListFailFast {
    public static void main(String[] args) {
        List masterList = new ArrayList();
        masterList.add("one");
        masterList.add("two");
        masterList.add("three");
        masterList.add("four");
        masterList.add("five");
        List branchList = masterList.subList(0, 3);
        //下方三行代码，如果不注释掉，则会导致 branchList 操作出现异常(第1处)
        masterList.remove(0);

        masterList.add("ten");
        masterList.clear();
        //下方四行全部能够正确执行
        branchList.clear();
        branchList.add("gix");
        branchList.add("seven");
        branchList.remove(0);
//正常遍历结束，只有一个元素:seven
        for (Object t : branchList) {
            System.out.println(t);
        }
// 子列表修改导致主列表也被改动，输出:[seven，four， five]
        System.out.println(masterList);
    }
}

第1处说明，如果不注释掉，masterList的任何关于元素个数的修改操作都会号致branchList的“增删改查”抛出ConcurrentModificationException异常。在实际调研中大部分程序员知道subList子列表无法序列化，也知道它的修改会导致主列表的修改，但是并不知道主列表元素个数的改动会让子列表如此敏感，频频抛出异常。在实际代码中，这样的故障案例属于常见的类型。subList 方法返回的是内部类 SubList 的对象SubList类是ArrayList的内部类，SubList的定义如下，并没有实现序列化接口，无法网络传输:

private static class Sublist<E> extends AbstractList<E> implements
RandomAccess {...)

在 foreach 遍历元素时，使用删除方式测试 fail-fast机制，查看如下代码

public class ArrayListFailFast {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("one");
        list.add("two");
        list.add("three");
        for (String s : list) {
            if ("two".equals(s)) {
                list.remove(s);
            }
        }
        System.out.println(list);
    }
}

编译正确，执行成功! 输出[one, three]。说好的 ConcurentModificationException 异常呢?这只是一个巧合而已。在集合遍历时维护一个初始值为0的游标 cursor，从头到尾地进行扫描，当cursor等于 size 时，退出遍历。执行 remove这个元素后，所有元素往前拷贝，size-size-1即为2，这时cursor也等于2。在执行hasNext0 时，结果为 alse，退出循环体，并没有机会执行到 nex0 的第一行代码checkForComodification0，此方法用来判断 expectedModCount和 modCount 是否相等，如果不相等，则抛出 ConcurrentModifcationException 异常。
这个案例应引起对删除元素时的 fail-fast 的警觉。我们可以使用 Iterator 机制进行遍历时的删除，如果是多线程并发，还需要在iterator 遍历时加锁，如下源码:

Iterator<string> iterator = list.iterator();
while (iterator.hasNext()){
    synchronized(对象){
        String item = iterator.next();
        if (删除元素的条件) {
            iterator.remove();
        }
    }
}

或者使用并发容器CopyOnWriteArrayList代替ArrayLis。顺便简单介绍一个COW(奶牛)家族，即Copy-On-Write。它是并发的一种新思路，实行读写分离，如果是写操作，则复制一个新集合，在新集合内添加或删除元素。待一切修改完成之后，再将原集合的引用指向新的集合。这样做的好处是可以高并发地对 COW 进行读和遍历操作，而不需要加锁，因为当前集合不会添加任何元素。使用COW 时应注意两点:第一，尽量设置合理的容量初始值，它扩容的代价比较大;第二，使用批量添加或删除方法，如 addAll 或 removeAll 操作，在高并发请求下，可以攒一下要添加或者，的元素，避免增加一个元素复制整个集合。如果集合数据是 100MB，再写入 5OMB那么某个时间段内占用的内存就达到(100MB X2)+50MB-250MB，内存的大量用会导致GC的频繁发生，从而降低服务器的性能，我们观察如下代码:

    public static void main(String[] args) {
        List<Long> copy = new CopyOnWriteArrayList<Long>();
        long start = System.nanoTime();
        for (int i = 0; i < 20 * 10000; i++) {
            copy.add(System.nanoTime());
        }
    }

循环20 万次，不断地进行数据插入，这对 COW 类型的集合来说简直是灾难的操作，本示例执行时间为97.8秒，如果换成ArrayList，则只需39 毫秒，差距大!要初始化这样的COW集合，建议先将数据填充到ArayList 集合中去然后ArrayList 集合当成COW的参数，这就是使用批量添加的另一种方式。这种一个接个往里增加元素的场景，简直就是 COW 的阿喀琉斯之踵。所以明显 COW 适用于多写极少的场景。
COw 是 fail-safe 机制的，在并发包的集合中都是由这种机制实现的，fail-safe是在安全的副本(或者没有修改操作的正本)上进行遍历，集合修改与副本的遍历是有任何关系的，但是缺点也很明显，就是读取不到最新的数据。这也是 CAP理论中C(Consistency)与A(Availability)的矛盾，即一致性与可用性的矛盾。

7. Map类集合

??在数据元素的存储、查找、修改和遍历中，Java 中的 Map 类集合都与 Collectiot类集合存在很大不同。它是与 Collection 类平级的一个接口，在集合框架图上，它有一条微弱的依赖线与Collection 类产生关联，那是因为部分方法返回 Collection 视图比如values0方法返回的所有 Value的列表。Map类集合中的存储单位是KV键值对Map 类就是使用一定的哈希算法形成一组比较均匀的哈希值作为 Key，Value值挂Key上。Map 类的特点如下:

• Map 类取代了旧的抽象类 Dictionary，拥有更好的性能。
• 没有重复的 Key，可以有多个重复的 Value。
• Valu可以是List、Map、Set类对象。
• KV 是否允许为 null，以实现类约束为准。
  Map 接口除提供传统的增删改查方式外，还有三个 Map 类特有的方法，即返回所有的 Key，返回所有的 Vaue，返回所有的 KV键值对。源码加注释如下:

//返回Map类对中的 Key的视图
Set<K> keySet();
//返 回Map 类对象中的所有 Value集合的 Collection视图
//返回的集合实现类为 Values extends AbstractCollection<v>
Collection<v> values();
//返回Map类对象中的Key-Value 对的 Set 视图
Set<Map.Entry<K，V>> entrySet();

通常这些返回的视图是支持清除操作的，但是修改和增加元素会抛出异常，因为AbstractCollection 没有实现 agd 操作，但是实现了 remove、clear 等相关操作。所以在使用这些视图返回集合时，注意不要操作此类相关方法。是否将KV 设置为 null，以实现类约束为准，这是一个十分难以记忆的知识点，如下图所示。

主要Map类集合

TreeMap
??TreeMap 是按照Key的排序结果来组织内部结构的Map 类集合，它改变了Map 类散乱无序的形象。虽然 TreeMap 没有 ConcurrentHashMap 和 HashMap 普及(毕竟插入和删除的效率远没有后两者高)，但是在 Key 有排序要求的场景下，使用TreeMap 可以事半功倍。在集合框架图中，它们都继承于 AbstractMap 抽象类
??总体来说，TreeMap的时间复杂度比 HashMap 要高一些，但是合理利用好TreeMap 集合的有序性和稳定性，以及支持范围查找的特性，往往在数据排序的场景中特别高效。另外，TreeMap 是线程不安全的集合，不能在多线程之间进行共享数据的写操作。在多线程进行写操作时，需要添加互斥机制，或者把对象放在Collections.synchronizedMap(treeMap)中实现同步。
HashMap
??除局部方法或绝对线程安全的情形外，优先推荐使用 ConcurrentHashMap。二者虽然性能相差无几，但后者解决了高并发下的线程安全问题。HashMap 的死链问题及扩容数据丢失问题是慎用 HashMap 的两个主要原因.
ConcurrentHashMap
??考虑到线程并发安全性，ConcurrentHashMap 是比HashMap 更加推荐的一种哈希式集合。JDK8对 ConcurrentHashMap 进行了脱胎换骨式的改造，使用了大量的 lockfree 技术来减轻因锁的竞争而对性能造成的影响。
??Hashtable是在JDK1.0中入的哈希式集合，以全互斥方式处理并发情况，性能极差; HashMap是在JDK1.2中引入的，是非线程安全的，它最大的问题是在并发写的情形下，容易出现死链问题，导致服务不可用。ConcurrentHashMap 是在JDK5中引入的线程安全的哈希式集合，在JDK8之前采用了分段锁的设计理念，相当于 Hashtable 与 HashMap 的折中版本，这是效率与一致性权衡后的结果。分段锁是由内部类 Segment 实现的，它线承RecntrantLock，用来管理它辖区的各个 HashEntry。 ConcurrentHashMap 被 Segmem 成了很多小区，Segment就相当于小区保安，HashEntry列表相当于小区业主，小保安通过加锁的方式，保证每个Segment 内都不发生冲突。