likes
comments
collection
share

Java中的集合类(二)

作者站长头像
站长
· 阅读数 19

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,以实现类约束为准,这是一个十分难以记忆的知识点,如下图所示。 Java中的集合类(二) 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 内都不发生冲突。

转载自:https://juejin.cn/post/7241015051661082685
评论
请登录