1. 整体关系图
Collection
|---------List
|----------ArrayList
|----------LinkedList
|----------Vector（笔者在开发中用的很少）
|---------Set
|----------HashSet
|----------LinkedHashSet
|----------TreeSet
Map
|----------HashMap
|----------LinkedMap
|----------TreeMap
下面，会对这几个实现类做一些说明
2. ArrayList
- 属性
/**
* 初始化数组长度,当使用 List<T> list = new ArrayList<>()初始化集合时，第一次调用add方法会将数组长度设置为此值;
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 当调用构造器方法传递的初始化大小为0或者空集合的时候，elementData为此值
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 调用 List<T> list = new ArrayList<>(); 时 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存放集合数据
*/
transient Object[] elementData;
-
构造器
/** * 创建一个给定初始值大小的数组，其中elementData存放真实数据 */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 将集合的数据放入到此数组中,如果集合为空，则elementData = EMPTY_ELEMENTDATA */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } } 添加
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
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);
}
通过上面的方法不难看到，在调用add方法时，会首先进行数组大小检查，当使用new ArrayList 构造方法时，默认数组长度取DEFAULT_CAPACITY（10），调用grow()方法进行扩容，每次扩容 大小为原来数组大小的1.5倍 ，即int newCapacity = oldCapacity + (oldCapacity >> 1); 底层会调用System.arrayCopy进行数组复制，注意,System.arrayCopy调用java本地native方法，在内存进行数组复制，这个是个线程不安全的方法，多线程竞争的情况下会出现java.lang.RuntimeException: System.arraycopy is not thread safe。
- 获取
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
从这里看出获取方法是从elementData里面取出来数据,这里就不加赘述了。
- 删除
/**
* 找到对应的数组下标，如果这个是最后一个元素，直接将其置为null；
* 如果不是最后一个元素，则调用System.arraycopy方法，将后面的元素位置+1，最后将最后一个元素置空
* eg.
* before : 1 | 2 | 3 | 4 | 5
* move : 1 | 2 | 4 | 5 | __
* after: 1 | 2 | 4 | 5 | null
*/
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;
}
/**
* 此方法跟上面的方法大同小异，都是先通过确定数组下标在进行删除操作
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
- 更新
/**
* 根据传入的数组下标确定值，返回原值
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
- 并发情况
- 只add，中间不进行遍历
public static void main(String[] args) throws InterruptedException {
List<Integer> list = new ArrayList<>();
list.get(1);
Random random = new Random();
CountDownLatch countDownLatch = new CountDownLatch(20);
for (int i = 0; i < 20; i++) {
new Thread(() -> {
System.out.println("线程" + Thread.currentThread().getName() + "开始执行");
int total = random.nextInt(1000) % 4001 + 1000;
System.out.println("长度：" + total);
for (int j = 0; j < total; j++) {
list.add(j);
}
countDownLatch.countDown();
System.out.println("线程" + Thread.currentThread().getName() + "执行完毕");
}, String.valueOf(i)).start();
}
countDownLatch.await();
System.out.println("集合长度：" + list.size());
}
此样例只是模拟高并发下add操作，通过实验发现会报出java.lang.ArrayIndexOutOfBoundsException 异常,对于此异常网上没有什么好的解释。
笔者猜测在执行到add方法时，a,b 两个线程同时进行ensureCapacityInternal检查，每个线程检查都不够扩容条件，所以执行elementData[size++] = e 方法，
假设elementData的容量就是10，现在已经有了9个元素，正常情况下a线程插入正常，b线程在插入时候会变成elementData[10++]，由此造成数组下标越界。当然，
这个猜想如果有不对的地方欢迎指正
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
2.插入和遍历同时进行
public static void main(String[] args){
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 4; i++) {
new Thread(() -> {
System.out.println("线程" + Thread.currentThread().getName() + "开始执行");
System.out.println("长度：" + 20);
for (int j = 0; j < 20; j++) {
list.add(j);
}
System.out.println("线程" + Thread.currentThread().getName() + "执行完毕");
for (Integer integer : list){
System.out.println(integer);
}
}, String.valueOf(i)).start();
}
System.out.println("集合长度：" + list.size());
}
执行此操作会报java.util.ConcurrentModificationException异常，ArrayList里面有一个内部类，private class Itr implements Iterator<E>，在ListArray每次add是，有一个变量modCount一直在做自增，当做遍历操作的时候，ArrayList因为没有加入同步机制，所以checkForComodification检查方法不允许在遍历时进行新增和删除操作。
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
...
...
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
...
...
}
3. LinkedList
- 属性
/**
* 集合元素个数
*/
transient int size = 0;
/**
* 集合首个元素
*/
transient Node<E> first;
/**
* 集合最后一个元素
*/
transient Node<E> last;
- 构造器
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
- 新增
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
// 保存集合中最后一个元素
final Node<E> l = last;
// 将传入的元素构造成node
final Node<E> newNode = new Node<>(l, e, null);
// 因为是末尾插入，新插入的元素为最后一个
last = newNode;
// 如果当前集合为空的时候，first和last都指向这个新增的元素
// 如果不是空，维护原来的链状关系
if (l == null)
first = newNode;
else
l.next = newNode;
// 集合元素个数+1
size++;
// 计数，遍历用
modCount++;
}
// 新增集合
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
// 指定位置插入集合
public boolean addAll(int index, Collection<? extends E> c) {
// 检查传入的index是否合理 (index >= 0 && index <= size)
checkPositionIndex(index);
Object[] a = c.toArray();
// 记录插入元素个数
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
//分为两种情况
// ① 集合从末尾插入，这时只要维护尾端的链式结构就可以，对原集合前面的元素没有影响,
// 当循环插入之后，只需要将last节点指向最后一个元素即可
// ② 从中间某一段插入，这时，succ记录原集合的指定位置元素，pred记录上一节点元素
// ，当循环插入之后，维护succ与插入的最后一个节点之间的关系
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
-
删除
移除首项元素,如果集合为空，会抛出NoSuchElementException异常
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
移除指定位置元素，如果集合为空或者位置不合法，会抛出IndexOutOfBoundsException异常
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
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;
}
移除特定对象，会先遍历集合，如果没有找到，不会抛出异常，会返回false
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
- 更改,会返回原来的值
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
- 查询，会使用折半查找，查找的时间复杂度为O(n),对比ArrayList的时间复杂度O(1)在查找上的效率不高，但是插入和删除的效率要比ArrayList高，
只需要维护链状结构即可。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
// 折半查找
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;
}
}
4. Vector
- 对于Vector来说，为JDK1.0就已经存在古老集合，ArrayList在实现上很大一部分借鉴了Vector里面的方法，
所不同的是Vector里面的方法大部分为同步方法，单个操作是线程安全的。有兴趣的同学可以看看源码，
其实跟ArrayList大同小异。但是如果涉及到组合操作也会造成线程不安全问题。测试代码：
public static void main(String[] args) throws InterruptedException {
List<String> list = new Vector<>();
CountDownLatch count = new CountDownLatch(20);
Random random = new Random();
for (int i = 0; i < 20; i++) {
new Thread(() -> {
int k = random.nextInt(100);
if (!list.contains(String.valueOf(k))) {
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
list.add(String.valueOf(k));
}
count.countDown();
}, String.valueOf(i)).start();
}
count.await();
System.out.println("运行前集合数量：\t" + list.size());
Set<String> set = new HashSet<>();
list.forEach(a -> set.add(a));
System.out.println("排序后集合数量：\t" + set.size());
}
这里我们是中间加了一段Thread.sleep(2000);休息时间的代码，来让这个错误放大。测试结果表明list中的元素确实回出现重复值的情况，
所以要实现线程安全，外部还得加入安全机制。
5. HashMap(本来按照上面的顺序需要这里需要写HashSet，但是因为HashSet底层都是用的HashMap，所以先介绍HashMap)
-
参考资料：
- HashMap源码注解 之 静态工具方法hash()、tableSizeFor()
- HashMap中的tableSizeFor方法
- JDK1.8源码解析-HashMap
- HashMap源码解析JDK1.8(史上最详细的源码分析)（如果感觉我这里讲的不清晰，可以来这里，这个博客感觉写的是最全的,本文的很多注释也是参考这篇文章）
属性
/**默认容量，1向左移位4个，00000001变成00010000，也就是2的4次方为16，使用移位是因为移位是计算机基础运算，效率比加减乘除快。**/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量，2的30次方。
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子，用于扩容使用。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当某个桶节点数量大于8时，会转换为红黑树。
static final int TREEIFY_THRESHOLD = 8;
//当某个桶节点数量小于6时，会转换为链表，前提是它当前是红黑树结构。
static final int UNTREEIFY_THRESHOLD = 6;
//当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。
static final int MIN_TREEIFY_CAPACITY = 64;
//存储元素的数组，transient关键字表示该属性不能被序列化
transient Node<K,V>[] table;
//将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。
transient Set<Map.Entry<K,V>> entrySet;
//元素数量
transient int size;
//统计该map修改的次数
transient int modCount;
//临界值，也就是元素数量达到临界值时，会进行扩容。
int threshold;
//也是加载因子，只不过这个是变量。
final float loadFactor;
- 构造器,注意：构造HashMap的时候并不会进行table的初始化操作，这个操作会延迟到第一次调用put（）方法的时候。
// ① 设置负载因子为0.75f
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// ② 初始化长度，使用默认的负载因子
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// ③ 指定负载因子和临界值容量
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
// 求出给定数值的最接近的2的幂
// ① 如果cap 开始不进行 -1 ，造成的情况：如果我输入的是8，那么按照下面算法操作结果为16，
// 明显求出的数不是最接近的，最接近的是8，所以需要-1
// ② 位运算，如果这段代码不太理解可以参考：https://blog.csdn.net/fan2012huan/article/details/51097331，这篇文章讲的很详细
static final int tableSizeFor(int cap) {
int n = cap - 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;
}
// ④ 放入一个Map集合
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
// 如果table没有初始化
if (table == null) {
// 因为容量阈值为 总容量 * 负载系数，所以这一步要根据m的大小来计算
// 总容量
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 如果总容量超出临界值，则重新计算临界值大小,
// 在putVal里面会对容器大小进行重新计算
if (t > threshold)
threshold = tableSizeFor(t);
}
// 容器已经初始化，但是临界值小于m的大小，进行扩容
else if (s > threshold)
resize();
// 循环遍历,putVal 会在下面解释
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
- 新增
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 求出Key的hash值，将高位和低位混合，增加hash的随机性，笔者也是参考:
// https://blog.csdn.net/kenzhang28/article/details/80212936,
// 这篇文章会有详细描述
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab指向哈希数组，p为哈希数组特定位置的首个节点，n为数组大小，i为hash位置
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 当table没有初始化或者tab的容量为0是，进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果当前hash值的节点为null，则证明没有元素存放，直接将新元素放进去
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 当节点值不为null的时候
Node<K,V> e; K k;
// 由上面的代码，p已经指向了首节点，如果首节点的hash值和key都相同，则将e指向p
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果当前节点为红黑树结构，则将值放在树中，e指向这里
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 如果当前结构为链表，遍历，如果当前元素的数量大于等于8，则将其转化为红黑树
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;
}
这里没有对resize()和链表转红黑树做进一步说明，有兴趣的同学可以继续看一看源码，
对于红黑树而言，笔者也是一知半解就不误人子弟了_。
- 删除
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 如果table已经初始化并且里面有元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 查找
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 如果存在元素,移除并返回老值
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
- 更新
// 比较老值，如果符合传入的则替换
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
// 将对应的key的value设置为传入值
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
- 查询
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) {
// 根据hash寻址，找出节点第一个元素,如果hash和key符合就返回
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;
}
因为对红黑树没有什么研究，所以本文涉及到红黑树的部分就一笔带过，后续会单独写一章红黑树的介绍~~
6. LinkedHashmap
- 参考资料：
- LinkedHashMap，集成自HashMap，可以说LinkedHashMap = HashMap + LinkedList，跟HashMap不同的是
LinkedHashMap加了一些维护链表的操作，其中accessOrder来决定是按照插入排序还是按照访问排序，具体细节
可以参考上面给的链接，这里就不过多叙述了
7. TreeMap/HashSet/LinkedHashSet/TreeSet
- TreeMap是基于红黑树的结构来实现的，支持自定义排序，这里笔者会在后续专门写一篇关于红黑树的分析文章，
并且会将红黑树的实现放在那篇文章里面讲解（说到底还是底蕴不足，学无止境啊~） - TreeSet:底层是由TreeMap实现的，至于HashSet、LinkedHashSet都是由Map的对应实现类变种过来的，有兴趣
可以看一下源码，这里就不过多做解释了。
