概述:
- 集合类继承或实现自两个接口Collection和map。
- list、set、queue实现Collection接口,map类实现map接口。
- Set有HashSet,LinkedHashSet,TreeSet实现类。各个实现类内部使用map作为数据存储。
- List有ArrayList,Vector,LinkedList,Stack实现类。
- Map下有Hashtable,LinkedHashMap,HashMap,TreeMap实现类。
-
Queue有PriorityQueue实现类。
ArrayList
ArrayList实现于List、RandomAccess接口。可以插入空数据,也支持随机访问,相当于动态数据,其中最重要的两个属性分别是:elementData数组,以及size大小,默认为10
ArrayList实现于List、RandomAccess接口。可以插入空数据,也支持随机访问,相当于动态数据,其中最重要的两个属性分别是:elementData数组,以及size大小,默认为10
性能消耗主要在于数组复制上,所以ArrayList查找快O(1),增删慢O(n),不是线程安全的
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 扩容检查
elementData[size++] = e; // 将插入的值放到尾部,并将size+1
return true;
}
// 该方法涉及数组拷贝
public void add(int index, E element) {
rangeCheckForAdd(index); // 范围检查
ensureCapacityInternal(size + 1); // 扩容检查
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element; // 对数据进行复制,目的是把index位置空出来来放本次插入的数据,并将后面的数据向后移动一个位置
size++;
}
// 扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原来的1.5倍
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);
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
// 删除,涉及拷贝
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
Vector
也是实现于List接口,底层数据结构和ArrayList类似,也是一个动态数组存放数据。不过是在add()方法的时候使用synchronize进行同步写数据,但是开销较大,所以Vector是一个同步容器并不是一个并发容器,基本不用了。
LinkedList
底层是基于双向链表实现的,也实现了list接口
插入、删除都是移动指针,效率高O(1);查找需要遍历,效率低O(n)
不是线程安全的
实现了Deque接口,所以LinkedList不止有队列的接口,还有栈的接口,可以使用LinkedList作为队列和栈的实现。
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
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 E get(int index) {
checkElementIndex(index); // 范围校验
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
HashSet
无序不可重复,底层是HashMap实现,HashMap中的key是不能重复的,从而产生了不能重复的集合
//数据结构
//HashSet集合中的内容是通过 HashMap 数据结构来存储的
private transient HashMap<E,Object> map;
//向HashSet中添加数据,数据在上面的 map 结构是作为 key 存在的,而value统一都是 PRESENT
private static final Object PRESENT = new Object();
//添加元素
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
//删除元素
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
//查找元素
public boolean contains(Object o) {
return map.containsKey(o);
}
TreeSet
有序不可重复,底层是TreeMap实现
HashTable
默认initialCapacity:11,loadFactor:0.75
线程安全,key和value不能为null
效率低,基本不用
HashMap
线程不安全,Key和value可为null。底层数据结构如下图:
底层是基于数组、链表、红黑树实现的,其中有两个重要的参数:容量、负载因子,容量默认值为16,负载因子默认值为0.75,当HashMap的size>容量*0.75时,就会发生扩容; 当hash碰撞之后写入链表的长度超过了阈值(默认为8),链表将会转换为红黑树。假设hash冲突非常严重,一个数组后面接了很长的链表,此时查找的时间复杂度就是O(n),如果是红黑树,时间复杂度就是O(logn),大大提高了查询效率。
get和put实现:
static final int hash(Object key) {
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// jdk1.7源码,jdk1.8没这个方法,但实现原理一样
static int indexFor(int h, int length) {
return h & (length -1); // 第三步 取模运算
}
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K, V> e;
K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0;; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
上述过程举例:
首先会将传入的Key做hash运算计算出 hashcode,然后根据数组长度取模计算出在数组中的index下标。
由于在计算中位运算比取模运算效率高的多,所以HashMap规定数组的长度为2n。这样用2n - 1做位运算与取模效果一致,并且效率还要高出许多。
由于数组的长度有限,所以难免会出现不同的Key通过运算得到的index相同,这种情况可以利用链表来解决,HashMap会在table[index]处形成链表,将数据插入到链表尾部。
resize扩容:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
看下图可以明白这句话的意思,n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。
元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:
因此,我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,可以看看下图为16扩充为32的resize示意图:
这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别,JDK1.7中rehash的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK1.8不会倒置。
LinkedHashMap
LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。
TreeMap
TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。
ConcurrentHashMap
线程安全,key和value不能为null
底层数据结构为:数据+链表+红黑树 CAS+Synchronized来保证并发更新的安全。
几个重要变量:
table:默认为null,初始化发生在第一次插入操作,默认大小为16的数组,用来存储Node节点数据,扩容时大小总是2的幂次方。
nextTable:默认为null,扩容时新生成的数组,其大小为原数组的两倍。
sizeCtl:默认为0,用来控制table的初始化和扩容操作,具体应用在后续会体现出来。
- -1 代表table正在初始化
- -N 表示有N-1个线程正在进行扩容操作
- 其余情况:
1、如果table未初始化,表示table需要初始化的大小。
2、如果table初始化完成,表示table的容量,默认是table大小的0.75倍,居然用这个公式算0.75(n - (n >>> 2))。
Node:保存key,value及key的hash值的数据结构。其中value和next都用volatile修饰,保证并发的可见性。
ForwardingNode:一个特殊的Node节点,hash值为-1,其中存储nextTable的引用。
初始化
确保table的大小总是2的幂次方:
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
private static final int tableSizeFor(int c) {
int n = c - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) 1 : (n >= MAXIMUM_CAPACITY) MAXIMUM_CAPACITY : n + 1;
}
注意:并不会直接初始化table,而是延缓到第一次put操作
Table初始化:
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// 如果一个线程发现sizeCtl<0,意味着另外的线程执行CAS操作成功,当前线程只需要让出cpu时间片
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
sizeCtl默认为0,如果ConcurrentHashMap实例化时有传参数,sizeCtl会是一个2的幂次方的值。所以执行第一次put操作的线程会执行Unsafe.compareAndSwapInt方法修改sizeCtl为-1,有且只有一个线程能够修改成功,其它线程通过Thread.yield()让出CPU时间片等待table初始化完成。
确定哈希桶数组索引位置:
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
(f = tabAt(tab, i = (n - 1) & hash)) == null
Put(K,V):
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException(); // key和value都不可为空,为空直接抛出错误
int hash = spread(key.hashCode());// 计算Hash值,确定数组下标,这个和HashMap是一样的
int binCount = 0;
// 进入无线循环,直到插入为止
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 如果table为空或者容量为0就表示没有初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();// 初始化数组
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// CAS如果查询数组的某个桶是空的,就直接插入该桶中
if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null))) //
break; // no lock when adding to empty bin 不加锁
}
// 如果在插入的时候,节点是一个forwordingNode状态,表示正在扩容,那么当前线程进行帮助扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 锁定头节点
synchronized (f) {
// 确定这个节点的确是数组中的这个头结点
if (tabAt(tab, i) == f) {
// 是个链表
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 如果遍历到一个值,这个值和当前的key是相同的,那就更改value值
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
// 如果遍历到结束都没有遇到相同的key,且后面没有节点了,那就直接在尾部插入一个
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 如果是红黑树存储就需要用红黑树的专门处理了
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
// 判断节点数量是否大于8,如果大于就需要把链表转化成红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// map已存储的数量+1
addCount(1L, binCount);
return null;
}
tabAt:
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
在java内存模型中,我们已经知道每个线程都有一个工作内存,里面存储着table的副本,虽然table是volatile修饰的,但不能保证线程每次都拿到table中的最新元素,Unsafe.getObjectVolatile可以直接获取指定内存的数据,保证了每次拿到数据都是最新的。
扩容:
当table容量不足的时候,即table的元素数量达到容量阈值sizeCtl,需要对table进行扩容。
整个扩容分为两部分:
构建一个nextTable,大小为table的两倍。
把table的数据复制到nextTable中。
这两个过程在单线程下实现很简单,但是ConcurrentHashMap是支持并发插入的,扩容操作自然也会有并发的出现,这种情况下,第二步可以支持节点的并发复制,这样性能自然提升不少,但实现的复杂度也上升了一个台阶。
先看第一步,构建nextTable,毫无疑问,这个过程只能只有单个线程进行nextTable的初始化,具体实现如下:
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}
通过Unsafe.compareAndSwapInt修改sizeCtl值,保证只有一个线程能够初始化nextTable,扩容后的数组长度为原来的两倍,但是容量是原来的1.5。
节点从table移动到nextTable,大体思想是遍历、复制的过程。
首先根据运算得到需要遍历的次数i,然后利用tabAt方法获得i位置的元素f,初始化一个forwardNode实例fwd。
如果f == null,则在table中的i位置放入fwd,这个过程是采用Unsafe.compareAndSwapObjectf方法实现的,很巧妙的实现了节点的并发移动。
如果f是链表的头节点,就构造一个反序链表,把他们分别放在nextTable的i和i+n的位置上,移动完成,采用Unsafe.putObjectVolatile方法给table原位置赋值fwd。
如果f是TreeBin节点,也做一个反序处理,并判断是否需要untreeify,把处理的结果分别放在nextTable的i和i+n的位置上,移动完成,同样采用Unsafe.putObjectVolatile方法给table原位置赋值fwd。
遍历过所有的节点以后就完成了复制工作,把table指向nextTable,并更新sizeCtl为新数组大小的0.75倍 ,扩容完成。
get(k):
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
// 数组已被初始化且指定桶中不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 先判断头节点,如果头节点的hash值与入参key的hash值相同
if ((eh = e.hash) == h) {
// 头节点的key就是传入的key
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// eh<0表示这个节点是红黑树
else if (eh < 0)
// 直接从树上进行查找返回结果,不存在就返回null
return (p = e.find(h, key)) != null p.val : null;
// 如果首节点不是查找对象且不是红黑树结构,那边就遍历这个列表
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
// 都没有找到直接返回null
return null;
}
参考:
常见集合源码分析(基于jdk8)
https://my.oschina.net/jzgycq/blog/1933002
JDK源码解析
https://www.cnblogs.com/ysocean/category/1149707.html
HashMap 源码详细分析(JDK1.8)
https://segmentfault.com/a/1190000012926722