Notes
Search
⌃K

Collection

Java 集合框架和分为 Collection 和 Map 两大类。其中 Collection 又由 ListSetQueue 三类组成。
本节主要讲线程不安全的容器,线程安全的容器见 Thread-safe Collection
Collection 类继承关系

List 概述

存取有序,有索引,可以根据索引来进行取值,元素可以重复。主要实现有 ArrayListLinkedList、Vector。
其中 Vector 已经过时,被ArrayList取代了。线程安全,通过在每个方法上加synchronized实现。

ArrayList(源码分析)

底层是使用数组实现,实现了自动扩容数组大小。实现了如下接口:
  • List:列表。
  • Cloneable:可以克隆。
  • Serializable:可以实现序列化。
  • RandomAccess:是一个标志接口,表示可以快速随机访问。
下面是对 ArrayList 的源码分析,Java 1.11。

属性

private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData; // non-private to simplify nested class access
private int size;
可以看到数据元素 elementData 被 transient 修饰了,但是 ArrayList 又实现了 Serializable 接口,这样不是矛盾的吗?
原因:ArrayList 可以自动扩容,所以不是数组的每个元素都存储了数据,所以不能序列化整个数组。ArrayList 有两个方法 writeObject、readObject,ObjectInputStream/ObjectOutputStream 在序列化对象时会通过反射调用这两个方法。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException { }
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException { }

构造函数

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;
}
public ArrayList(Collection<? extends E> c) { ... }
ArrayList 新增元素时,若超过数组大小,数组会扩容,导致内存复制,所以最好指定合理的初始化容量。

新增元素

public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
有两个新增元素的方法,一个是将元素增加到末尾,一个是增加到任意位置。都会先确定容量大小,若大小不够,则先扩容 1.5 倍。
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}
添加元素到指定位置的方法,会使改位置之后的所有元素都移动。
若 ArrayList 在初始化时指定了容量,并且每次添加都在末尾,那么新增元素的速度比 LinkedList 高。

删除元素

public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
同样每次删除元素都会挪动一些元素,删除位置越靠前,挪动的范围越大。

获取元素

public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
由于是基于数组实现,所以获取元素很快。

LinkedList(源码分析)

是基于双向链表结构实现的,所以查询速度慢,增删速度快,提供了特殊的方法,对头尾的元素操作(进行增删查)。定义了 Node 结构:
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
在 Java 1.7 之前,LinkedList 只包含了一个Entry 结构的 header 属性;1.7 之后做了优化,Entry 结构换成了 Node,header 属性变成了 first 和 last 两个属性。
LinkedList 实现了这些接口:Deque、Cloneable、Serializable,没有实现 RandomAccess 接口。

属性

transient int size = 0;
transient Node<E> first;
transient Node<E> last;
与 ArrayList 一样,属性也被 transient 修饰,也有 readObject、writeObject 方法。

新增元素

将元素添加到队尾:
public boolean add(E e) {
linkLast(e);
return true;
}
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++;
}
将元素添加到任意位置,相对于 ArrayList,不需要移动元素:
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(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;
}
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

删除元素

注意 node 方法,作用是找到元素位置,若位置处于前半段,则从前往后找,若处于后半段,则从后往前找。
所以删除靠前或靠后的元素效率很高,删除中间部分的元素效率相对较低。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
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;
}

获取元素

同样也是调用 node 方法,区分前半段和后半段。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
所以建议遍历 LinkedList 时,使用 Iterator 的方式。

Iterator(源码分析)

如下 remove1 方法是正确的,remove2 是不正确的,会抛出 ConcurrentModificationException。
因为虽然 foreach 方法是语法糖,会转换成 Iterator 方法,但是第 15 行还是调用的 List 的 remove 方法,而不是 Iterator 的 remove 方法。
public static void remove1(ArrayList<String> list) {
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String str = it.next();
if (str.equals("b")) {
it.remove();
}
}
}
public static void remove2(ArrayList<String> list) {
for (String s : list) {
if (s.equals("b")) {
list.remove(s);
}
}
}
Iterator 有属性 expectedModCount,当不匹配时会抛出异常。List 的 remove 方法不会修改该值,造成不匹配,所以抛出异常。
public Iterator<E> iterator() {
return new 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;
...
}

Set

元素不可以重复。

HashSet

存取无序,基于哈希表实现。
通过hashCodeequals方法来共同保证元素唯一的。底层也维护了一个数组。
根据存储的元素计算出hashCode值,然后根据计算得出的hashCode值和数组的长度进行计算出存储的下标;如果下标的位置无元素,那么直接存储;如果有元素,那么使用要存入的元素和该元素进行equals方法,如果结果为真,则已经有相同的元素了,所以直接不存;如果结果假,那么进行存储,以链表的形式存储。

LinkedHashSet

基于链表哈希表共同实现的,所以具有存取有序,元素唯一。

TreeSet

存取无序,可以进行排序(排序是在添加的时候进行排序)。基于二叉树的数据结构。
TreeSet 保证元素的唯一性是有两种方式:
  1. 1.
    存取的元素必须实现Comparable接口。
  2. 2.
    在创建TreeSet的时候向构造器中传入一个Comparator对象,Comparator对象用于比较存取元素的类型。

Queue

队列通常是指“先进先出”(FIFO)的容器。新元素插入(offer)到队列的尾部,访问元素(poll)操作会返回队列头部的元素。
通常,队列不允许随机访问队列中的元素。

Map 概述

Map保存的是键值对,键要求保持唯一性,值可以重复。
Map 类继承关系

LinkedHashMap

基于链表哈希表结构的,所以具有存取有序

TreeMap

TreeMap 底层使用的二叉树,其中存放进去的所有数据都需要排序,所以要求对象具备比较功能。与 TreeSet 类似,存取的元素需要实现Comparable接口,或者给 TreeMap 集合传递一个Comparator接口对象。

HashTable

HashTable 是一个线程安全的 Map 实现,其它与 HashMap(非线程安全)类似。
HashTable 不允许Null作为 Key 和 Value,但是 HashMap 可以。

HashMap(源码分析)

基于哈希表结构实现的,将键的 hash 值通过 hash 函数映射到数组下标,所以存储自定义对象作为键时,必须重写hasCodeequals方法。存取无序的。
会出现 hash 冲突的情况,解决方式有:开放寻址再哈希函数链表法等。Java 的 HashMap 采用的是链表法,采用数组+链表的数据结构实现。
HashMap 在多线程使用时可能会出现 CPU 100% 的情况,原因是 JDK1.7 出现 Hash 冲突时,采用的是头插法,会改变节点顺序,会造成循环链表,发生死循环。

属性

有三个重要的属性:
  • table:存储数据,有 next 属性指向 hash 冲突的下一节点。
  • threshold:默认 12,Node 数量超过 threshold 就会调用 resize 方法。
  • loadFactor:加载因子,默认 0.75。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
int threshold;
final float loadFactor;
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
}

新增元素

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// 判断当 table 为 null 或者 tab 的长度为 0 时,即 table 尚未初始化,此时通过 resize() 方法得到初始化的 table
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 通过(n - 1) & hash 计算出的值作为 tab 的下标 i,并另 p 表示 tab[i],也就是该链表第一个节点的位置。并判断 p 是否为 null
tab[i] = newNode(hash, key, value, null);
// 当 p 为 null 时,表明 tab[i] 上没有任何元素,那么接下来就 new 第一个 Node 节点,调用 newNode 方法返回新节点赋值给 tab[i]
else {
// p 不为 null 的情况,有三种情况:p 为链表节点;p 为红黑树节点;p 是链表节点但长度为临界长度 TREEIFY_THRESHOLD,再插入任何元素就要变成红黑树了。
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 判断 key 相同的条件是 key 的 hash 相同,并且符合 equals 方法。这里判断了 p.key 是否和插入的 key 相等,如果相等,则将 p 的引用赋给 e
e = p;
else if (p instanceof TreeNode)
// 第一种情况,p 是红黑树节点,那么肯定插入后仍然是红黑树节点,所以我们直接强制转型 p 后调用 TreeNode.putTreeVal 方法,返回的引用赋给 e
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// p 为链表节点的情形,也就是上述说的另外两类情况:插入后还是链表 / 插入后转红黑树。另外,上行转型代码也说明了 TreeNode 是 Node 的一个子类
for (int binCount = 0; ; ++binCount) {
// 我们需要一个计数器来计算当前链表的元素个数,并遍历链表,binCount 就是这个计数器
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 插入成功后,要判断是否需要转换为红黑树,因为插入后链表长度加 1,而 binCount 并不包含新节点,所以判断时要将临界阈值减 1
treeifyBin(tab, hash);
// 当新长度满足转换条件时,调用 treeifyBin 方法,将该链表转换为红黑树
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;
}
hash 函数:先无符号向右位移 16 位,即取 int 类型的一般,将二进制的 int 类型对半切开;再异或运算。
(n - 1) & hash:hash 表习惯将数组长度 n 设为 2 的 x 次方,这样可以保证索引位置处于数组范围内。
为什么要 2 的 x 次方?因为 n - 1 后,每一位都是 1,进行 & 运算可以减少冲突。若有些位数是 0,那么有些位置永远都不能存放数据了。
JDK 1.8 引入了红黑树来提升链表的查询效率,链表长度超过 8 后,红黑树的效率比链表高。

获取元素

没有冲突时效率最高,有冲突是链表的效率 O(n),树化后为 O(logn)。
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;
}

扩容

JDK 1.7:依次取出数组的每个元素,元素是链表,链表的头是最后添加的,重新计算 hash,然后依次插入新数组,所以原来 hash 冲突的链表会倒置顺序。
JDK 1.8:由于扩容是 2 倍关系,即 tableSize 就是左移一位,所以原来的 hash 值和新的 tableSize 按位与计算,0 索引不变,1 索引加上原来数组大小。