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。
网友评论