1.7源码阅读-Java集合

作者: czn5991 | 来源:发表于2019-03-02 14:44 被阅读0次

Java集合提供了存储数据和对象的类，其主要的关系如下图。

集合类关系图.gif
Collection和Map为其中两个主要的接口，定义了两种存储数据的方式。Collection直接存储数据，而Map通过键值对来存储数据。下面是这两个接口定义的方法。

public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    //保留集合C中的元素，删除其他元素
    boolean retainAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
}

public interface Map<K,V> {
    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    V get(Object key);
    V put(K key, V value);
    V remove(Object key);
    void putAll(Map<? extends K, ? extends V> m);
    void clear();
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
    boolean equals(Object o);
    int hashCode();
    interface Entry<K,V> {
        K getKey();
        V getValue();  
        V setValue(V value);
        boolean equals(Object o);
        int hashCode();
    }
}

不难发现Collection和Map定义的方法十分相似，其中主要不同的有Map中定义了一个键值对的接口Entry<K,V>，以及Map不支持Iterator和toArray()方法。

1 List

List继承了Collection的接口，除了Collection定义的方法外，List接口中新增了下面的这些方法。Collection中已定义了Iterator，而List中增加了ListIterator，在原Iterator的基础上增加了向前遍历、增加的方法，更加实用，可以说是能用ListIterator就不用Iterator。

public interface List<E> extends Collection<E> {
    //Collection中已实现的方法不再赘述

    E get(int index);
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);
    int indexOf(Object o);
    int lastIndexOf(Object o);
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    List<E> subList(int fromIndex, int toIndex);
}

AbstractList类实现继承了AbstractCollection类，实现了List接口，其中AbstractCollection类实现了Collection中定义的部分方法。
AbstractList除了实现了List中定义的一些方法外，更主要的是具体实现了Iterator和ListIterator这两个私有类和SubList快照。

AbstractList的实现类有ArrayList、LinkedList、Vector，其特点是有序，可重复。

ArrayList

ArrayList继承了AbstractList，实现了List、RandomAccess、Cloneable、java.io.Serializable接口。。
ArrayList使用数组对数据进行存储，定义了EMPTY_ELEMENTDATA。

private static final Object[] EMPTY_ELEMENTDATA = {};

当创建了ArrayList对象且还未存入任何数据时，存储数据的数组Object[] elementData还未实现，只有第一次存入数据时才真正的为该数组申请内存空间。
ArrayList重写了AbstractList中的方法，实现方式并不复杂，其中比较值得学习的一点是源码中将重复的简短代码也进行了函数包装，使得阅读代码非常容易。

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

此外，ArrayList实现了对数elementData数组进行扩充的方法，当数组容量不够时，会将容量增加到原来的1.5倍并将原数组中的元素拷贝到新数组中。

ArrayList重新实现了快照，即私有类SubList，可以通过subList(fromIndex,toInex)获得。该私有类实现了ArrayList的所有方法，并且在该对象引用上的操作会直接影响原ArrayList。当获得了一个ArrayList的快照时，不能修改原ArrayList，否则会产生fast-fail错误。（详见http://cmsblogs.com/?p=1220）
该错误主要目的是为了防止多个线程通过迭代器操作同一ArrayList时，一个线程对其修改导致了另一线程的操作产生不符合目的的结果。其实现的机制是在ArrayList中存在 modCount变量，存储该ArrayList被修改容量的次数。当通过Iterator或SubList对ArrayList进行修改时，判断modCount是否复合预期值（值在操作该ArrayList前将其保存）。

Vector

Vector与ArrayList的实现方式基本相同，都是通过数组来实现，其主要的区别在于Vector是线程同步的，即多个线程操作同一个Vector也是安全的。Vector通过在add()、remove()等对Vector进行修改的方法上使用synchronized进行修饰。因此在大多数情况下，能使用ArrayList就要避免使用Vector，以此来避免系统为了保证线程同步而产生的性能消耗。

LinkedList

LinkedList继承了AbstractSequentialList，实现了List、Deque、Cloneable、java.io.Serializable接口。
AbstractSequentialList继承了AbstractList，但并未增加任何新方法。
LinkedList与ArrayList的主要区别是其使用了链表来存储数据，以及实现了Deque接口，Deque接口中定义的peek()、pop()、push()等方法，可以将其当作栈使用，其栈顶为链表首部，栈底为链表尾部。LinkedList中add()、remove()、contains()等方法的实现方式与ArrayList区别不大。

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
}

2 Set

Set接口继承了Collection接口，但并没有实现或增加任何功能。
AbstractSet继承了AbstractCollection类，实现了Set接口。
AbstractSet主要有HashSet和TreeSet两个子类，其基本实现分别基于HashMap和TreeMap。

HashSet

HashSet在类内创建了一个HashMap和一个Object对象。

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

对于需要放入HashSet的元素，以该元素和PRESENT构建键-值对，存入map中。其中该元素为Key，这样就保证了HashSet中不存在相同的元素，并且可以通过调用HashMap的add()、remove()等方法直接实现其自身的方法。

TreeSet

TreeSet继承了AbstractSet，实现了NavigableSet、Cloneable、java.io.Serializable接口。
SortedSet是一个有序集合的接口，任何存入实现了该接口的类的对象需要实现Comparable接口。
NavigableSet接口继承了SortedSet接口，实现了元素的比较等方法。

public interface NavigableSet<E> extends SortedSet<E> {
    //返回比e小的最大元素
    E lower(E e);
    E higher(E e);
    //返回不比e大的最大元素
    E floor(E e);
    E ceiling(E e);
    //删除并返回最小元素
    E pollFirst();
    E pollLast();
    Iterator<E> iterator();
    NavigableSet<E> descendingSet();
    Iterator<E> descendingIterator();
    //返回视图
    NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                           E toElement,   boolean toInclusive);
    //返回比toElement小的元素（或等于，若inclusive==True）
    NavigableSet<E> headSet(E toElement, boolean inclusive);
    NavigableSet<E> tailSet(E fromElement, boolean inclusive);
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);
}

TreeSet存储数据的方式与HashSet类似，TreeSet默认创建了TreeMap来存储数据，利用键值对保证数据的唯一性。

3 Queue

Queue接口继承了Collection接口，定义了如下方法。

public interface Queue<E> extends Collection<E> {
    boolean add(E e);
    //插入元素
    boolean offer(E e);
    E remove();
    //返回并删除队首
    E poll();
    //返回队首，若不存在则抛出异常
    E element();
    //返回队首，若不存在则返回null
    E peek();
}

这里主要介绍PriorityQueue和ConcurrentLinkedQueue。

PriorityQueue
PriorityQueue继承了AbstractQueue，实现了java.io.Serializable接口。
优先队列使用平衡二叉堆保证了非严格有序地存储数据（仅保证父亲小于儿子），默认的顺序是对象从小到大的顺序，也可以通过自定义比较器来设定数据排序的顺序。

存储
PriorityQueue使用数组对平衡二叉堆进行存储，queue[n]的两个儿子分别是queue[2*n+1]和queue[2*(n+1)]，queue[0]保存了最小的元素。默认的数组大小为11，当数组不够用时，会根据当前数组的大小来扩大。如果当前数组小于64则容量翻倍，否则增加至1.5倍。
```
private transient Object[] queue;
```
修改
当从优先队列删除或增加一个元素时，为了保证堆的性质，需要对元素进行上移或下移。
当增加一个元素时，将该元素插入到末端，然后将其不断上移，直到其父亲的值大于其值；当删除一个元素时，将队列末端的元素插入到该元素的位置，然后通过上移或下移该元素的位置，使得堆仍保持性质。

ConcurrentLinkedQueue
ConcurrentLinkedQueue在类内创建了Node类，该类使用了Unsafe类的compareAndSwap方法实现了线程同步。Node类还使用了和ConcurrentHashMap相同的方法，通过Unsafe类和偏移直接修改JVM。

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

    Node(E item) ;

    boolean casItem(E cmp, E val) {
        return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
    }

    void lazySetNext(Node<E> val) {
        UNSAFE.putOrderedObject(this, nextOffset, val);
    }

    boolean casNext(Node<E> cmp, Node<E> val) {
        return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
    }

    // Unsafe mechanics
    private static final sun.misc.Unsafe UNSAFE;
    private static final long itemOffset;
    private static final long nextOffset;

    static {
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class k = Node.class;
            itemOffset = UNSAFE.objectFieldOffset
                (k.getDeclaredField("item"));
            nextOffset = UNSAFE.objectFieldOffset
                (k.getDeclaredField("next"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }
}

增加
ConcurrentLinkedQueue通过offer()实现了对元素的增加。每次增加时并不立即修改tail，而是当每2次增加后才修改，知道这点后，阅读代码就方便了许多。

public boolean offer(E e) {
    checkNotNull(e);
    final Node<E> newNode = new Node<E>(e);

    for (Node<E> t = tail, p = t;;) {
        Node<E> q = p.next;
        if (q == null) {
            // p is last node
            if (p.casNext(null, newNode)) {
                // 如果是第一次添加的线程，则直接返回
                // 如果是第二次添加的线程，更改tail
                if (p != t) // hop two nodes at a time
                    casTail(t, newNode);  // Failure is OK.如果失败则说明其他线程已经更改了tail
                return true;
            }
            // Lost CAS race to another thread; re-read next
        }
        //如果p==q，说明该结点已经不在队列中，需要重新从头遍历
        else if (p == q)
            p = (t != (t = tail)) ? t : head;
        else
            // Check for tail updates after two hops.
            p = (p != t && t != (t = tail)) ? t : q;
    }
}

删除
poll()方法实现了从队首移除一个元素。和offer()方法一样，每当移除2个元素后才会更改head。

public E poll() {
    restartFromHead:
    for (;;) {
        for (Node<E> h = head, p = h, q;;) {
            E item = p.item;

            if (item != null && p.casItem(item, null)) {
                // 第二个移除元素的线程更改头部
                if (p != h) // hop two nodes at a time
                    updateHead(h, ((q = p.next) != null) ? q : p);
                return item;
            }
            //如果整个队列为空
            else if ((q = p.next) == null) {
                updateHead(h, p);
                return null;
            }
            //如果p结点已经从队列移除，则重新遍历
            else if (p == q)
                continue restartFromHead;
            else
                p = q;
        }
    }
}

4 Map

最常用的两类Map有HashMap和TreeMap。

HashMap

HashMap继承了AbstractMap，实现了Map、Cloneable、java.io.Serializable。
HashMap类中实现了一个Entry<K,V>类来保存每一个键-值对。HashMap通过Entry[]数组来保存所有的键-值对，其中每一个索引称为一个桶（bucket）。

键-值对的存储
Entry[]数组可能包含多个桶，那如何确定某个键-值对应该保存在哪个桶中呢？Java中通过对键取hash并对数组长度取余，将该键-值对存放到余数对应的桶中。

final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
}

最后两行代码被称为扰动函数，这两行代码对原hash值进行了4次异或处理，使每一位与不同的4位进行异或。当原Object的hashCode()方法实现不佳，不同Object对象hashCode()方法的返回值可能会呈等差数列等冲突较多的情况时，使用扰动函数能够将降低冲突，即降低了不同Object对象保存在同一个桶中的可能性。

static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
}

该方法计算了Object的hash对应桶的索引。HashMap中Entry[]数组长度要求是2的指数，这样length-1就是一个低位的掩码，和h进行与操作后，得到的就是余数，即对应的桶。

桶的扩充
当往一个HashMap中存入远超其桶数量的键-值对时，冲突的次数会大幅度增加，因此需要根据数据的多少来动态更改桶的个数。
在初始化HashMap时需要输入负载因子（loadFactor），每当HashMap中的键-值对总数量大于桶个数X负载因子时，HashMap便会使容量X2，并重新放置原键-值对。

HashMap提供了和ListIterator类似的HashIterator，该类是抽象类，其实现类有ValueIterator、KeyIterator、EntryIterator。这几个类均实现了从首桶到尾桶遍历所有元素。
HashMap也提供了和SubList类似的KeySet、Values、EntrySet视图来供使用。

TreeMap

TreeMap继承了AbstractMap，实现了NavigableMap、Cloneable、java.io.Serializable接口。
TreeMap与HashMap的主要不同之处是使用了红黑树存储键值对。

ConcurrentHashMap

ConcurrentHashMap继承了AbstractMap，实现了ConcurrentMap、Serializable接口。

public interface ConcurrentMap<K, V> extends Map<K, V> {
    //如果存在key，则返回对应的value；否则放入key-value
    V putIfAbsent(K key, V value);
    boolean remove(Object key, Object value);
    boolean replace(K key, V oldValue, V newValue);
    //如果key存在，则将value替换
    V replace(K key, V value);
}

Segment
ConcurrentHashMap实现了Segment<K,V>类来代替HashMap中的elementData数组，以实现多线程的并发访问。

static final class Segment<K,V> extends ReentrantLock implements Serializable {
    //以下是Segment实现的方法，申明的变量以及各个方法的具体实现未拷贝
    Segment(float lf, int threshold, HashEntry<K,V>[] tab) ;
    final V put(K key, int hash, V value, boolean onlyIfAbsent) ;
    private void rehash(HashEntry<K,V> node);
    private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value);
    private void scanAndLock(Object key, int hash);
    final V remove(Object key, int hash, Object value);
    final boolean replace(K key, int hash, V oldValue, V newValue);
    final V replace(K key, int hash, V value);
    final void clear();
}

Segment<K,V>类中对外的方法均是线程安全的，使用了可重入锁以保证这一特性。以put()为例。

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    HashEntry<K,V> node = tryLock() ? null :
        scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        //put操作
    } finally {
        unlock();
    }
    return oldValue;
}

在该方法中先使用了tryLock()尝试直接获得锁。如果获得锁，则直接进行操作；否则再调用scanAndLockForPut()方法。

private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
    //得到存储数据的入口
    HashEntry<K,V> first = entryForHash(this, hash);
    HashEntry<K,V> e = first;
    HashEntry<K,V> node = null;
    int retries = -1; // negative while locating node
    while (!tryLock()) {
        HashEntry<K,V> f; // to recheck first below
        //如果重试次数<0
        if (retries < 0) {
            if (e == null) {
                if (node == null) // speculatively create node
                        node = new HashEntry<K,V>(hash, key, value, null);
                retries = 0;
            }
            else if (key.equals(e.key))
                retries = 0;
            else
                e = e.next;
            }
        //如果重试次数超过了上限时（如果jvm允许多线程则为64，否则为1）
        else if (++retries > MAX_SCAN_RETRIES) {
            lock();
            break;
        }
        else if ((retries & 1) == 0 &&
            (f = entryForHash(this, hash)) != first) {
                e = first = f; // re-traverse if entry changed
                retries = -1;
            }
        }
        return node;
}

该方法实现了在不断调用tryLock()的同时遍历该Segment对象中存储的数据，如果遍历一遍后发现不存在该键值对，则创建node并初始化，等到获取锁后再返回。在put()中，获得锁后先遍历一次，若该键值对没有被其他线程添加，则在表中加入node，这样就避免了添加key相同的键值对。这种方法让线程不是傻等锁的释放，而让线程在不断调用tryLock()的同时还遍历了数据，更大程度的榨取了线程的剩余价值。

ConcurrentHashMap的并发度
在初始化ConcurrentHashMap对象时可以设定并发程度，并发程度越高，创建的Segment对象越多，对hash值区段的划分越细，直接使得不同线程访问相同Segment对象的冲突减少。
默认的concurrencyLevel为16，即创建16个Segment对象。

public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel);

Unsafe类
ConcurrentHashMap中使用了Unsafe类，Unsafe类可以直接观察并操作JVM。

 private Segment<K,V> ensureSegment(int k) {
    final Segment<K,V>[] ss = this.segments;
    long u = (k << SSHIFT) + SBASE; // raw offset
    Segment<K,V> seg;
    if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
        //do somthing
    }
    return seg;
}

像在ensureSegment()方法中，先计算了目标Segment对象的偏移，然后利用Unsafe.getObjectVolatile()获得了该对象的引用。

1.7源码阅读-Java集合

1 List

ArrayList

Vector

LinkedList

2 Set

HashSet

TreeSet

3 Queue

4 Map

HashMap

TreeMap

ConcurrentHashMap

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读