Java 集合框架（8）---- 总结

指点

发布于 2019-01-18 15:07:24

5650

发布于 2019-01-18 15:07:24

前言

在之前的文章中我们介绍了一下 Java 集合框架中的一些类并对一些常用的类的源码和设计理念进行了解析。那么在这篇文章中我们来将之前介绍过的一些集合类做个总结，并补充一些没有涉及到的知识点。我们从几个不同的角度来进行分类。在此之前我们来看看整个 Java 集合框架的类图：

接下来根据不同的分类角度来进行分类，首先是按集合类别：

集合类别

线性集合类

说到线性集合类我们脑海里第一个想到的基本上都是 ArrayList ，确实，这个类太常用了，当然除了这个类，Java 集合框架中还有一些其他的有用的线性集合类，我们来一一看一下

ArrayList

具体的解析可以参考：ArrayList

这里直接说结论了：ArrayList 内部通过数组来保存元素，默认初始容量为 10，之后以 1.5 倍进行扩容。每次扩容时新建一个新的数组，然后将原数组中的元素复制到新数组中（直接复制引用），之后将原数组中的元素清除，数组引用指向新的数组。插入元素和删除元素的时间复杂度都是 O(n)，获取元素的时间复杂度为 O(1)， ArrayList 是非线程安全的类。

LinkedList 、Queue、Deque

具体的解析可以参考： LinkedList

LinkedList 内部以双向链表的结构来保存元素，每一个元素都是一个双向链表节点。每次来一个元素，就新建一个链表节点并将这个节点插入当前的双向链表尾部，时间复杂度为 O(1)。删除元素的时候也是通过要删除元素的值来找到对应的链表节点，之后将这个链表节点从双向链表中移除，寻找链表节点的时间复杂度为 O(n)，删除节点的时间复杂度为 O(1)，因此整个删除节点的时间复杂度为 O(n)。此外，因为 LinkedList 实现了 Deque 接口，因此也可以将其作为队列/双端队列使用。最后， LinkedList 也是非线程安全的类。

Vector

具体解析可以参考：Vector

Vector 和 ArrayList 类似，内部都是采用数组来保存元素，而其与 ArrayList 最大的区别在于 Vecotr 是线程安全的类。因此，如果需要用线程安全的线性结构，可以采用 Vecotor ，也可以采用其他的方法（后文介绍）。

Stack

具体的解析可以参考：Stack

该类继承自 Vector，因此也是线程安全的类，其提供了 “栈” 这种数据结构的一些操作元素 API，入栈、出栈、取栈顶元素等。

映射集合类

同样的，说到映射集合类（Map），脑海里面第一个想到的就是 HashMap，这个类也算是我们最常用的一个类之一了，当然也还有其他的一些有用的映射类，我们来看看：

HashMap

具体解析可以参考：HashMap

HashMap 提供了一种高效的两种数据之间的映射能力。内部提供了一个 table 表，其实就是数组，不过数组元素为自定义的实现了 Map.Entry 接口的对象。Map.Entry 就描述了一个完整的键值对对象。通过键的 hash 值来决定当前键值对元素所在的数组下标。其默认的初始元素容量为 16，扩容因子默认为 0.75，当容量达到当前最大容量 * 扩容因子的值时，进行扩容。每次扩容的时候容量翻倍。这样保证每次进行键值对进行 hash 时可以通过位运算来代替取余操作（防止得到的数组下标越界），提高效率。当出现 hash 值冲突的时候，先采用链地址法处理（使用单链表将冲突的元素连接），当某个冲突链表的长度不小于 8 时，将其树化（转换为红黑树，加快查找速度）。 HashMap 是非线程安全的类。

TreeMap

具体的解析可以参考：TreeMap

同 HashMap 一样，TreeMap 也是提供了一种数据之间的的映射能力，但是这里并没有用高效来形容它，是因为同 HashMap 相比，它的效率还是略低，因为其还提供对键排序的功能，我们在遍历 TreeMap 的时候，元素的遍历顺序已经是根据某种规则排序后的序列，为了达成这种功能，其内部借助了一种平衡二叉树（红黑树）的数据结构来实现。当我们在插入新的元素的时候，其依据定义的排序规则来找到合适的位置进行插入。所以其插入元素的过程是来一个插一个，所以在 TreeMap 中并没有初始容量和扩容的概念。而插入、删除、查询等操作的时间复杂度为 O(logn)。n 为树中的节点总数，即为元素总数。

LinkedHashMap

具体解析可以参考：LinkedHashMap

我们知道 HashMap 在遍历时的元素顺序和插入时的元素顺序是不一定相同的，那么有时候我们可能有这种需求，即使得遍历时的元素顺序和插入时一致，此时我们就可以考虑使用 LinkedHashMap，因为 LinkedHashMap 是继承于 HashMap 的，只不过为了维护元素顺序和插入时的保持一致，LinkedHashMap 在 HashMap 节点的基础上增加了指向前驱和后继节点的引用，也就是通过双向链表来维护元素的顺序。而同时留有一些扩展方法，一些缓存算法（LRU）就可以通过 LinkedHashMap 来轻松实现。

WeakHashMap

具体解析可以参考：WeakHashMap

由于弱引用（详解 Java 的四种引用）的出现，使得 WeakHashMap 可以做到保证其所引用的元素不会导致 OutofMemoryError 异常。同 HashMap 一样， WeakHashMap 内部也是通过数组来储存元素的，WeakHashMap 默认的初始容量是 16，最大容量为 1 << 30 ；默认扩容因子为 0.75；可以指定初始容量，但是处理过后的初始容量一定是 2 的次幂，好处是可以通过 & 运算来代替 % 运算提高效率；每次扩容时容量翻倍。节点（Entry）之间利用单项链表之间来处理 hash 值冲突。

Hashtable

具体解析可参考：Hashtable

和 HashMap 类似，不过其是线程安全的类，其实也就是在每个操作元素的方法前加入 synchronized 关键字修饰，效率不高，我们完全有更好的方法来代替这个，同时具体的扩容机制和 HashMap 也略有不同：默认初始容量为 11，扩容因子为 0.75，每次扩容后的容量变为之前容量的 2 倍 + 1。这个类已经被标为 Legacy（遗留类），即不被推荐使用。关于其的替代，后面将会介绍。

IdentifyHashMap

具体解析可参考：IdentifyHashMap

之前介绍的 Map 都是通过具体元素的 key 的 equals 方法来判断元素等价，而这个 Map 中则是通过最原始的方法（Object 的 equals 方法）来判断，即如果两个对象不是同一个对象，即使其内部属性值相同，那么也被当做不等价。其内部通过一个 Object 类型的数组来储存元素，即键值都用这个数组储存，键所在的下标是偶数（0、2、4…），值所在的下标是对应的键下标 + 1。同时，存入元素也按照相同的规则。如果 当前元素个数 * 3 > table.length（包括了键和值）。那么进行扩容，扩容是数组容量翻倍。table 数组的最大容量是 1 << 30，默认初始容量为 32。

一般集合类

为了统一，这里给它起了个名字叫一般集合类，其实就是 Set 了。

因为集合类内部都是借助了对应的 Map 来进行实现，所以理解了 Map 接口的相关具体类，Set 的相关类就非常简单了。这里用一篇文章总结了一下 Set 接口下的具体类：Java 集合框架（7）.

HashSet

内部通过 HashMap 实现，效率较高。但是元素取出的顺序和存入的顺序不一定相同

TreeSet

内部通过 TreeMap 实现，将元素按照一定规则排序，取出的元素顺序是按照某个规则排好序的。这个排序规则可以在创建 TreeSet 对象的时候通过参数传入，或者存入的元素类型实现 Comparable 接口。

LinkedHashSet

内部通过 LinkedHashMap 实现，可以实现元素取出的顺序和存入的顺序相同

线程安全分类

下面按照线程安全来对各个集合类进行介绍，同时会介绍一些之前提到过的一些其他的集合类

非线程安全的集合类：

ArrayList、LinkedList、Queue、Deque （Queue 和 Deque 是两个接口，其实现是 LinkedList，所以也是非线程安全的）。

HashMap、TreeMap、LinkedHashMap、WeakHashMap、IdentifyHashMap

HashSet、TreeMap、LinkedHashSet

线程安全的集合类：

Vector、Stack、 CopyOnWriteArrayList（JDK 1.5）

Hashtable、ConcurrentHashMap（JDK 1.5）

上面说的 HashSet、TreeMap、LinkedHashSet 都是非线程安全的，那么我们就没有线程安全的 Set 集合用吗，其实并不是，这里有两种方法来解决这个问题：

1、我们已经知道 Set 集合内部都是通过对应的 Map 实现的，那么我们自定义一个 Set 集合类，内部用一个线程安全的 Map 来实现不就行了吗。对于具体的实现，可以参考下面的代码：

public class ThreadSafeSet<E> extends AbstractSet<E> implements Set<E> {
    private static int DEFAULT_INIT_CAPACITY = 16;
    private static float DEFAULT_LOAD_FACTOR = 0.7F;
    private static Object VALUE = new Object();

    private ConcurrentMap<E, Object> concurrentMap;

    public ThreadSafeSet() {
        this(DEFAULT_INIT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public ThreadSafeSet(int initCapacity, float loadFactor) {
        concurrentMap = new ConcurrentHashMap<>(DEFAULT_INIT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    @Override
    public int size() {
        return concurrentMap.size();
    }

    @Override
    public boolean isEmpty() {
        return concurrentMap.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        return concurrentMap.containsKey(o);
    }

    @Override
    public Iterator<E> iterator() {
        return concurrentMap.keySet().iterator();
    }

    @Override
    public boolean add(Object e) {
        return concurrentMap.put((E) e, VALUE) == null;
    }

    @Override
    public boolean remove(Object o) {
        return concurrentMap.remove(o) != null;
    }
}

2、除了上面的方式外，在集合工具类 Collections 中已经提供了一些方法来创造一些线程安全的集合：

可以看到，这里面有一些以 synchronized 开头的方法名，接受的参数也是有 List、Map、Set 等集合，这些方法就可以返回一些线程安全的集合，我们随便挑一个方法来看：

public static <T> Set<T> synchronizedSet(Set<T> s) {
    return new SynchronizedSet<>(s);
}

这里直接返回了一个 SynchronizedSet 对象，这个类继承于 SynchronizedCollection 类，我们来看看这个类：

/**
  * @serial include
  */
static class SynchronizedCollection<E> implements Collection<E>, Serializable {
    private static final long serialVersionUID = 3053995032091335093L;

    final Collection<E> c;  // Backing Collection
    final Object mutex;     // Object on which to synchronize

    SynchronizedCollection(Collection<E> c) {
        this.c = Objects.requireNonNull(c);
        mutex = this;
    }

    SynchronizedCollection(Collection<E> c, Object mutex) {
        this.c = Objects.requireNonNull(c);
        this.mutex = Objects.requireNonNull(mutex);
    }

    public int size() {
        synchronized (mutex) {return c.size();}
    }
    public boolean isEmpty() {
        synchronized (mutex) {return c.isEmpty();}
    }
    public boolean contains(Object o) {
        synchronized (mutex) {return c.contains(o);}
    }
    public Object[] toArray() {
        synchronized (mutex) {return c.toArray();}
    }
    public <T> T[] toArray(T[] a) {
        synchronized (mutex) {return c.toArray(a);}
    }

    public Iterator<E> iterator() {
        return c.iterator(); // Must be manually synched by user!
    }

    public boolean add(E e) {
        synchronized (mutex) {return c.add(e);}
    }
    public boolean remove(Object o) {
        synchronized (mutex) {return c.remove(o);}
    }

    public boolean containsAll(Collection<?> coll) {
        synchronized (mutex) {return c.containsAll(coll);}
    }
    public boolean addAll(Collection<? extends E> coll) {
        synchronized (mutex) {return c.addAll(coll);}
    }
    public boolean removeAll(Collection<?> coll) {
        synchronized (mutex) {return c.removeAll(coll);}
    }
    public boolean retainAll(Collection<?> coll) {
        synchronized (mutex) {return c.retainAll(coll);}
    }
    public void clear() {
        synchronized (mutex) {c.clear();}
    }
    public String toString() {
        synchronized (mutex) {return c.toString();}
    }
    // Override default methods in Collection
    @Override
    public void forEach(Consumer<? super E> consumer) {
        synchronized (mutex) {c.forEach(consumer);}
    }
    @Override
    public boolean removeIf(Predicate<? super E> filter) {
        synchronized (mutex) {return c.removeIf(filter);}
    }
    @Override
    public Spliterator<E> spliterator() {
        return c.spliterator(); // Must be manually synched by user!
    }
    @Override
    public Stream<E> stream() {
        return c.stream(); // Must be manually synched by user!
    }
    @Override
    public Stream<E> parallelStream() {
        return c.parallelStream(); // Must be manually synched by user!
    }
    private void writeObject(ObjectOutputStream s) throws IOException {
        synchronized (mutex) {s.defaultWriteObject();}
    }
}

可以看到，这里面对元素操作的方法全都用了 synchronized 关键字修饰，而本身也只是调用了对应类的对应方法，所以说 Collections 类中为我们准备的线程安全的集合类就是把相关的方法都用 synchronized 关键字修饰了一下以保证线程安全。接下来看看 SynchronizedSet：

/**
  * @serial include
  */
static class SynchronizedSet<E> extends SynchronizedCollection<E> implements Set<E> {
    private static final long serialVersionUID = 487447009682186044L;

    SynchronizedSet(Set<E> s) {
        super(s);
    }
    SynchronizedSet(Set<E> s, Object mutex) {
        super(s, mutex);
    }

    public boolean equals(Object o) {
        if (this == o)
            return true;
        synchronized (mutex) {return c.equals(o);}
    }
    public int hashCode() {
        synchronized (mutex) {return c.hashCode();}
    }
}

这个类里面没有多余的元素操作的方法，因为 Set 集合中的操作元素的方法都已经被其父类 SynchronizedCollection 涵盖了。那么对于其余的集合类也是一样的道理。

其实 Collections 类是 Java 集合框架的类库，里面有很多的集合相关操作的方法（排序、二分查找、逆转元素顺序等），于此对应的还有一个类：Arrays，也是一个工具类库，与 Collections 不同的是 Arrays 更多的是针对数组和线性集合，而 Collestions 针对的更多是集合框架中的类。

好了，关于 Java 中的集合框架到这里就告一段落了。其实在 java.util.concurrent 包中还有一些具有线程安全的集合，我们已经看过了 ConcurrentHashMap，其余的由于不太常用（对我来说，因为我主要是 Android 开发），这里就不细讲了，有兴趣的小伙伴可以去看看里面的一些类。到这里 Java 集合框架系列就结束了，如果以后有新的体会再来补充吧如果觉得本系列对您有帮助，请不要吝啬您的赞。如果觉得文章中有什么不正确的地方，还请多多指点。下个系列应该会是关于 Java 类体系的专题，里面会有一些令人期待的新知识点。那么下个系列再见～

谢谢观看。。。

我的博客即将搬运同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=3o2apkp87k2sc

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019年01月01日，如有侵权请联系 cloudcommunity@tencent.com 删除

java

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

java

登录后参与评论

0 条评论

热度