Java 容器和泛型HashSet,TreeSet 和 LinkedHashSet比较

图片 3

一、Set回顾

一个不包括重复元素(包括可变对象)的Collection,是一种无序的集合。Set不包含满
a.equals(b) 的元素对a和b,并且最多有一个null。

泥瓦匠的记忆宫殿:

1、不允许包含相同元素

2、判断对象是否相同,根据equals方法

图片 1

集合概述

  • 集合用来储存数量不等的对象,且只能保存对象,实际保存的是对象的引用变量
  • 主要由两个接口派生而出,Collection(派生了Set List Queue) Map
  • Set无序不重复,List有序重复,Map key-value队,Queue是队列实现

图片 2

图片 3


10.1 Set集合

       
Set接口继承Collection接口,没有提供额外的方法。Set集合不允许包含相同的元素,向Set集合添加已存在的元素时,add()方法返回false。

二、HashSet

一个按着Hash算法来存储集合中的元素,其元素值可以是NULL。它不能保证元素的排列顺序。同样,HashSet是不同步的,如果需要多线程访问它的话,可以用
Collections.synchronizedSet 方法来包装它:

Set s = Collections.synchronizedSet(new HashSet(...));

同上一节一样,用迭代器的时候,也要注意 并发修改异常ConcurrentModificationException

要注意的地方是,HashSet集合判断两个元素相等不单单是equals方法,并且必须hashCode()方法返回值也要相等。看下面的例子:

import java.util.HashSet;

class EuqalsObj
{
    public boolean equals(Object obj)
    {
        return true;
    }
}

class HashCodeObj
{
    public int hashCode()
    {
        return 1;
    }
}

class HashSetObj
{
    public int hashCode()
    {
        return 2;
    }

    public boolean equals(Object obj)
    {
        return true;
    }
}

public class HashSetTest
{
    public static void main(String[] args)
    {
        HashSet objs = new HashSet();
        objs.add(new EuqalsObj());
        objs.add(new EuqalsObj());
        objs.add(new HashCodeObj());
        objs.add(new HashCodeObj());
        objs.add(new HashSetObj());
        objs.add(new HashSetObj());

        System.out.println("HashSet Elements:");
        System.out.print("/t" + objs + "/n");
    }
}

Run 一下,控制台如下输出:

HashSet Elements:
    [HashCodeObj@1, HashCodeObj@1, HashSetObj@2, EuqalsObj@1471cb25, EuqalsObj@3acff49f]

泥瓦匠根据结果,一一到来。首先,排列顺序不定。

HashSetObj 类满足我们刚刚的要求,所以集合中只有一个且它的HashCode值为2。

HashCodeObj
类虽然它们HashCode值为1,但是他们不相等。(其实当HashCode值一样,这个存储位置会采用链式结构保存两个HashCodeObj对象。)

同样,EqualsObj
类他们相等,但是他们HashCode值不等,分别为1471cb25、3acff49f。

因此,用HashSet添加可变对象,要注意当对象有可能修改后和其他对象矛盾,这样我们无法从HashSet找到准确我们需要的对象。

Collection和Iterator接口

  • Collection是Set List
    Queue的父接口,该接口里提供的方法可以操作Set、List、Queue集合。有add
    addAll clear contains containsAll isEmpty iterator remove removeAll
    retainAll size toArray。
  • 所有的Collection实现类都已经重写了toString()方法
  • Iterable是Collection的一个父接口,其forEach(Consumer
    action)默认方法可以用来遍历集合元素,Consumer是函数式接口,可以用Lambda表达式
  • Iterator接口主要用于遍历Collection集合元素,Iterator对象被称为迭代器
  • Iterator提供的方法:hasNext next remove forEachRemaining(java8新增)
  • 用集合实例调用Iterator构造器创建迭代器实例,Iterator必须依附于Collection对象
  • 值传递,修改迭代变量的值对集合无影响
  • 使用Iterator迭代访问集合元素时,只能通过remove()
    next()返回的元素,其他修改都不允许,一旦检测到集合被修改,会立即引发异常
  • Collection还可以用foreach循环来迭代访问集合元素,在迭代中同样不能改变集合
  • Collection新增removeIf(Predicate filter)批量删除符合条件的集合元素
  • Predicate是函数式接口,其test方法检测对象是否满足指定条件
  • 独立使用Steam
    • 使用Steam或XxxSteam的builder()类方法创建Stream对应的Builder
    • 重复调用Builder的add()方法向该流中添加多个元素
    • 调用Builder的build()方法获取对应的Stream
    • 调用Stream的聚集方法
  • 对于大部分的聚集方法,每个Stream只能执行一次,分为中间方法和末端方法,流的方法又两个特性,有状态的方法和短路方法
  • Stream常用中间方法:filter mapToXxx peek distinct sorted limit
    常用末端方法:forEach toArray reduce min max count anyMatch allMatch
    nonMatch findFirst findAny
  • 使用Collection接口提供的一个stream()默认方法返回集合对应的流,使用流式API来整体操作集合元素很方便

10.2 HashSet类

       
HashSet按Hash算法存储集合中的元素,具有良好的性能。Hash会调用该对象的hashCode()方法来得到该对象的hashCode值,然后根据hashCode值决定该对象在集合里的存储位置。即HashSet集合采用hash算法来决定元素的存储位置

        HashSet中每个能存储元素的位置被称为“桶”。

    HashSet具有如下特点:

        – 元素的排列顺序与添加顺序不一定相同。

        – 不是线程同步的。

        – 集合元素可以是null

    HashSet判断两个元素相等的标准:

        两个对象通过equals()方法比较相等,并且两个对象的hashCode()方法返回值也相等。

    HashSet重写equals和hashCode方法的规则:

       
如果两个对象通过equals()方法比较返回true,这两个对象的hashCode()值也应该相同。

 
  注意:如果HashSet存储了可变类,对某一个元素的更改致使集合中出现两个相同的元素,未被修改的元素可以被删除,修改后的元素无法被删除。因为HashSet根据hashCode值找到存储位置,然后用equals判断相等。

三、LinkedHashList

HashSet的子类,也同样有HashCode值来决定元素位置。但是它使用链表维护元素的次序。记住两个字:有序

有序的妙用,复制。比如泥瓦匠实现一个HashSet无序添加,然后复制一个一样次序的HashSet来。代码如下:

package com.sedion.bysocket.collection;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashListTest
{
    public static void main(String[] args)
    {
        /* 复制HashSet */
        Set h1 = new HashSet<String>();
        h1.add("List");
        h1.add("Queue");
        h1.add("Set");
        h1.add("Map");

        System.out.println("HashSet Elements:");
        System.out.print("/t" + h1 + "/n");

        Set h2 = copy(h1);
        System.out.println("HashSet Elements After Copy:");
        System.out.print("/t" + h2 + "/n");
    }

    @SuppressWarnings({ "rawtypes", "unchecked" })
    public static Set copy(Set set)
    {
        Set setCopy = new LinkedHashSet(set);
        return setCopy;
    }

}

Run 一下,控制台输出:

HashSet Elements:
    [Map, Queue, Set, List]
HashSet Elements After Copy:
    [Map, Queue, Set, List]

可见,每个数据结构都有它存在的理由。

Set集合

  • Set与Collection基本相同,没有提供额外的方法,Set不允许包含重复元素,不能记住元素添加顺序
  • Set三个常用实现类,HashSet TreeSet EnumSet

HashSet

  • HashSet是Set接口的典型实现,大多时候都用这个,按Hash算法来存储集合中的元素,具有很好的存取和查找性能
  • 特点:不能保证元素的排列顺序、不是同步的,必须通过代码来保证其同步、集合元素可以是null
  • 向集合中存入一个元素时HashSet会调用hashCode()方法得到该对象的hashCode值,根据值决定元素的储存位置
  • HashSet判断两个元素的相等标准是equals()比较相等并且hashCode()方法返回值相等,所以重写方法时尽量保证equals()和hashCode()比较结果一致
  • equals()相等hashCode()不等时,会将两个相同元素保存在不同位置,违背了Set的规则。equals()不等hashCode()相等时会在一个位置上用链式结构保存多个对象,导致定位性能下降。
  • 重写hashCode()方法的基本规则:
    • 程序运行中,同一对象多次调用hashCode()方法应该返回相等的值
    • 两个对象equals()返回true时,hashCode()也应该又相同的返回值
    • 对象中用于equals()方法比较标准的实例变量也都应该用于计算hashCode值
  • 当程序把可变对象添加到HashCode中后,尽量不要去修改参与计算hashCode()和equals()的实例变量,否则会导致HashSet无法正确操作这些集合元素
  • HashSet有一个子类LinkedHashSet,它同时使用链表维护元素次序,遍历时会按元素添加顺序来访问
  • LinkedHashSet因为需要维护元素的插入顺序,性能略低于HashSet,但在迭代访问全部元素时有良好的性能

TreeSet

  • TreeSet是SortedSet接口的实现类,可以确保元素处于排序状态
  • 比起HashSet额外提供的方法:comparator first last lower higher subSet
    headSet tailSet
  • TreeSet采用红黑树的数据结构存储集合元素,支持两种排序方式:自然排序和定制排序,默认自然排序
  • 自然排序调用Comparable接口的compareTo()方法来比较元素大小关系,然后升序排列
  • 添加到自然排序TreeSet的对象必须实现了Comparable接口,实现了compareTo()方法
  • 大部分类在实现compareTo()时都需要比较对象是相同类的实例,所以向TreeSet中添加的应该是同一个类的对象
  • TreeSet比较两个对象是否相等的唯一标准是compareTo()是否返回0,重写equals()时应该保证与compareTo()方法结果一致
  • TreeSet可以删除没有被修改实例变量且不与其他被修改实例变量的对象重复的对象
  • 当TreeSet中可变对象的实例变量被修改时,处理这些对象很复杂且容易出错,所以不要修改关键的实例变量
  • 定制排序,new
    TreeSet(Comparator对象),可以用Lambda表达式代替,根据此来排序
  • 依然不可以添加不同类的实例,比较元素相等的标准是Comparator

EnumSet

  • EnumSet中的元素必须是指定美剧类型的枚举值,有序,以枚举值在枚举类内定义顺序来决定,不允许加入null
  • 内部以位向量的形式储存,EnumSet对象占用内存小运行效率高
  • EnumSet只能通过类方法来创建实例,allOf complementOf copyOf noneOf of
    range
  • 试图复制一个Collection集合里的元素来创建EnumSet集合时,必须保证Collection集合里的所有元素都是同一个枚举类的枚举值

Set实现类的性能分析

  • HashSet比TreeSet性能好,特别是添加、查询等操作,只有当需要保持排序的Set时才使用TreeSet,其他时候应该使用HashSet
  • LinkedHashSet对于HashSet,普通的插入、删除操作较慢,但遍历会更快
  • EnumSet是三个实现类中性能最好的,但是只能保存同一枚举类的枚举值作为集合元素
  • 三个实现类都是线程不安全的,必须手动保证集合的同步性,可以通过Collections工具类的synchronizedSortedSet来包装Set集合,最好在创建时执行。

10.3 LinkedHashSet类

       
LinkedHashSet类是HashSet类的子类,根据元素的hashCode值来决定元素的存储位置,使用链表维护元素的添加次序。遍历LinkedHashSet集合里的元素时,LinkedHashSet会按照元素的添加顺序来访问集合里的元素。

四、TreeSet

TreeSet使用树结构实现(红黑树),集合中的元素进行排序,但是添加、删除和包含的算法复杂度为O(log(n))。

举个例子吧,首先我们定义一个Bird类。(鸟是泥瓦匠最喜欢的动物)

class Bird
{
    int size;

    public Bird(int s)
    {
        size = s;
    }

    public String toString()
    {
        return size + "";
    }

}

然后用TreeSet添加Bird类。

public class TreeSetTest
{
    public static void main(String[] args)
    {
        TreeSet<Bird> bSet = new TreeSet<Bird>();
        bSet.add(new Bird(1));
        bSet.add(new Bird(3));
        bSet.add(new Bird(2));

        Iterator<Bird> iter = bSet.iterator();

        while (iter.hasNext())
        {
            Bird bird = (Bird) iter.next();
            System.out.println(bird);
        }
    }
}

Run一下,控制台输出如下:

Exception in thread "main" java.lang.ClassCastException: Bird cannot be cast to java.lang.Comparable
    at java.util.TreeMap.compare(Unknown Source)
    at java.util.TreeMap.put(Unknown Source)
    at java.util.TreeSet.add(Unknown Source)
    at com.sedion.bysocket.collection.TreeSetTest.main(TreeSetTest.java:29)

答案很明显,TreeSet是排序的。所以Bird需要实现Comparable此接口。

java.lang.Comparable此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序,类的 compareTo 方法被称为它的自然比较方法

修改Bird如下:

class Bird implements Comparable<Bird>
{
    int size;

    public Bird(int s)
    {
        size = s;
    }

    public String toString()
    {
        return size + "号鸟";
    }

    @Override
    public int compareTo(Bird o)
    {
        return size - o.size;
    }

}

再次Run一下:

1号鸟
2号鸟
3号鸟

List集合

  • List集合有序、可重复,每个元素都有对应的顺序索引,从0开始
  • List接口增加的一些方法:get indexOf lastIndexOf set subList
    replaceAll sort,还有一些原有方法的重载
  • List判断两个对象相等的唯一标准是equals()
  • set(int index, Object
    element)方法不会改变List集合的成都,索引必须有效
  • sort()和replaceAll()都可以提供一个Lambda表达式作为参数
  • List还额外提供listIterator(),返回一个ListIterator对象,ListIterator接口继承了Iterator接口,增加了hasPrevious
    previous add 方法,增加了向前迭代的功能

ArrayList和Vector

  • 都是基于数组实现的,封装了一个动态的、可再分配的Object[]数组,不指定initialCapacity时,数组默认长度为10
  • initialCapacity参数设置数组的长度,会自动增加,当添加大量元素时可以用ensureCapacity(int
    minCapacity)方法一次性增加initialCapacity大小,减少分配次数,提高性能
  • trimToSize()调整数组长度等于当前元素个数
  • Vector比较古老,有很多缺点,不推荐使用
  • ArrayList线程不安全,Vector线程安全,所以性能相对较低
  • Stack继承了Vector,模拟栈,进出栈都是Object类型,需要类型转换,提供了peek
    pop push方法,同样比较古老不推荐使用,应该考虑ArrayDeque
  • Arrays工具类有个asList()方法江数组转换成List集合,是Arrays内部类ArrayList的实例,固定长度,只能遍历访问,不能增删

10.4 TreeSet类

       
TreeSet类是SortedSet接口的实现类,TreeSet集合内的元素处于有序状态。TreeSet采用红黑树的数据结构来存储集合元素。TreeSet中应添加同一种类型的对象。

    TreeSet集合新增如下方法:

        – Comparator
comparator():如果TreeSet使用的定制排序,此方法将返回使用的Comparator;若使用了自然排序,则返回null。

        – Object first():返回集合中的第一个元素。

        – Object last():返回集合中的最后一个元素。

        – Object lower(Object o):小于o的最大元素,o不需要存在集合中。

        – Object higher(Object o):大于o的最小元素,o不需要存在集合中。

        – SortedSet subSet(Object form, Object
to):返回form(包括)到to(不包括)之间的元素作为子集合。

        – SortedSet headSet(Object to):返回小于to的元素作为子集合。

        – SortedSet tailSet(Object
from):返回大于或等于from的元素作为子集合。

    实现了Compable接口的常用类及比较方式:

        – BigDecimal和所有的数值型对应的包装类。

        – Character按UNICODE值进行比较。

        – Boolean按true大于false比较。

        – String按字符串中字符的UNICODE值进行比较。

        – Date、Time类,后面的日期时间比前面的大。

    自然排序:

        TreeSet会调用集合元素的compareTo(Object
o)方法来比较元素之间的大小关系,然后将集合元素按升序排序,即为自然排序。

        如果试图把一个对象添加到TreeSet时,该对象的类必须实现Comparable接口。如果对象的类未实现Comparable接口,那么在加入元素和取出元素时,程序将会抛出ClassCastException异常。

       
注意:如果TreeSet集合存储了可变类,对某一个元素的更改致使集合中出现两个相同的元素,则未被修改的和修改以后的元素均不能被成功删除。只有删除其他未被修改的元素,并且TreeSet对元素重新索引之后,发生重复的元素才可以被删除。

    定制排序:

        创建TreeSet对象时传入一个Comparator实现类的对象,并且重写了int
compare(T o1, T o2)方法。此时对象的类无须实现Comparable接口。

    TreeSet判断两个元素相等的标准:

        两个对象通过compareTo(Object o)方法比较返回0。

    TreeSet重写equals和compareTo方法的规则:

       
如果两个对象通过equals方法比较返回true时,这两个对象通过compareTo方法比较应返回0。

五、性能测试比较

针对上面三种Set集合,我们对它们的Add方法进行性能测试:

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Random;
import java.util.TreeSet;

class Bird implements Comparable<Bird>
{
    int size;

    public Bird(int s)
    {
        size = s;
    }

    public String toString()
    {
        return size + "号鸟";
    }

    @Override
    public int compareTo(Bird o)
    {
        return size - o.size;
    }

}
public class Set
{
    public static void main(String[] args)
    {
        Random r = new Random();

        HashSet<Bird> hashSet = new HashSet<Bird>();
        TreeSet<Bird> treeSet = new TreeSet<Bird>();
        LinkedHashSet<Bird> linkedSet = new LinkedHashSet<Bird>();

        // start time
        long startTime = System.nanoTime();

        for (int i = 0; i < 1000; i++) {
            int x = r.nextInt(1000 - 10) + 10;
            hashSet.add(new Bird(x));
        }
        // end time
        long endTime = System.nanoTime();
        long duration = endTime - startTime;
        System.out.println("HashSet: " + duration);

        // start time
        startTime = System.nanoTime();
        for (int i = 0; i < 1000; i++) {
            int x = r.nextInt(1000 - 10) + 10;
            treeSet.add(new Bird(x));
        }
        // end time
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("TreeSet: " + duration);

        // start time
        startTime = System.nanoTime();
        for (int i = 0; i < 1000; i++) {
            int x = r.nextInt(1000 - 10) + 10;
            linkedSet.add(new Bird(x));
        }
        // end time
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("LinkedHashSet: " + duration);
    }
}

Run一下,可以在控制台中看出:

HashSet: 2610998
TreeSet: 3195378
LinkedHashSet: 2673782

可见,TreeSet因为需要进行比较,所以性能比较差。

Queue

  • Queue用于模拟队列,Queue接口定义的方法:add element offer peek poll
    remove
  • Queue有一个PriorityQueue实现类,Deque子接口,Deque有ArrayDeque和LinkedList两个实现类

PriorityQueue实现类

  • 保存队列元素的顺序是按元素大小进行排列,peek取出的是队列中最小的元素,不能插入null
  • PriorityCity的toString()返回值影响看不到顺序输出
  • 自然排序,实现Comparable接口,且元素应是同一个类的多个实例
  • 定制排序,传入Comparator对象,不要求实现Comparable接口

Deque接口

  • Deque是Queue的子接口,代表双端队列,定义了一些双端队列的方法还提供了pop
    push,也可以当作栈来使用
  • Iterator
    descendingIterator()返回一个双端队列对应的迭代器,逆向顺序迭代队列中的元素
  • Deque接口提供了一个典型的实现类ArrayDeque,基于数组实现的双端队列,同样可指定一个numElements,指定数组长度,不指定时默认16,提供了push
    peek pop方法
  • ArrayDeque也可以作为队列使用,取决于使用的方法

LinkedList

  • 同时实现了List和Deque,可以根据索引随机访问集合的元素,可以被当成双端队列使用,可以做栈也可以做队列
  • LinkedList内部以链表的形式存储集合元素,随机访问性能较差,但是插入删除元素的性能较好

线性表的性能分析

  • List是一个线性表接口,ArrayList和LinkedList是线性表的两个典型实现,一个是基于数组的,一个是基于链表的。Queue代表队列,Deque代表双端队列。
  • 总体来说ArrayList比LinkedList性能好,大部分时候应该考虑用ArrayList
  • 使用List集合的建议
    • 遍历List,对于ArrayList、Vector集合应该是用随机访问(get)来遍历,对于LinkedList应该采用迭代器(Iterator)来遍历
    • 经常插入删除元素应使用LinkedList,ArrayList和Vector经常重新分配内部数组大小性能较差
    • 多线程应考虑使用Collections包装成线程安全的集合,而不是去用古老的集合

10.5 EnumSet类

        EnumSet是专门为枚举设计的集合类,EnumSet中的所有元素必须为指定枚举类型的枚举值。EnumSet按枚举值在枚举类中的定义顺序对集合元素进行排序。

       
EnumSet内部以位向量的形式进行存储。数据存储紧凑且高效,占用内存小,运行效率好。

        Enum集合不允许加入null元素

    EnumSet类提供如下类方法来创建对象(未提供构造器):

        – EnumSet allOf(Class
enumType):创建一个包含指定枚举类所有枚举值的集合。

        – EnumSet complementOf(EnumSet
s):创建一个EnumSet相对枚举类为补集的集合。

        – EnumSet copyOf(Collection
c):根据只包含相同枚举类枚举值的普通集合来创建。

        – EnumSet copyOf(EnumSet
s):根据EnumSet集合来创建,两个集合有相同的枚举值。

        – EnumSet noneOf(Class
enumType):创建一个类型为指定枚举类的空集合。

        – EnumSet of(E first/E…
rest):创建一个包含一个或多个枚举值的集合。

        – EnumSet range(E from, E
to):根据枚举类中form到to之间的枚举值创建集合,包含两边值。

六、总结

HashSet:equlas hashcode

LinkedHashSet:链式结构

TreeSet:比较,Comparable接口,性能较差

Map集合

  • Map用于保存具有映射关系额数据,键值对,key不允许重复,key童工equals方法比较
  • 键值一一对应,Map中所有的key组成了一个Set集合,Map的实现类和子接口中的key集存储形式和对应的Set集合元素的存储形式完全相同
  • Java先实现了Map,然后通过包装一个所有value都为null的Map实现了Set集合
  • Map常用方法:clear containsKey containsValue entrySet get isEmpty
    keySet put putAll remove size values
  • Map中有一个内部类Entry,封装了一个键值对,提供了三个方法:getKey
    getValue setValue
  • 如果添加的键值对key重复,新添加的value将会覆盖原来的
  • 所有的Map实现类都重写了toString()
  • Java8新增Map方法:compute computeIfAbsent computeIfPresent forEach
    getOrDefault merge putIfAbsent replace replaceAll

HashMap和Hashtable

  • Hashtable是一个古老的Map实现类,线程安全,,不允许null作为key和value
  • HashMap线程不安全,可以null作为key和value
  • HashMap和Hashtable的元素对象必须实现hashCode()和equals()并保证结果一致
  • 当修改了作为key的可变对象,会出现和HashSet类似的情形,所以尽量不要使用可变对象,尽量不要修改可变对象
  • LinkedHashMap,HashMap的子类,用双向链表来维护键值对的次序,与插入顺序保持一致
  • Properties是Hashtable的子类,在处理属性文件时比较方便,相当于一个键值都是String的Map,getProperty
    setProperty load store

SortedMap接口和TreeMap实现类

  • Map接口有子接口SortedMap,TreeMap为其实现类
  • TreeMap时红黑数据结构,每个键值对为一个红黑树节点,同样的两种排序方式,自然排序和定制排序,规则同TreeSet
  • TreeMap提供的访问键值对的方法:firstEntry firstKey lastEntry lastKey
    higherEntry higherKey lowerEntry lowerKey subMap tailMap headMap

WeakHashMap实现类

  • key只保留了对实际对象的弱引用,所以key所引用的对象没有被其他强引用变量所引用,就有可能会被垃圾回收,WeakHashMap也可能自动删除这些键值对
  • 如果需要使用弱引用,就不要让key引用的对象具有任何强引用,否则失去了使用WeakHashMap的意义

IdentityHashMap实现类

  • key相等标准为key1==key2严格相等才认为是相等的
  • 允许null作为key和value,不保证顺序

EnumMap实现类

  • EnumMap的key都必须是单个枚举类的枚举值,创建EnumMap时需要显式或隐式指定它对应的枚举类
  • 在内部以数组形式保存,根据key在枚举类中的定义顺序维护键值对顺序,不允许null作为key,但可以作为value

Map实现类性能分析

  • Hashtable和HashMap实现机制几乎一样,由于Hashtable比较古老且线程安全,所以通常比HashMap慢
  • TreeMap更慢,但是总处于有序状态,可以调用keySet()再使用toArray()生成key的数组,再使用Arrays的binarySearch()再排序的数组中快速地查询对象
  • 一般应该多考虑使用HashMao,需要排序好的考虑用TreeMap
  • LinkedHashMap比HashMap慢,EnumMap性能最好

10.6 各Set类的性能分析

        HashSet的性能总是比TreeSet好,只有当需要一个保持排序的Set是,才考虑使用TreeSet。
LinkedHashSet在插入删除时,性能比HashSet差,但遍历元素时却更快。EnumSet是所有集合中性能最好的,但是只能保存同一枚举类中的枚举值。

        HashSet、TreeSet、EnumSet都是线程不安全的。

HashSet和HashMap性能选项

  • hash表中桶只有一个元素时有最好的性能,多个元素时以链表形式储存在一个桶里,按顺序搜索(hash冲突)
  • hash表的负载影子达到负载极限时,hash表胡自动成倍增加桶地数量,将原有对象重新分配,放入新桶内,rehashing
  • 负载极限默认0.75,折中时间和控件成本地开销,所占内存和查询开销

Collections工具类

  • 对List集合地排序操作的类方法:reverse shuffle sort swap rotate
  • 用于查找替换操作的类方法:binarySearch(保证List处于有序状态) max min
    fill frequency indexOfSubList replaceAll
  • 同步控制的类方法:synchronizedXxx()将指定集合包装成线程同步的集合
    xxx c = Collections.synchronizedXxx(new XxxXxx());
  • 设置不可变集合的类方法:emptyXxx singletonXxx
    unmodifiableXxx,返回值为集合的只读版本

Enumeration接口

  • Enumeration时Iterator的古老版本,hasMoreElements nextElement
  • 只有Vector Stack Hashtable BitSet这些古老的集合类支持Enumeration
You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图