04 java 集合框架汇总及使用场景

2019-07-05  本文已影响0人  花神子

首先了解下Java提供的集合类的顶级接口，主要存在两个体系：Collection接口和Map接口

Collection接口

Collection

Collection是最基本的集合接口，Collection接口抽象的定义了集合的基本操作：

public interface Collection<E> extends Iterable<E> {
    // Query Operations

    int size();

    boolean isEmpty();

    boolean contains(Object o);

    Iterator<E> iterator();

    Object[] toArray();

    <T> T[] toArray(T[] a);

    // Modification Operations
    boolean add(E e);

    boolean remove(Object o);

    // Bulk Operations
    boolean containsAll(Collection<?> c);

    boolean addAll(Collection<? extends E> c);

    boolean removeAll(Collection<?> c);

    /**
     * @since 1.8
     */
    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }
    ...
}

Map接口

Map接口 储存一组成对的键-值对象,提供key(键)到value(值)的映射,Map中的key不要求有序,不允许重复.value同样不要求有序,但可以重复。

public interface Map<K,V> {
    // Query Operations

    int size();

    boolean isEmpty();

    boolean containsKey(Object key);

    boolean containsValue(Object value);

    V get(Object key);

    // Modification Operations
    V put(K key, V value);

    V remove(Object key);

    // Bulk Operations
    void putAll(Map<? extends K, ? extends V> m);

    void clear();

    // Views
    Set<K> keySet();

    Collection<V> values();

    Set<Map.Entry<K, V>> entrySet();

    ...

    boolean equals(Object o);

    int hashCode();

    ...
}

List类集合

List接口继承自Collection，用于定义以列表形式存储的集合，List接口为集合中的每个对象分配了一个索引(index)，标记该对象在List中的位置，并可以通过index定位到指定位置的对象。

List在Collection基础上增加的主要方法包括：

List接口的常用实现类：

ArrayList

ArrayList基于数组来实现集合的功能，其内部维护了一个可变长的对象数组，集合内所有对象存储于这个数组中，并实现该数组长度的动态伸缩.

ArrayList使用数组拷贝来实现指定位置的插入和删除：

LinkedList

LinkedList基于链表来实现集合的功能，其实现了静态类Node，集合中的每个对象都由一个Node保存，每个Node都拥有到自己的前一个和后一个Node的引用.

LinkedList-insert
ArrayList vs LinkedList

Vector

Vector和ArrayList很像，都是基于数组实现的集合，它和ArrayList的主要区别在于

CopyOnWriteArrayList

与 Vector一样，CopyOnWriteArrayList也可以认为是ArrayList的线程安全版，不同之处在于 CopyOnWriteArrayList在写操作时会先复制出一个副本，在新副本上执行写操作，然后再修改引用。这种机制让 CopyOnWriteArrayList可以对读操作不加锁，这就使CopyOnWriteArrayList的读效率远高于Vector。 CopyOnWriteArrayList的理念比较类似读写分离，适合读多写少的多线程场景。但要注意，CopyOnWriteArrayList只能保证数据的最终一致性，并不能保证数据的实时一致性，如果一个写操作正在进行中且并未完成，此时的读操作无法保证能读到这个写操作的结果。

Map类集合

Map将key和value封装至一个叫做Entry的对象中，Map中存储的元素实际是Entry。只有在keySet()和values()方法被调用时，Map才会将keySet和values对象实例化。

HashMap

HashMap将Entry对象存储在一个数组中，并通过哈希表来实现对Entry的快速访问：

HashMap

Hashtable

Hashtable 可以说是HashMap的前身（Hashtable自JDK1.0就存在，而HashMap乃至整个Map接口都是JDK1.2引入的新特性），其实现思 路与HashMap几乎完全一样，都是通过数组存储Entry，以key的哈希值计算Entry在数组中的index，用拉链法解决哈希冲突。二者最大的不同在于，Hashtable是线程安全的，其提供的方法几乎都是同步的。

ConcurrentHashMap

ConcurrentHashMap是HashMap的线程安全版（自JDK1.5引入），提供比Hashtable更高效的并发性能。
JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，

1.JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）

2.JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了 3.JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档

4.JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock，我觉得有以下几点

1.因为粒度降低了，在相对而言的低粒度加锁方式，synchronized并不比ReentrantLock差，在粗粒度加锁中         ReentrantLock可能通过Condition来控制各个低粒度的边界，更加的灵活，而在低粒度中，Condition的优           势就没有了

2.JVM的开发团队从来都没有放弃synchronized，而且基于JVM的synchronized优化空间更大，使用内嵌的           关键字比使用API更加自然

3.在大量的数据操作下，对于JVM的内存压力，基于API的ReentrantLock会开销更多的内存，虽然不是瓶             颈，但是也是一个选择依据

HashMap vs Hashtable vs ConcurrentHashMap

LinkedHashMap

LinkedHashMap与HashMap非常类似，唯一的不同在于前者的Entry在HashMap.Entry的基础上增加了到前一个插入和后一个插入的Entry的引用，以实现能够按Entry的插入顺序进行遍历。

TreeMap

TreeMap是基于红黑树实现的Map结构，其Entry类拥有到左/右叶子节点和父节点的引用，同时还记录了自己的颜色：


static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left = null;
        Entry<K,V> right = null;
        Entry<K,V> parent;
        boolean color = BLACK;
 
}

ConcurrentSkipListMap

ConcurrentSkipListMap同样能够提供有序的Entry排列，但其实现原理与TreeMap不同，是基于跳表(SkipList)的.
ConcurrentSkipListMap由一个多级链表实现，底层链上拥有所有元素，逐级上升的过程中每个链的元素数递减。在查找时从顶层链出发，按先右后下的优先级进行查找，从而实现快速寻址。

static class Index<K,V> {
        final Node<K,V> node;
        final Index<K,V> down;//下引用
        volatile Index<K,V> right;//右引用
}

TreeMap vs ConcurrentSkipListMap

Set类集合

Set 接口继承Collection，用于存储不含重复元素的集合。几乎所有的Set实现都是基于同类型Map的，简单地说，Set是阉割版的Map。每一个Set内都有一个同类型的Map实例（CopyOnWriteArraySet除外，它内置的是CopyOnWriteArrayList实例），Set把元素作为key存储在自己的Map实例中，value则是一个空的Object。Set的常用实现也包括 HashSet、TreeSet、ConcurrentSkipListSet等，原理和对应的Map实现完全一致.

Queue/Deque类集合

Queue和Deque接口继承Collection接口，实现FIFO（先进先出）的集合。二者的区别在于，Queue只能在队尾入队，队头出队，而Deque接口则在队头和队尾都可以执行出/入队操作

Queue接口常用方法：

Deque接口常用方法：

Queue接口的常用实现类：

ConcurrentLinkedQueue

ConcurrentLinkedQueue是基于链表实现的队列，队列中每个Node拥有到下一个Node的引用：

private static class Node<E> {
        volatile E item;
        volatile Node<E> next;
}

由于Node类的成员都是volatile的，所以ConcurrentLinkedQueue自然是线程安全的。能够保证入队和出队操作的原子性和一致性，但在遍历和size()操作时只能保证数据的弱一致性。

LinkedBlockingQueue

与ConcurrentLinkedQueue不同，LinkedBlocklingQueue是一种无界的阻塞队列。所谓阻塞队列，就是在入队时如果队列已满，线程会被阻塞，直到队列有空间供入队再返回；同时在出队时，如果队列已空，线程也会被阻塞，直到队列中有元素供出队时再返回。LinkedBlocklingQueue同样基于链表实现，其出队和入队操作都会使用ReentrantLock进行加锁。所以本身是线程安全的，但同样的，只能保证入队和出队操作的原子性和一致性，在遍历时只能保证数据的弱一致性。

ArrayBlockingQueue
ArrayBlockingQueue是一种有界的阻塞队列，基于数组实现。其同步阻塞机制的实现与LinkedBlocklingQueue基本一致，区别仅在于前者的生产和消费使用同一个锁，后者的生产和消费使用分离的两个锁。

ConcurrentLinkedQueue vsLinkedBlocklingQueue vs ArrayBlockingQueue

SynchronousQueue

SynchronousQueue算是JDK实现的队列中比较奇葩的一个，它不能保存任何元素，size永远是0，peek()永远返回null。向其中插入元素的线程会阻塞，直到有另一个线程将这个元素取走，反之从其中取元素的线程也会阻塞，直到有另一个线程插入元素。

这种实现机制非常适合传递性的场景。也就是说如果生产者线程需要及时确认到自己生产的任务已经被消费者线程取走后才能执行后续逻辑的场景下，适合使用SynchronousQueue。

PriorityQueue & PriorityBlockingQueue

上一篇 下一篇

猜你喜欢

热点阅读