Java容器类(1)-List

Posted by zhidaliao on October 22, 2016

This document is not completed and will be updated anytime.

点击查看大图

点击查看大图

普通容器类

Collections关系图1

List

All Known Implementing Classes: AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector

以下为 List 的子类,当然也实现了其他的接口,比如 LinkedList实现了 Queue接口

ArrayList

父接口:Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess

public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable{

    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private transient Object[] elementData;

    // 初始化逻辑
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }
  
    // 添加元素逻辑
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

    
    // 扩容逻辑
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

}
  • 每次插入前都会进行容量检查,检查是否超出了容量,如果超出了,则进行扩容

  • 默认大小是10,容量拓展,是创建一个新的数组,然后将旧数组上的数组copy到新数组,这是一个很大的消耗,所以在我们使用ArrayList时,最好能预计数据的大小,在第一次创建时就申请够内存。

  • clear方法并不是把整个数组都删除,因为毕竟已经申请了内存,这样删了,很可惜,因为可能以后还用得着,这就免去了再次去申请内存的麻烦。这里只是把每个元素的都置为null,并把size设为0.

  • 容量进行扩展的时候,其实例如整除运算将容量扩展为原来的1.5倍加1,而jdk1.7是利用位运算oldCapacity >> 1,从效率上,jdk1.7就要快于jdk1.6。

  • 在算出newCapacity时,其没有和ArrayList所定义的MAX_ARRAY_SIZE作比较,为什么没有进行比较呢,原因是jdk1.6没有定义这个MAX_ARRAY_SIZE最大容量,也就是说,其没有最大容量限制的,但是jdk1.7做了一个改进,进行了容量限制。

ArrayList实现原理以及其在jdk1.6和jdk1.7的实现区别

LinkedList

父接口:Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;

     public LinkedList() {
    }

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }


    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned = null;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

        ...
    }   

    // 获取指定元素 折中查找元素
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    Node<E> node(int index) {
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }
}

ArrayList vs LinkedList

ArrayList底层数据结构为数组, LinkedList 是双向列表。

LinkedList迭代器的next函数只是通过next指针快速得到下一个元素并返回。而get方法会从折中开始遍历直到index下标,查找一个元素时间复杂度为哦O(n/2),get()遍历的时间复杂度就达到了O(n2),next()方式遍历时间复杂度是O(n)

ArrayList 和 LinkedList遍历方式结果对比分析

从上面的数量级来看,同样是foreach循环遍历,ArrayList和LinkedList时间差不多,可将本例稍作修改加大list size会发现两者基本在一个数量级上。

但ArrayList get函数直接定位获取的方式时间复杂度为O(1),而LinkedList的get函数时间复杂度为O(n)。 再结合考虑空间消耗的话,建议首选ArrayList。对于个别插入删除非常多的可以使用LinkedList。

结论总结

通过上面的分析我们基本可以总结下:

(1) 无论ArrayList还是LinkedList,遍历建议使用foreach,尤其是数据量较大时LinkedList避免使用get遍历。

(2) List使用首选ArrayList。对于个别插入删除非常多的可以使用LinkedList。

(3) 可能在遍历List循环内部需要使用到下标,这时综合考虑下是使用foreach和自增count还是get方式。

Set

存在相同的元素则不插入。

SortedSet

SortedSet接口,定义了排序的 Set方法,子类有 TreeSet

子类有:ConcurrentSkipListSet, TreeSet

TreeSet

TreeSet extends `AbstractSet` implements `NavigableSet`

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    private transient NavigableMap<E,Object> m;
    private static final Object PRESENT = new Object();

    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    public  boolean addAll(Collection<? extends E> c) {
        // Use linear-time version if applicable
        if (m.size()==0 && c.size() > 0 &&
            c instanceof SortedSet &&
            m instanceof TreeMap) {
            SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            TreeMap<E,Object> map = (TreeMap<E, Object>) m;
            Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) {
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c);
    }

    ...

    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
}

可以看出来 TreeSet底层是用 TreeMap 来保存元素

根据add方法可以推断, 值是 Object PRESENT = new Object(); ,一个无意义的对象, 使用 Map的结构用来保持 键值不会重复。

public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}

遍历也是使用 TreeMap 的遍历方法 . 使用红黑树保持顺序

HashSet

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    ...
}

底层使用Map数据结构。使用哈希值做索引。

EnumSet

建立枚举值的集合,没有什么特别的

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>
    implements Cloneable, java.io.Serializable
{
     
    final Class<E> elementType;

    final Enum[] universe;

    private static Enum[] ZERO_LENGTH_ENUM_ARRAY = new Enum[0];

    EnumSet(Class<E>elementType, Enum[] universe) {
        this.elementType = elementType;
        this.universe    = universe;
    }

    public static <E extends Enum<E>> EnumSet<E> of(E e) {
        EnumSet<E> result = noneOf(e.getDeclaringClass());
        result.add(e);
        return result;
    }

    public static <E extends Enum<E>> EnumSet<E> range(E from, E to) {
        if (from.compareTo(to) > 0)
            throw new IllegalArgumentException(from + " > " + to);
        EnumSet<E> result = noneOf(from.getDeclaringClass());
        result.addRange(from, to);
        return result;
    }
  
    // 返回所有elementType的元素
    private static <E extends Enum<E>> E[] getUniverse(Class<E> elementType) {
        return SharedSecrets.getJavaLangAccess()
                                        .getEnumConstantsShared(elementType);
    }

    ...
}

LinkedHashSet

通过HashSet的源码可以得知,底层使用LinkedHashMap保存,Entry中存在链表指针

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;
 
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }
 
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
 
    public LinkedHashSet() {
        super(16, .75f, true);
    }
 
    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }
}

Map

映射表,存在值相同的情况,会被覆盖

HashMap

两个非常重要的参数:初始容量 和 负载因子,这两个参数是影响HashMap性能的重要参数。其中,容量表示哈希表中 桶的数量 (table 数组的大小),初始容量是创建哈希表时桶的数量;负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,它衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。

对于使用 拉链法(下文会提到)的哈希表来说,查找一个元素的平均时间是 O(1+a),a 指的是链的长度,是一个常数。特别地,若负载因子越大,那么对空间的利用更充分,但查找效率的也就越低;若负载因子越小,那么哈希表的数据将越稀疏,对空间造成的浪费也就越严重。系统默认负载因子为 0.75,这是时间和空间成本上一种折衷,一般情况下我们是无需修改的。

JDK1.8 版本之后,拉链法链表长度大于8,会转换成红黑树

浅谈算法和数据结构(11):哈希表

Java 8系列之重新认识HashMap

SortedMap<K,V>

All Known Implementing Classes:ConcurrentSkipListMap, TreeMap

定义了有序映射表的部分接口

public interface SortedMap<K,V> extends Map<K,V> {
    
    Comparator<? super K> comparator();

    SortedMap<K,V> subMap(K fromKey, K toKey);

    SortedMap<K,V> headMap(K toKey);
    
    SortedMap<K,V> tailMap(K fromKey);

    K firstKey();
    
    K lastKey();
    
    Set<K> keySet();

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

继承自SortedMap,定义了更丰富的方法,返回更多个性化的子集。

public interface NavigableMap<K,V> extends SortedMap<K,V> {
    
    Map.Entry<K,V> lowerEntry(K key);
 
    K lowerKey(K key);
   
    Map.Entry<K,V> floorEntry(K key);
 
    K floorKey(K key);
 
    Map.Entry<K,V> ceilingEntry(K key);

    ... 

TreeMap

红黑树实现。


public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{ 
    private final Comparator<? super K> comparator;

    private transient Entry<K,V> root = null;
 
    private transient int size = 0;
 
    private transient int modCount = 0;
 
    public TreeMap() {
        comparator = null;
    }
 
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
    transient KeySet<K> navigableKeySetView = null;

    public final NavigableSet<K> navigableKeySet() {
        KeySet<K> nksv = navigableKeySetView;
        return (nksv != null) ? nksv :
          (navigableKeySetView = new TreeMap.KeySet(this));
    }

    public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }

    public boolean containsValue(Object value) {
        for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
            if (valEquals(value, e.value))
                return true;
        return false;
    }
  
    public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

    final Entry<K,V> getFirstEntry() {
        Entry<K,V> p = root;
        if (p != null)
            while (p.left != null)
                p = p.left;
        return p;
    }

    ...


    static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
        private final NavigableMap<E, Object> m;
        KeySet(NavigableMap<E,Object> map) { m = map; }

        public Iterator<E> iterator() {
            if (m instanceof TreeMap)
                return ((TreeMap<E,Object>)m).keyIterator();
            else
                return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
        }
        ...
    }


    Iterator<K> keyIterator() {
        return new KeyIterator(getFirstEntry());
    }
}

迭代器模式是获取根节点,然后依次遍历每个子节点。

通过分析 JDK 源代码研究 TreeMap 红黑树算法实现

LinkedHashMap

LinkedHashMap采用的hash算法和HashMap相同,但是它重新定义了数组中保存的元素Entry,该Entry除了保存当前对象的引用外,还保存了其上一个元素before和下一个元素after的引用,从而在哈希表的基础上又构成了双向链接列表

深入Java集合学习系列:LinkedHashMap的实现原理

WeakHashMap

public class WeakHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V> {
 
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
 
    private static final int MAXIMUM_CAPACITY = 1 << 30;
 
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
    Entry<K,V>[] table;
 
    private int size;
 
    private int threshold;
 
    private final float loadFactor;
 
    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
 
    int modCount;
 
    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

    public V put(K key, V value) {
        Object k = maskNull(key);
        int h = hash(k);
        Entry<K,V>[] tab = getTable();
        int i = indexFor(h, tab.length);

        for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
            if (h == e.hash && eq(k, e.get())) {
                V oldValue = e.value;
                if (value != oldValue)
                    e.value = value;
                return oldValue;
            }
        }

        modCount++;
        Entry<K,V> e = tab[i];
        tab[i] = new Entry<>(k, value, queue, h, e);
        if (++size >= threshold)
            resize(tab.length * 2);
        return null;
    }

    private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
        V value;
        int hash;
        Entry<K,V> next;

        Entry(Object key, V value,
              ReferenceQueue<Object> queue,
              int hash, Entry<K,V> next) {
            super(key, queue);
            this.value = value;
            this.hash  = hash;
            this.next  = next;
        }
        ..
    }

    private void expungeStaleEntries() {
        for (Object x; (x = queue.poll()) != null; ) {
            synchronized (queue) {
                @SuppressWarnings("unchecked")
                    Entry<K,V> e = (Entry<K,V>) x;
                int i = indexFor(e.hash, table.length);

                Entry<K,V> prev = table[i];
                Entry<K,V> p = prev;
                while (p != null) {
                    Entry<K,V> next = p.next;
                    if (p == e) {
                        if (prev == e)
                            table[i] = next;
                        else
                            prev.next = next;
                        // Must not null out e.next;
                        // stale entries may be in use by a HashIterator
                        e.value = null; // Help GC
                        size--;
                        break;
                    }
                    prev = p;
                    p = next;
                }
            }
        }
    }

   public int size() {
        if (size == 0)
            return 0;
        expungeStaleEntries();
        return size;
    }
}

expungeStaleEntries 方法用来清除 引用队列queue中,无效的键对应的entry对象。该方法在getTable,size,resize方法会被调用

Entry对象继承自WeakReference,使用的是弱引用机制。

private final ReferenceQueue<Object> queue = new ReferenceQueue<>();是引用队列,被GC的键会入列,等待下次对象调用 expungeStaleEntries方法

Queue

队列与栈一样是一种线性结构,因此以常见的线性表如数组、链表作为底层的数据结构。

虽然 List 可以模拟 Queue ,但是需要Queue这种数据接口,去掉List随机访问需求,从而实现高效的并发操作

通过接口的定义可以看出,没有随机访问,提供了针对FIFO的方法。

public interface Queue<E> extends Collection<E> {
 
    boolean add(E e);
 
    boolean offer(E e);
 
    E remove();
 
    E poll();
 
    E element();
 
    E peek();
}

队列(queue)原理

Deque

继承了Queue,增加了额外的双向接口方法。

public interface Deque<E> extends Queue<E> {
    
    void addFirst(E e);
 
    void addLast(E e);
 
    boolean offerFirst(E e);
 
    boolean offerLast(E e);
}

AbstractQueue

抽象类,新增了通用方法(对接口中的方法进行封装,业务处理)

public abstract class AbstractQueue<E>
    extends AbstractCollection<E>
    implements Queue<E> {
 
    protected AbstractQueue() {
    }

    public boolean add(E e) {
        if (offer(e))
            return true;
        else
            throw new IllegalStateException("Queue full");
    }
    ..
}

AbstractDeque

抽象方法,使用数组,实现了基本的通用方法

public E pollFirst() {
    int h = head;
    E result = elements[h]; // Element is null if deque empty
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}

ArrayDeque

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{ 
    private transient E[] elements;
 
    private transient int head;
 
    private transient int tail;

    private static final int MIN_INITIAL_CAPACITY = 8;

    private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        elements = (E[]) new Object[initialCapacity];
    }

    /**
     * Double the capacity of this deque.  Call only when full, i.e.,
     * when head and tail have wrapped around to become equal.
     */
    private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = (E[])a;
        head = 0;
        tail = n;
    }

    /**
     * Copies the elements from our element array into the specified array,
     * in order (from first to last element in the deque).  It is assumed
     * that the array is large enough to hold all elements in the deque.
     *
     * @return its argument
     */
    private <T> T[] copyElements(T[] a) {
        if (head < tail) {
            System.arraycopy(elements, head, a, 0, size());
        } else if (head > tail) {
            int headPortionLen = elements.length - head;
            System.arraycopy(elements, head, a, 0, headPortionLen);
            System.arraycopy(elements, 0, a, headPortionLen, tail);
        }
        return a;
    }

    public ArrayDeque() {
        elements = (E[]) new Object[16];
    }

    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }

    public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }

    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }

    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

    ...
}

allocateElements 此方法是给数组分配初始容量,初始容量并不是numElements,而是大于指定长度的最小的2的幂正数

假设a=1xxxxxxxxxxxx…(base 2, x代表该位任意为0或1) 首先a |= (a »> 1)之后,a => 11xxxxxxxx…(最高两位是1) 然后a |= (a»> 2): a => 1111xxxxxxxxx…(最高四位是1) 再a |= (a»> 4): a => 11111111xxxxxxx…(最高八位是1) …….. 最终,a的所有低位也都变成了1,即11111111…111(全是1) 再a++ 就变成了10000000000…000(加一之后进位,比原来的二进制串多了一位,且第一位是1,其它位都是0),

得到的结果大于等于任意一个操作数 结果有趋向每个位都为1的趋势 所以这样运算下来,运算得到的结果的二进制一定是每个位都是1,再加一个,就刚好是2的整数幂了

jdk源码分析ArrayDeque

ArrayDeque源码分析

PriorityQueue

底层为数组,使用二叉堆算法,优先级队列

使用方式:

PriorityQueue<Object> queue = new PriorityQueue<Object>(6, new Comparator<Object>() {
    @Override
    public int compare(Object t1, Object t2) {
       //TODO 
    }
});

源码:

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

    private static final long serialVersionUID = -7720805057305804111L;

    private static final int DEFAULT_INITIAL_CAPACITY = 11;
 
    private transient Object[] queue;
 
    private int size = 0;
 
    private final Comparator<? super E> comparator;
 
    private transient int modCount = 0;
 
    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
    
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

    private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }
}

jdk PriorityQueue优先队列工作原理分析

JDK源码研究PriorityQueue(优先队列)

Deque & ArrayDeque

Deque的实现类

ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList

双向队列

Deque is an interface and has two implementations: LinkedList and ArrayDeque.

Deque dq = new LinkedList();
Deque dq = new ArrayDeque();
When to use ArrayList and when to use ArrayDeque?

ArrayDeque has the ability to add or remove the elements from both ends (head or tail)

on the other hand removing last element from ArrayList takes O(n) time as it traverses the whole list to reach the end.

So if you want to add or remove elements from both ends choose ArrayDeque over ArrayList, however if you only want to perform the opreation on the tail (at the end) then you should choose ArrayList.


同步容器类

每个操作都上锁,效率比较慢,相对于同步容器类,并发容器更高的效率和多样化的设计显得更加的主流。

迭代操作中,修改元素,可能会抛出ConcurrentModificationException , 删除元素元素可能抛出ArrayIndexOutBoundsException

Vector

Vector和ArrayList的实现方式可以看出非常的相像,每个方法中都添加了synchronized的关键字来保证同步

Hashtable

HashMap的同步版本,关键方法都使用了同步块

collections.synchronizedMap

Map m = Collections.synchronizedMap(new TreeMap());
m.put("1", "hello");
m.put("3", "hello");
m.put("4", "hello");

Iterator<String> it = m.keySet().iterator();
while(it.hasNext()){
    System.out.println(it.next());
}

collections.synchronizedlist

collections.synchronizedSet

SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
      ...
synchronized (s) {
  Iterator i = s.iterator(); // Must be in the synchronized block
  while (i.hasNext())
      foo(i.next());
}

collections.synchronizedSortedMap

SortedMap s1 = Collections.synchronizedSortedMap(new TreeMap());

collections.synchronizedSortedSet

collections.unmodifiableXXX


并发容器类

Set

ConcurrentSkipListSet

CopyOnWriteArraySet

CopyOnWriteArraySet内部持有一个CopyOnWriteArrayList引用,所有操作都是基于对CopyOnWriteArrayList的操作。

List

CopyOnWriteArrayList

CopyOnWriteArrayList实现原理及源码分析

区别于读写锁,写锁是通过 ReentrantLock 实现的 , 读是没有任何锁 ,不保证数据的强一致性

理论

CopyOnWriteArrayList是Java并发包中提供的一个并发容器,它是个线程安全且读操作无锁的ArrayList,写操作则通过创建底层数组的新副本来实现,是一种读写分离的并发策略,我们也可以称这种容器为”写时复制器”, Java并发包中类似的容器还有CopyOnWriteSet。

集合框架中的ArrayList是非线程安全的,Vector虽是线程安全的,但由于简单粗暴的锁同步机制,性能较差。而CopyOnWriteArrayList则提供了另一种不同的并发处理策略

很多时候,我们的系统应对的都是读多写少的并发场景。CopyOnWriteArrayList容器允许并发读,读操作是无锁的,性能较高。至于写操作,比如向容器中添加一个元素,则首先将当前容器复制一份,然后在新副本上执行写操作,结束之后再将原容器的引用指向新容器。

优点:

读操作性能很高,因为无需任何同步措施,比较适用于读多写少的并发场景。Java的list在遍历时,若中途有别的线程对list容器进行修改,则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其”读写分离”的思想,遍历和修改操作分别作用在不同的list容器,所以在使用迭代器进行遍历时候,也就不会抛出ConcurrentModificationException异常了

缺点:

内存可见性不能得到保证 、 内存的使用比较高

Map

ConcurrentHashMap

继承自ConcurrentMap接口

ConcurrentSkipListMap

所有的修改操作都是使用CAS,只要失败就会重试,直至成功,所以就算多线程并发操作也不会出现错误,而且通过CAS避免了使用锁,性能比用锁好很多。

ConcurrentSkipListMap和TreeMap,它们虽然都是有序的哈希表.

  • 它们的线程安全机制不同,TreeMap是非线程安全的,而ConcurrentSkipListMap是线程安全的。
  • ConcurrentSkipListMap是通过跳表实现的,而TreeMap是通过红黑树实现的。

java并发编程(二十三)—-(JUC集合)ConcurrentSkipListMap介绍 Java多线程系列–“JUC集合”05之 ConcurrentSkipListMap

Queue

BlockingQueue 接口

阻塞队列,相对于Queue 增加了阻塞超时参数,批量几个处理方法。

BlockingQueue 接口实现类:ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue

public interface BlockingQueue<E> extends Queue<E> {

    boolean add(E e);
    
    boolean offer(E e);
    
    void put(E e) throws InterruptedException;
    
    boolean offer(E e, long timeout, TimeUnit unit)
        throws InterruptedException;
    
    E poll(long timeout, TimeUnit unit)
        throws InterruptedException;
    
    E take() throws InterruptedException;

    int remainingCapacity();

    boolean remove(Object o);
    
    public boolean contains(Object o);

    int drainTo(Collection<? super E> c);
    
    int drainTo(Collection<? super E> c, int maxElements);
}

ArrayBlockingQueue

public class ArrayBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {

    final Object[] items;

    int takeIndex;

    int putIndex;

    int count;

    /** Main lock guarding all access */
    final ReentrantLock lock;
    
    /** Condition for waiting takes */
    private final Condition notEmpty;

    /** Condition for waiting puts */
    private final Condition notFull;

    public ArrayBlockingQueue(int capacity, boolean fair) {
        if (capacity <= 0)
            throw new IllegalArgumentException();
        this.items = new Object[capacity];
        lock = new ReentrantLock(fair);
        notEmpty = lock.newCondition();
        notFull =  lock.newCondition();
    }

    public ArrayBlockingQueue(int capacity, boolean fair,
                              Collection<? extends E> c) {
        this(capacity, fair);

        final ReentrantLock lock = this.lock;
        lock.lock(); // Lock only for visibility, not mutual exclusion
        try {
            int i = 0;
            try {
                for (E e : c) {
                    checkNotNull(e);
                    items[i++] = e;
                }
            } catch (ArrayIndexOutOfBoundsException ex) {
                throw new IllegalArgumentException();
            }
            count = i;
            putIndex = (i == capacity) ? 0 : i;
        } finally {
            lock.unlock();
        }
    }

    public boolean add(E e) {
        return super.add(e);
    }

    public boolean offer(E e, long timeout, TimeUnit unit)
        throws InterruptedException {

        checkNotNull(e);
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (count == items.length) {
                if (nanos <= 0)
                    return false;
                nanos = notFull.awaitNanos(nanos);
            }
            insert(e);
            return true;
        } finally {
            lock.unlock();
        }
    }
    ...
}

ConcurrentLinkedQueue

并发的顺序队列

SynchronousQueue

ArrayBlockingQueue

DelayQueue

LinkedBlockingQueue

PriorityBlockingQueue

LinkedTransferQueue

LinkedBlockingDeque


同步工具

AbstractQueuedSynchronizer

深度解析Java 8:JDK1.8 AbstractQueuedSynchronizer的实现分析(上)

背景

Java中的FutureTask作为可异步执行任务并可获取执行结果而被大家所熟知。通常可以使用future.get()来获取线程的执行结果,在线程执行结束之前,get方法会一直阻塞状态,直到call()返回,其优点是使用线程异步执行任务的情况下还可以获取到线程的执行结果,但是FutureTask的以上功能却是依靠通过一个叫AbstractQueuedSynchronizer的类来实现。

至少在JDK 1.5、JDK1.6版本是这样的(从1.7开始FutureTask已经被其作者Doug Lea修改为不再依赖AbstractQueuedSynchronizer实现了,这是JDK1.7的变化之一)。但是AbstractQueuedSynchronizer在JDK1.8中还有如下图所示的众多子类:ReentrantLock、Semaphore、CountDownLatch、AbstractFuture

在锁框架中,AbstractQueuedSynchronizer抽象类可以毫不夸张的说,占据着核心地位,它提供了一个基于FIFO队列,可以用于构建锁或者其他相关同步装置的基础框架

AbstractQueuedSynchronizer类底层的数据结构是使用双向链表,是队列的一种实现,故也可看成是队列

  • 其中Sync queue,即同步队列,是双向链表,包括head结点和tail结点,head结点主要用作后续的调度。
  • 而Condition queue不是必须的,其是一个单向链表,只有当使用Condition时,才会存在此单向链表。并且可能会有多个Condition queue。

AQS的功能可以分为两类:独占功能和共享功能

它的所有子类中,要么实现并使用了它独占功能的API,要么使用了共享锁的功能,而不会同时使用两套API,即便是它最有名的子类ReentrantReadWriteLock,也是通过两个内部类:读锁和写锁,分别实现的两套API来实现的,为什么这么做,后面我们再分析,到目前为止,我们只需要明白AQS在功能上有独占控制和共享控制两种功能即可。

如FutureTask(JDK1.6)一样,ReentrantLock内部有代理类完成具体操作,ReentrantLock只是封装了统一的一套API而已

独占:

有那么一个被volatile修饰的标志位叫做key,用来表示有没有线程拿走了锁,或者说,锁还存不存在,还需要一个线程安全的队列,维护一堆被挂起的线程,以至于当锁被归还时,能通知到这些被挂起的线程,可以来竞争获取锁了。

共享锁。

代表:CountDownLatch. 共享的状态是可以被共享的,也就是意味着其他AQS队列中的其他节点也应能第一时间知道state状态的变化。1

ReentrantLock

公平锁

先判断队列的头指针是否为NULL,为NULL就是获取锁,修改state值。没有就排队。

final void lock() {
    acquire(1);
}

protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        if (!hasQueuedPredecessors() &&
            compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0)
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}
非公平锁

直接修改状态位 state,成功直接返回,失败入队列

final void lock() {
    if (compareAndSetState(0, 1))
        setExclusiveOwnerThread(Thread.currentThread());
    else
        acquire(1);
}

深度解析Java 8:AbstractQueuedSynchronizer的实现分析(上)

CountDownLatch

深度解析Java 8:AbstractQueuedSynchronizer 的实现分析(下)

Semaphore

本质是 AbstractQueueSynchronizer 共享锁。 分析同步工具 Semaphore 和 CyclicBarrier 的实现原理

Barier

CyclicBarrier是通过ReentrantLock(独占锁)和Condition来实现的

分析同步工具 Semaphore 和 CyclicBarrier 的实现原理

其他

ThreadLocal

类似于栈封闭

  • ThreadLocal 避免修改到其他线程的变量,所有操作局限在本线程,没有数据入库的操作,因为是全局变量 ; T1 A=5 ,T2 修改A=6 ,导致错误的 T1 A=6
  • 使用ThreadLocal,能使线程中的某个值所有改变只在该当前线程中变动,不会被其他线程操作,保证了当前线程的数据不共享,避免竞态条件的发生。

内部实现:

public T get() {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null) {
        ThreadLocalMap.Entry e = map.getEntry(this);
        if (e != null)
            return (T)e.value;
    }
    return setInitialValue();
}


public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null)
        map.set(this, value);
    else
        createMap(t, value);
}

void createMap(Thread t, T firstValue) {
    t.threadLocals = new ThreadLocalMap(this, firstValue);
}   


static class ThreadLocalMap {

    static class Entry extends WeakReference<ThreadLocal> {
        /** The value associated with this ThreadLocal. */
        Object value;

        Entry(ThreadLocal k, Object v) {
            super(k);
            value = v;
        }
    }
   
    private static final int INITIAL_CAPACITY = 16;
   
    private Entry[] table;
    
    private int size = 0;
 
    private int threshold; // Default to 0

    private void setThreshold(int len) {
        threshold = len * 2 / 3;
    }
}

其他

RandomAccess

1) 有两个类实现了 RandomAccess 接口:ArrayList Vector

2) RandomAccess 是一个声明接口,表示集合内的元素获取的时间是一样的,第一个和第一万个元素获取的时间一致。用来表明其支持快速(通常是固定时间)随机访问。此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。

3) RandomAccess 没有声明任何方法,所以也成为标记接口.用来向编译器暗示

RandomAccess 接口是List 实现所使用的标记接口,

在对List特别的遍历算法中,要尽量来判断是属于RandomAccess(如ArrayList)还是SequenceAccess(如LinkedList),因为适合RandomAccess List的遍历算法,用在SequenceAccess List上就差别很大

即对于实现了RandomAccess接口的类实例而言,遍历的效率依次递减:

for (int i=0, i<list.size(); i++)
    list.get(i);

for (int i=0, n=list.size(); i < n;!i++)
    itr.next();

for (Iterator i=list.iterator(); i.hasNext(); )
    i.next();

对于容器类的接口,要使用什么方式进行遍历需要自己指定:

Object o;
if (listObject instanceof RandomAccess)
{
  for (int i=0, n=list.size(); i < n; i++)
  {
    o = list.get(i);
    //do something with object o
  }

}
else
{
  Iterator itr = list.iterator();
  for (int i=0, n=list.size(); i < n; i++)
  {
    o = itr.next();
    //do something with object o

  }
}

参考网址

Java Collections

http://www.falkhausen.de/Java-8/