Java集合-Collection
一、Collection繼承關(guān)系
由上圖可知Collection有三個(gè)子類，分別是Set、List、Queue。
特點(diǎn)：
Set：無序且值唯一
List：有序、值可重復(fù)
Queue:先進(jìn)先出的線性表
二、Collection提供的方法
Collection提供了對(duì)集合的通用操作
三、Collection子類
1、Set
無序且值唯一。
Set子類有：
HashSet
底層數(shù)據(jù)結(jié)構(gòu)是哈希表（實(shí)際是hashMap）,從構(gòu)造函數(shù)可以看出在創(chuàng)建實(shí)例時(shí)會(huì)創(chuàng)建一個(gè)HashMap，該HashMap就是用來實(shí)際存儲(chǔ)元素的，除此之外在創(chuàng)建HashSet實(shí)例時(shí)我們可以指定其內(nèi)部HashMap的容量和加載因子（默認(rèn)大小為16，加載因子為0.75）
public HashSet() {
map = new HashMap<>();
}
再來看下增刪查數(shù)據(jù)是如何實(shí)現(xiàn)的：
- add操作
public boolean add(E e) {
//add是調(diào)用HashMap的put操作
return map.put(e, PRESENT)==null;
}
- remove操作
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
- contains操作
public boolean contains(Object o) {
return map.containsKey(o);
}
HashSet如何來保證元素唯一性? 1.依賴兩個(gè)方法：hashCode()和equals()。
TreeSet
TreeSet是一個(gè)非同步的非線程安全的二叉樹，底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹。(唯一，排序)，其add ， remove和contains操作的時(shí)間復(fù)雜度為log（n）
來看下默認(rèn)構(gòu)造函數(shù)：
public TreeSet() {
this(new TreeMap<E,Object>());
}
private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
可以看出其內(nèi)部默認(rèn)是使用TreeMap存儲(chǔ)元素的，因?yàn)槠鋬?nèi)部元素是有序的，對(duì)于元素的排序有兩種方式自然排序和比較器排序，自然排序就是當(dāng)comparator為空的時(shí)候，構(gòu)建無參構(gòu)造函數(shù)的時(shí)候默認(rèn)的一種排序方式，比較器排序就是在構(gòu)造函數(shù)中傳入comparator從而指定排序方式。
treeSet = new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length()-o2.length();
}
});
TreeSet保證元素唯一性的是通過比較的返回值是否是0來決定
LinkedHashSet
Set接口的哈希表和鏈接列表實(shí)現(xiàn)即保證插入順序，(FIFO插入有序,唯一)由鏈表保證元素有序由哈希表保證元素唯一。linkedHashSet是一個(gè)非線程安全的集合。如果有多個(gè)線程同時(shí)訪問當(dāng)前l(fā)inkedhashset集合容器，并且有一個(gè)線程對(duì)當(dāng)前容器中的元素做了修改，那么必須要在外部實(shí)現(xiàn)同步
來看下其構(gòu)造函數(shù)
public LinkedHashSet() {
super(16, .75f, true);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
LinkedHashSet父類為HashSet，然后在HashSet的構(gòu)造函數(shù)中創(chuàng)建了LinkedHashMap實(shí)例，也就是說LinkedHashSet最終是使用LinkedHashMap來存儲(chǔ)元素。
Set小結(jié)
我們簡(jiǎn)紹了三種Set在實(shí)際使用時(shí)可以根據(jù)需求選擇合適的，同時(shí)我們也看到這三種Set的實(shí)現(xiàn)最終都是通過Map來存儲(chǔ)元素的。
2、List
List鏈表是一種線性結(jié)構(gòu)，其內(nèi)部元素有序（插入有序）、不唯一，可以根據(jù)索引來查找獲取數(shù)據(jù)。
ArrayList
底層通過數(shù)組實(shí)現(xiàn)，查找快增刪慢，線程不安全。來看下默認(rèn)構(gòu)造函數(shù)
transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
可以看到存儲(chǔ)元素的是一個(gè)叫做elementData的數(shù)組。
- add操作
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
我們看到在增加元素前會(huì)先調(diào)用 ensureCapacityInternal來確保數(shù)組elementData有足夠的空間，如果空間不足會(huì)進(jìn)行擴(kuò)容操作。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//判斷是否需要擴(kuò)容
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 需要擴(kuò)容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 當(dāng)前數(shù)組大小
int oldCapacity = elementData.length;
//擴(kuò)容為原來的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1); //擴(kuò)容后還不滿足所需最小容量則把容量設(shè)置為所需最小容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//MAX_ARRAY_SIZE的值為Integer.MAX_VALUE - 8表示最大可設(shè)置的值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 真正擴(kuò)容操作是通過Arrays.copyOf來完成的
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // 溢出
throw new OutOfMemoryError();
//所需最小容量大于MAX_ARRAY_SIZE則擴(kuò)容為Integer.MAX_VALUE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
再來看下在指定位置插入元素的操作
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//檢查是否需要擴(kuò)容
ensureCapacityInternal(size + 1);
//把插入位置后面所有元素后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//插入元素
elementData[index] = element;
size++;
}
- remove操作
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;
}
可以看到remove中是根據(jù)equals來判斷元素是否是要?jiǎng)h除的，具體移除操作是通過fastRemove來完成。
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
//把移除位置之后所有元素向前移動(dòng)一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
總體來說ArrayList底層采用數(shù)組存儲(chǔ)元素在元素增刪時(shí)通過copy數(shù)組來實(shí)現(xiàn)元素移動(dòng)，其增刪操作的時(shí)間復(fù)雜度為O（n）。
Vector
底層數(shù)組實(shí)現(xiàn)，查找快增刪慢，線程安全。構(gòu)造函數(shù)
public Vector() {
this(10);
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
//這里的capacityIncrement是指擴(kuò)容時(shí)增加的容量
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
因?yàn)閂ector底層也是數(shù)組實(shí)現(xiàn)，所以在增刪數(shù)據(jù)時(shí)會(huì)涉及到數(shù)組容量的變化，這跟ArrayList類似下面是Vector擴(kuò)容的核心內(nèi)容，可以看出其在容量不足時(shí)會(huì)增加capacityIncrement的容量，如果capacityIncrement<0則直接增加一倍的容量。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
Vector實(shí)現(xiàn)跟ArrayList類似最大的不同在于Vector是線程安全的。
stack
先進(jìn)后出的結(jié)構(gòu)，stack中peek函數(shù)是查看棧頂元素但并不移除，pop是彈出棧頂元素。
其構(gòu)造函數(shù)是空實(shí)現(xiàn)
public Stack() {
}
- push操作
public E push(E item) {
addElement(item);
return item;
}
public synchronized void addElement(E obj) {
modCount++;
//檢查是否需要擴(kuò)容
ensureCapacityHelper(elementCount + 1);
//存入數(shù)據(jù)
elementData[elementCount++] = obj;
}
- pop操作
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1;
if (j > 0) {
//移動(dòng)數(shù)據(jù)
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--;
//將刪除位置置空
elementData[elementCount] = null; /* to let gc do its work */
}
- peek操作
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
public synchronized E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
LinkedList
底層雙鏈表實(shí)現(xiàn)，查找慢增刪快，線程不安全，LinkedList同時(shí)實(shí)現(xiàn)了List, Deque兩個(gè)接口也就是說它既可以作為list也可作為deque使用。
既然是雙鏈表則會(huì)有節(jié)點(diǎn)的概念，我們來看下它的Node，這是LinkedList的一個(gè)內(nèi)部類。
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;
}
}
- add操作
public boolean add(E e) {
linkLast(e);
return true;
}
//在表尾插入一個(gè)Node
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++;
}
- add（index，obj）
public void add(int index, E element) {
//檢查插入位置是否合法
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//插入鏈表
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++;
}
-
remove操作
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 { //先查找到要?jiǎng)h除節(jié)點(diǎn) for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { //移除節(jié)點(diǎn) unlink(x); return true; } } } return false; } 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; //修改前驅(qū)指針 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; }可以看出LinkedList的數(shù)據(jù)操作大多都是鏈表的操作所以其特點(diǎn)是增刪快查找慢，在類內(nèi)部LinkedList維護(hù)了first和last兩個(gè)指針，這也是其能實(shí)現(xiàn)deque功能的基礎(chǔ)。在作為deque時(shí)offer表示在隊(duì)尾入隊(duì)一個(gè)元素，poll是出隊(duì)隊(duì)首一個(gè)元素，peek是查看隊(duì)首元素但并不出隊(duì)。在作為deque時(shí)無法調(diào)用list相關(guān)接口方法。
3、Queue
隊(duì)列是一種先進(jìn)先出的線性結(jié)構(gòu)，不支持隨機(jī)訪問數(shù)據(jù)。
PriorityQueue
優(yōu)先隊(duì)列是基于堆實(shí)現(xiàn)的，對(duì)內(nèi)元素是有序的，offer，poll，remove和add等方法提供了O（log（n））的時(shí)間復(fù)雜度 ，而remove（obj）和contains方法的時(shí)間復(fù)雜度是O（n），peek時(shí)間復(fù)雜度為O（1）。排序是通過自然排序和比較器排序?qū)崿F(xiàn)的，采用哪種排序是通過構(gòu)造函數(shù)確定的，其中自然排序要求元素實(shí)現(xiàn)compare函數(shù)，比較排序則需要在構(gòu)造函數(shù)中指明排序規(guī)則。
默認(rèn)構(gòu)造函數(shù)
private static final int DEFAULT_INITIAL_CAPACITY = 11;
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
//可以看出內(nèi)部采用數(shù)組存儲(chǔ)
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
- offer
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
//擴(kuò)容
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
//入隊(duì)
siftUp(i, e);
return true;
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
//這里以分析siftUpComparable為例
siftUpComparable(k, x);
}
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
//找k位置的父節(jié)點(diǎn)的index
int parent = (k - 1) >>> 1;
//k位置的父節(jié)點(diǎn)
Object e = queue[parent];
//調(diào)整堆，大于父節(jié)點(diǎn)的就不動(dòng)，小于父節(jié)點(diǎn)的就上浮
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
- poll操作
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
//調(diào)整堆
siftDown(0, x);
return result;
}
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
ArrayDeque
雙端隊(duì)列，底層數(shù)組實(shí)現(xiàn)。
默認(rèn)構(gòu)造函數(shù)
public ArrayDeque() {
//數(shù)組大小默認(rèn)16
elements = new Object[16];
}
因?yàn)榭梢噪p端操作數(shù)據(jù)所以其內(nèi)部采用head和tail來存儲(chǔ)頭尾元素的index這樣就可以快鎖找到頭尾元素。ArrayDeque還規(guī)定elements的size必須是2的整數(shù)次冪，當(dāng)我們?cè)O(shè)置容量大小不是2的整數(shù)次冪時(shí)會(huì)進(jìn)行調(diào)整
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1; // Good luck allocating 2^30 elements
}
elements = new Object[initialCapacity];
}
allocateElements實(shí)現(xiàn)思路如下：
1.要明確2整數(shù)次冪使用二進(jìn)制的表現(xiàn)形式如下：0...010...0，中間有一個(gè)1，其它的都是0。
2.根據(jù)1的形式，計(jì)算使輸入任意的X，等式成立的Y。X的二進(jìn)制形式為????????，是一個(gè)未知數(shù)，這樣如何求得Y呢？方法很簡(jiǎn)單，找到X最高位為1的位置：那么X就是0..001???，這種形式了。那么所求的Y就是0..010...0，其值就是比X最高位為1再高一位為1，其它位為0的值。
3.X的最高為1的那一位是未知的，如何求更高一位為1的Y呢？直接求是沒有辦法的，但是可以通過將X最高位為1后面所有位都變成1，再加1進(jìn)位的方式辦到。就是0..001???變成0.001..1，使用這個(gè)+1就會(huì)變成所要的Y：0.010...0了。
4.如何保證X最高位為1后面都是1呢？這個(gè)就是上面位運(yùn)算所實(shí)現(xiàn)的內(nèi)容了。假設(shè)X是0..01???，左移一位就是0.001??，做或運(yùn)算就變成了0..011??，是不是很巧妙，出現(xiàn)了兩位為1的就移動(dòng)2位，獲得四位為1的值，這樣移動(dòng)到16的時(shí)候就涵蓋了32位整數(shù)的所有范圍了。這個(gè)時(shí)候+1可能發(fā)生整數(shù)溢出，所以再左移一位保證在整數(shù)范圍內(nèi)。
- addFirst
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
//(head - 1) & (elements.length - 1)的作用是確定head的index
elements[head = (head - 1) & (elements.length - 1)] = e;
//首尾指向同一位置 擴(kuò)容至原先兩倍大小
if (head == tail)
doubleCapacity();
}
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
- pollFirst
public E pollFirst() {
final Object[] elements = this.elements;
final int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result != null) {
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
}
return result;
}
在addFirst中(head - 1) & (elements.length - 1)操作主要是確定入隊(duì)的隊(duì)首元素的位置，該操作相當(dāng)于取模操作同時(shí)還很好的處理了head-1是-1的情況（head-1是-1時(shí)該操作的結(jié)果是elements.length - 1）
