List

ArrayList

基本性质:

  • 底层基于数组保存;
  • 增删慢、随机查询快;
  • 线程不安全;

底层结构与初始化

(1) 结构

1
2
3
transient Object[] elementData; 
int size;
transient int modCount = 0;

(2) 加载和初始化

懒加载形式,在 add() 时进行对应的初始化;

共支持三种初始化方式:

① 无参构造: 默认不进行数据的初始化;

② 给定容量: 程序中通过给定容量来优化;

③ 通过放入 Collection 接口进行初始化;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
static final int DEFAULT_CAPACITY = 10;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_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(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;
}
}
import com.google.common.collect.Lists;
// 使用 Guava 创建指定容量的 List
List<String> list = Lists.newArrayListWithCapacity(oldList.size());

操作

1、add

① 默认插入尾部,O(1) 实现;

② 任意位置插入

  • 将插入位置后的所有元素右移一位,之后在插入位置赋值;
  • 插入的开销与插入的位置有关;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

public void add(int index, E element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index); /* 右移一位 */
elementData[index] = element;
size++;
}

2、remove

需要调用 System.arraycopy() 将 index + 1 后面的元素都复制到 index 位置上,该操作的时间复杂度为 O(N),开销大;

同 add() 操作,删除与位置紧密相关;

1
2
3
4
5
6
7
8
9
10
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;
}

3、 扩容

扩容后的大小为 oldN * 1.5 + 1

通过 Arrays.copyOf() 复制到新数组中;

可通过指定初始容量的方式,来减少扩容的次数,减少不必要的开销;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); /* init capacity */
}
ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(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);
/* copy to impl. */
elementData = Arrays.copyOf(elementData, newCapacity);
}

4、 迭代访问

采用快速失败模式实现;

通过成员变量 modCount 与 expectedModCount 比较实现;

主要用在序列化获得迭代操作时进行判断,对应抛出 ConcurrentModificationException

5、序列化

只序列化数组中存放值的这些部分。

ArrayList 基于数组实现,并且具有动态扩容特性,因此保存元素的数组不一定都会被使用,那么就没必要全部进行序列化。

1
transient Object[] elementData;     // not serialize

通过 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
int expectedModCount = modCount; /* keep to compare */
s.defaultWriteObject(); /* only have space */

s.writeInt(size);

for (int i=0; i<size; i++) { /* only write have element */
s.writeObject(elementData[i]);
}

if (modCount != expectedModCount) { /* use for fail-fast */
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;

s.defaultReadObject();

s.readInt(); // ignored

if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);

Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
// 将 list 序列化到指定文件
ArrayList list = new ArrayList();
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(list);

其他

(1) ArrayList 与 Array 的比较

① 存储类型: Array 可以存放基本和对象类型, ArrayList 只能存放对象类型;

② 存放元素的大小: ArrayList 动态可变,Array 不可变;

③ 其他方法和特性:

  • ArrayList 提供 addAll(),removeAll(),iterator() 等方法;
  • 对于基本类型数据,集合使用自动装箱来减少编码工作量。但当处理固定大小的基本数据类型的时候,这种方式相对比较慢。

(2)ArrayList 与 LinkedList 的比较

都是线程不安全的容器,都实现了 List 接口具备 List 的特性。

① 底层结构: ArrayList 基于索引的数据接口,底层是动态数组实现,LinkedList 以元素列表的形式存储数据,是双向链表实现;

② 操作性质:

  • 随机访问: ArrayList 支持随机访问,LinkedList 不支持;
  • 元素删除: LinkedList 在任意位置添加删除元素更快;
  • 操作是否与元素位置的影响: 比较插入和删除是否受元素位置影响,ArrayList 插入和删除受元素位置影响,add(e) 默认追加到末尾,在指定位置 i 插入和删除时复杂度为 O(n-i),而 LinkedList 链表存储,插入和删除不受位置影响;

③ 内存占用上: LinkedList 存放两个指针,相同数据量下占用更多的空间;

(3) ArrayList 与 Vector 的比较

  • 同步性: Vector 是同步的,因此开销就比 ArrayList 要大,访问速度更慢。
  • 扩容: Vector 每次扩容请求其大小的 2 倍空间,而 ArrayList 是 1.5 倍。且 Vector 可以设置增长空间的大小。

LinkedList

基本性质:

  • 基于双向链表实现,只能顺序访问,但是可以快速地在链表中间插入和删除元素。
  • 线程不安全;
  • LinkedList 可以用作栈、队列和双向队列。

底层结构与初始化

(1) 结构

通过记录 first, last, size 便于边界操作(注:用于队列、栈、双端队列)

队列中每个节点都存放元素,存在初始化情况;

1
2
3
4
5
6
7
8
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}

(2) 初始化

不支持初始情况下给定对应的容量,即基于链表都为无界队列;

1
2
3
4
5
6
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

操作

1、add

添加元素, 最后元素与中间元素, 可处理头结点位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public void add(int index, E element) {
checkPositionIndex(index);

if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
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++;
}
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) /* init 处理 */
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

2、remove

操作不受指定位置的影响;

为双向链表中指定节点的删除;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
}

Vector

基本性质:

  • 底层基于数组保存元素;
  • 随机查询快,增删慢;
  • 线程安全;
  • Java 中的 Stack 通过继承 Vector 实现的;

底层结构与初始化

(1) 结构

① elementCount:初始容量为 10,非懒加载实现;

② capacityIncrement;可以设置每次容量的增长数量;

③ 无 modCount: 同步容器;

1
2
3
Object[] elementData;
int elementCount;
int capacityIncrement;

(2) 初始化

支持 ArrayList 的各种初始化;

支持设置每次的扩容时的容量增长;

1
2
3
4
5
6
7
8
9
10
11
public Vector() {
this(10);
}
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}

操作

1、add / get

对修改底层结构的函数进行加锁同步访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}

public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);

return elementData(index);
}

2、扩容机制

默认扩容为 oldN * 2

可以通过用户设置的正常数量进行控制扩容大小;

1
2
3
4
5
6
7
8
9
10
11
void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? /* 默认扩容 1 倍 */
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}

其他

替代方案

因为 Vector 通过加锁实现,粒度大效率低。

(1) 获得对应线程不安全容器的同步容器

1
2
List<String> list = new ArrayList<>();
List<String> synList = Collections.synchronizedList(list);

(2) 使用并发容器,如 CopyOnWriteArrayList

1
List<String> list = new CopyOnWriteArrayList<>();

CopyOnWriteArrayList

基本性质:

  • 易引起 YongGC, FullGC
  • 不可用于实时的数据, 写操作复制防止并发修改不一致
  • 适合读多写少的情景
  • 读操作无需加锁,写操作加锁

三个设计思想:

  • 读写分离
  • 最终一致性
  • 新开辟空间,解决并发冲突

底层结构与初始化

(1) 结构

① ReentrantLock: 通过此来实现并发访问

1
2
3
4
final transient ReentrantLock lock = new ReentrantLock();
transient volatile Object[] array;
static final long lockOffset;
static final sun.misc.Unsafe UNSAFE;

(2) 初始化

三种初始化方式:

LinkedList 的初始化方式

支持泛型数组初始化

1
2
3
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

操作

(1) add

并发下安全的容器,需要处理并发访问问题、处理复制问题。

包含 lock 加锁获取与释放:

① 获取原数组

② 复制出 len+1 的数组

③ 为新数组末尾复制

④ 修改内部数组指向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray(); /* 获取原数组, volatile 保证可见性 */
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1); /* 复制数组 */
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}

final void setArray(Object[] a) {
array = a;
}

(2) get

无需加锁直接访问, 在 add 操作的同时可访问旧有的数据 ⇒ 实时性得不到保证 。

1
2
3
4
5
6
E get(int index) {         
return get(getArray(), index);
}
E get(Object[] a, int index) {
return (E) a[index];
}

3、迭代方式

通过安全失败实现,将当前数组放入到 Iterator 实现类中作为快照访问。

1
2
3
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}

迭代器中保存某个时间点下底层数组的快照,通过 cursor 来进行向前迭代访问。

1
2
3
4
5
6
7
8
9
10
11
final Object[] snapshot;
int cursor;
COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}

其他

(1) 读写分离

写操作在一个复制的数组上进行,读操作还是在原始数组中进行,读写分离,互不影响;

写操作需要加锁,防止并发写入时导致写入数据丢失;

写操作结束之后需要把原始数组指向新的复制数组;

(2)适用场景

CopyOnWriteArrayList 在写操作的同时允许读操作,大大提高了读操作的性能,因此很适合读多写少的应用场景。

(3) 缺陷

  • 内存占用:在写操作时需要复制一个新的数组,使得内存占用为原来的两倍左右;
  • 数据不一致:读操作不能读取实时性的数据,因为部分写操作的数据还未同步到读数组中。

所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

Set

HashSet

底层结构与初始化

通过一个 HashMap 实现,对应的 Value 为指定的一个 Object

1
2
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

操作

1、add

1
2
3
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

2、remove

1
2
3
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}

LinkedHashSet

基于 LinkedHashMap 实现, HashSet 的子类。

1
2
3
4
5
6
7
8
9
10
11
Set
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
public LinkedHashSet() {
super(16, .75f, true);
}
}

TreeSet

与 HashSet 的区别

① 底层结构:HashSet 基于 hash 表实现,元素无序, 一些方法 add(), remove(), contains() 复杂度为 O(1);

② 有序性: TreeSet 基于红黑树实现,元素有序, add(), remove(), contains() 复杂度为 O(logN);

Queue

PriorityQueue

基本性质:

  • 有序的优先队列;
  • 不可以存放 NULL,NULL 无自然顺序;
  • 非线程安全,入队和出队的时间复杂度为 O(logN);
  • 基于堆结构实现,默认情况下为最小堆;

底层结构与初始化

(1) 底层结构

数组保存的完全二叉树,首元素存放元素值。

堆顶元素有序,默认情况下为最小堆。

comparator: 默认自定义比较器优先于存入对象的自然排序进行比较

1
2
3
4
transient Object[] queue; 
int size = 0;
final Comparator<? super E> comparator;
transient int modCount = 0;

(2) 初始化

可指定初始容量与比较器;

1
2
3
4
5
6
7
static final int DEFAULT_INITIAL_CAPACITY = 11;

PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}

PriorityQueue(int initialCapacity, Comparator<? super E> comparator);

操作

(1) offer

实现:

  • 先将元素放到完全二叉树的尾节点
  • 之后不断上浮调整结构使其符合堆特性

辅助-shiftUp

上浮函数,用于维护最小堆的结构。

赋值替换交换优化;

找出正确位置并放入;

1
2
3
4
5
6
7
8
9
10
11
12
void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}

(2) poll

弹出当前堆顶元素。

实现:

  • 保存堆顶元素;
  • 将堆顶与最末叶子节点交换,之后通过堆顶下沉实现结构的维护;
  • siftDown,下沉函数,最小堆的结构;
  • 通过赋值来替换掉交换操作;
  • 找到元素应该放入的正确位置放入;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
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;
}

(3) remove

remove(o) 删除一个对象,为 Collection 中的方法,需要先进行向下调整后进行向上调整;

实现:

  • 最末叶子节点赋值到当前删除的位置;
  • 让原来的最末叶子节点向下调整;
  • 若结构不合法则向上调整;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else {
E moved = (E) queue[s]; /* 最末叶子节点赋值到当前删除的位置 */
queue[s] = null;
siftDown(i, moved); /* 让原来的最末叶子节点向下调整 */
if (queue[i] == moved) { /* 结构不合法向上调整 */
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}

(4) heapify

初始传入为 Collection 进行堆化处理,借助原始结构,从中间处向上不断下沉处理,相比较每次插入到最末叶子节点进行向上调整效率更高;

完全二叉树中间节点位置 size / 2 - 1;

1
2
3
4
5
6
7
8
void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
heapify();
}
void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--) /* 完全二叉树从上层节点不断向下调整实习 */
siftDown(i, (E) queue[i]);
}

3、扩容

小数据量快速 2 * oldCapacity + 2 扩容,容量大于 64 后进行 1.5 * oldCapacity 扩容;

1
2
3
4
5
6
7
8
9
10
11
void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}

4、迭代访问

通过双向队列 ArrayDeque 实现

1
2
3
4
5
6
7
class Itr implements Iterator<E> {
int cursor = 0;
int lastRet = -1;
ArrayDeque<E> forgetMeNot = null;
E lastRetElt = null;
int expectedModCount = modCount;
}

其他

使用场景

  • 贪心算法选择局部最优;
  • 图论中使用进行优化;
  • 实现哈夫曼树等结构;

ArrayDeque

基于数组实现的双向队列;

可使用 Stack 的 API;

底层结构与初始化

(1) 底层结构

一个数组,两个索引指向队列的头节点和尾部节点。

1
2
3
4
transient Object[] elements;
transient int head;
transient int tail;
private static final int MIN_INITIAL_CAPACITY = 8;

(2) 初始化

1
2
3
4
5
6
7
8
9
10
public ArrayDeque() {
elements = new Object[16];
}
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}

Util

Arrays

1、sort

JDK 中的排序都为稳定排序

算法的执行逻辑:

  • 小数据量使用 INSERT 排序
  • 一定规模数据量使用 QUICK 排序
  • 大数据量使用 MERGE 排序
  • 并非所有大数据量都是 Merge Sort,在不具备结构性时转换成 Quick Sort;

(1) 归并排序

① 小数据量转快速排序

② 通过分配当前大小进行 merge

③ 判断排序数组的结构,不具有时使用快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static void sort(int[] a, int left, int right,
int[] work, int workBase, int workLen) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
int[] run = new int[MAX_RUN_COUNT + 1]; /* aux space to merge */
int count = 0; run[0] = left;
// Check if the array is nearly sorted
for (int k = left; k < right; run[count] = k) {
// ...
/*
* The array is not highly structured,
* use Quicksort instead of merge sort.
*/
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
}
// ...
}

(2) 快速排序

① 小数据量插入排序

1
2
3
4
5
6
7
static void sort(int[] a, int left, int right, boolean leftmost) {
int length = right - left + 1;

// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
if (leftmost) {
}

② 逻辑实现

通过双枢纽元分割实现;

类似 BFPRT 算法中对于枢纽元的选取,将原来期望的复杂度转换成确定的复杂度;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
left part           center part                   right part
+--------------------------------------------------------------+
| < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
+--------------------------------------------------------------+
^ ^ ^
| | |
less k great


left part center part right part
+----------------------------------------------------------+
| == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
+----------------------------------------------------------+
^ ^ ^
| | |
less k great


Partitioning degenerates to the traditional 3-way
(or "Dutch National Flag") schema:

left part center part right part
+-------------------------------------------------+
| < pivot | == pivot | ? | > pivot |
+-------------------------------------------------+
^ ^ ^
| | |
less k great

(3) 插入排序

为快速排序中的子过程实现;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
if (length < INSERTION_SORT_THRESHOLD) {
if (leftmost) {
/*
* Traditional (without sentinel) insertion sort,
* optimized for server VM, is used in case of
* the leftmost part.
*/
for (int i = left, j = i; i < right; j = ++i) {
int ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == left) {
break;
}
}
a[j + 1] = ai;
}
} else {
/*
* Skip the longest ascending sequence.
*/
do {
if (left >= right) {
return;
}
} while (a[++left] >= a[left - 1]);

/*
* Every element from adjoining part plays the role
* of sentinel, therefore this allows us to avoid the
* left range check on each iteration. Moreover, we use
* the more optimized algorithm, so called pair insertion
* sort, which is faster (in the context of Quicksort)
* than traditional implementation of insertion sort.
*/
for (int k = left; ++left <= right; k = ++left) {
int a1 = a[k], a2 = a[left];

if (a1 < a2) {
a2 = a1; a1 = a[left];
}
while (a1 < a[--k]) {
a[k + 2] = a[k];
}
a[++k + 1] = a1;

while (a2 < a[--k]) {
a[k + 1] = a[k];
}
a[k + 1] = a2;
}
int last = a[right];

while (last < a[--right]) {
a[right + 1] = a[right];
}
a[right + 1] = last;
}
return;
}

2、binarySearch

计算 mid mid = (low + high) >>> 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Like public version, but without range checks.
private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
Object key) {
int low = fromIndex;
int high = toIndex - 1;

while (low <= high) {
int mid = (low + high) >>> 1; //
@SuppressWarnings("rawtypes")
Comparable midVal = (Comparable)a[mid];
@SuppressWarnings("unchecked")
int cmp = midVal.compareTo(key);

if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}

3、asList / subList

不推荐使用,返回的 List 修改会有问题。

Collections

1、提供一些容器的空实现:作为容器为空的情况下的返回值,规避空指针问题。

1
2
3
4
public static final List EMPTY_LIST = new EmptyList<>();
public static final <T> List<T> emptyList() {
return (List<T>) EMPTY_LIST;
}

2、提供单个元素的集合:

方便传递方法的参数

1
2
3
public static <T> List<T> singletonList(T o) {
return new SingletonList<>(o);
}

3、sort

JDK8 中借助 List 中自带的 sort() 函数调用实现;

4、binarySearch

对 List 进行二分搜索

根据底层是数组还是链表采用不同的处理:

① 数组: 数组随机访问定位实现

② 链表: 接着 ListIterator 实现二分查找

在 binarySearch()⽅法中,它要判断传⼊的list 是否 RamdomAccess 的实例,如果是,调⽤ indexedBinarySearch() ⽅法,如果不是,那么调⽤ iteratorBinarySearch() ⽅法

1
2
3
4
5
6
7
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}

5、提供将不安全的容器转换为同步容器

1
public static <T> List<T> synchronizedList(List<T> list)