List + Set + Map + Queue

2017-03-10 本文已影响263人 super_shanks

List

ArrayList
平时使用的最多的list，内部基于随机数组实现，set和get的方法效率较高，默认容量为10，

    private static final int DEFAULT_CAPACITY = 10;

当超过容量时，增加一半

        int newCapacity = oldCapacity + (oldCapacity >> 1);

LinkedList
基于链表实现的list，add和remove的方法效率较高，但也仅限于达到一定的数量级才能看得出差异。
Vector
线程安全的list，内部基于数组实现，默认容量为10，容量不够的时候翻倍

int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);

 处于线程安全的考虑，本来就会损失一定的效率，在扩容方面又被ArrayList甩开了。

CopyOnWriteArrayList
又是一个线程安全的list，基于数组的实现。每次都以当前数组大小+1，生成一个新的数组。
Vector和CopyOnWriteArrayList的抉择问题
两者都是线程安全，那我们应该如何取舍？
既然是线程安全，那肯定会从操作列表的方法开始着手，我们就一一来看一下双方的add方法
CopyOnWriteArrayList.java

public synchronized boolean add(E e) {
        Object[] newElements = new Object[elements.length + 1];
        System.arraycopy(elements, 0, newElements, 0, elements.length);
        newElements[elements.length] = e;
        elements = newElements;
        return true;
    }

同步方法，通过new新的数组出来，native做拷贝。

Vector.java

public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

就是纯粹的方法同步。

乍一看都是同步，貌似看不出什么使用区别，那我们再来看一个区别你就明白了：
CopyOnWriteArrayList.java

@Override public ListIterator<E> listIterator(int index) {
            Slice slice = this.slice;
            Object[] snapshot = elements;
            slice.checkPositionIndex(index);
            slice.checkConcurrentModification(snapshot);
            CowIterator<E> result = new CowIterator<E>(snapshot, slice.from, slice.to);
            result.index = slice.from + index;
            return result;
        }

Vector.java

public synchronized ListIterator<E> listIterator(int index) {
        if (index < 0 || index > elementCount)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }

一个是同步的，现在是不同步的。那么什么意思呢？

就是说CopyOnWriteArrayList在遍历的时候，你可以进行add和remove操作，但是就像前面说的其实现原理，如果你在遍历的时候对数据进行操作，实际上并不影响遍历的结果。
而Vector需要遍历了之后才可以进行操作，因为遍历是上锁的。

遍历的效率问题
只要是实现了RadomAccess接口的类，遍历的时候使用
for( int i = 0 ; i < x ; i++)是效率最高的
其他的遍历方式包括for(Object object : list)
list.forEach(new Consumer)
list.forEach(var->())

Set

HashSet
内部基于HashMap，线程不安全

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

   默认的大小为HashMap默认大小4

    static final int DEFAULT_INITIAL_CAPACITY = 4;

 由于基于HashMap的实现，故而存储元素需要重写equals和hashcode方法，来保证相同元素的equals放回true，hashcode相等

TreeSet
内部基于treeMap,非线程安全。

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

  由于跟树有关，存储的元素需要实现comparable

LinkedHashSet
继承了hashSet，基本和hashSet相同，在最新的代码中，我已看不出和HashSet有什么区别，除了初始的initialCapacity有些许差异之外，就是spliterator这个java8最新加入的方法了
CopyOnWriteArraySet
同CopyOnWriteArrayList
EnumSet
专门为枚举设计的set，内部基于enum数组实现
谈谈新出现的spliterator方法
用于实现并发遍历的方法，我们之前所用的for遍历都是单线程的实现，但是我们现在可以使用spliterator方法趋势线多线程的遍历，大大的提高遍历的效率。使用方式如下

        Spliterator<Employee> spliterator = set.spliterator();
        while (spliterator.tryAdvance(new Consumer<Employee>() {
                public void accept(Employee employee) {
                    employee.name += "new";
                }
            }));

  或者

        Spliterator<Employee> spliterator = set.spliterator();
        spliterator.forEachRemaining (new Consumer<Employee>() {
                public void accept(Employee employee) {
                    employee.name += "new";
                }
            });

Map

HashMap
使用的最多的map，内部基于数组链表实现，需要重写key对象的hashcode和equals方法，先通过hashcode方法找到数组的index，然后通过equals方法去该index的链表中找到这个key，然后取出键值对。

```

final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}

    int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
    for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

     非线程安全

   * ArrayMap


   * TreeMap
     非线程安全，内部基于红黑树实现，相应的key需要实现comparable接口，需要以此来实现内部树排序

   * LinkedHashMap
     非线程安全，内部会有排序（默认为插入的顺序），或者根据你传入的排序规则LRU等等。在遍历的时候，会按照顺序进行遍历，而非HashMap的乱序

   * HashTable
      线程安全，看到所有的方法都是synchronized的，key和value都不能为null

// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}

    // Makes sure the key is not already in the hashtable.
    HashtableEntry tab[] = table;
    int hash = hash(key);

   * ConcurrentHashMap
     结合了HashTable和HashMap的有点，不是所有的方法都上锁，在保证线程安全的情况下摇臂HashTable的性能好。
    
   * WeakHashMap
     和HashMap基本相同，只是key使用的若引用，一旦key的对象呗销毁，就会自动抹去相应的key
    ```
        public K getKey() {
            return (K) WeakHashMap.unmaskNull(get());
        }
        static Object unmaskNull(Object key) {
            return (key == NULL_KEY) ? null : key;
        }
        private static final Object NULL_KEY = new Object();

EnumMap
适用于Enum的map

Queue

ArrayBlockingQueue
线程安全的队列，内部基于数组实现。实现阻塞队列接口，采用外部锁方式进行添加

public void put(E e) throws InterruptedException {
        Objects.requireNonNull(e);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (count == items.length)
                notFull.await();
            enqueue(e);
        } finally {
            lock.unlock();
        }
    }

构造时需要传入队列大小，一旦队列存满，再次存数据将被阻塞

    public ArrayBlockingQueue(int capacity) {
        this(capacity, false);
    }

LinkedBlockingQueue
依然实现阻塞队列的接口，默认的capacity为无穷大，可以指定，内部一链表形式实现。线程安全
PriorityBlockingQueue
优先级阻塞队列，基于数组实现，默认大小为11

    public PriorityBlockingQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
    private static final int DEFAULT_INITIAL_CAPACITY = 11;

内部按照传入的Comparator方法来布置队列优先级。线程安全

PriorityQueue
线程不安全的优先级队列。

使用场景的梳理

首先List, Set, Queue都是基于Collection的实现，collection的最基本定义就是一个位置只能存一个值。

List更多强调的是具有一定的顺序，相当于只是对数组做了简单的封装。
Set更强调的是不能存在重复的对象。
Queue更强调的是进出容器的顺序。

Map自成一类，本身的实现基于数组的链表，在数组的index上存了一串链表，链表中按照put的顺序存着许多entry，根据key找到相应的entry。

List + Set + Map + Queue

List

Set

Map

Queue

使用场景的梳理

猜你喜欢

热点阅读