解析 Java 集合工具類：功能與實(shí)踐
在編程的廣袤領(lǐng)域中，集合是一個(gè)至關(guān)重要的概念，它猶如數(shù)據(jù)的魔法盒子，承載著各種元素的有序或無序組合。而集合工具類，則像是一把神奇的鑰匙，為我們開啟了高效處理和操作這些集合的大門。
一、詳解Java集合常用的方法
1. 集合判空
日常業(yè)務(wù)功能開發(fā)，為保證程序的健壯性，判空操作是必不可少的，筆者在日常審查代碼時(shí)候會(huì)看到很多開發(fā)會(huì)使用size方法進(jìn)行判空，這種方案在常規(guī)集合容器下沒有任何問題，但是在某些特殊場(chǎng)景下，這個(gè)判空就可能存在性能問題：
if (list.size() == 0) {
//do something
}最典型的就是ConcurrentLinkedQueue，打開其內(nèi)部源碼即可看到，該容器獲取元素?cái)?shù)時(shí)是從頭節(jié)點(diǎn)開始遍歷獲取的：
public int size() {
int count = 0;
//從頭節(jié)點(diǎn)開始遍歷累加count
for (Node<E> p = first(); p != null; p = succ(p))
if (p.item != null)
// Collection.size() spec says to max out
if (++count == Integer.MAX_VALUE)
break;
return count;
}所以一般情況下，我們更建議使用isEmpty，該方法無論從語義還是實(shí)現(xiàn)上，都避免了掃描容器的開銷，是筆者比較推薦的一種判空方式：
public boolean isEmpty() {
return size == 0;
}2. 列表集合轉(zhuǎn)Map
集合轉(zhuǎn)Map時(shí)可以直接使用java8版本的流編程，對(duì)應(yīng)代碼示例如下：
ArrayList<Person> list = new ArrayList<>();
list.add(new Person("jack", 18));
list.add(new Person("rose", 16));
//用流編程進(jìn)行轉(zhuǎn)換
list.stream().collect(Collectors.toMap(Person::getName, Person::getAge));對(duì)應(yīng)的我們也給出輸出結(jié)果：
16:17:35.383 [main] INFO com.sharkChili.Main - [Person(name=jack, age=18), Person(name=rose, age=16)]需要注意一點(diǎn)，我們使用的時(shí)候盡可能保證value非空，要知道toMap底層用到了HashMap的方法，該方法中如果判斷value為空會(huì)拋出空指針異常：
@Override
public V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
//如果value為空則拋出空指針異常
if (value == null)
throw new NullPointerException();
//......
}3. 集合遍歷時(shí)移除元素(重點(diǎn))
不建議使用for循環(huán)等方式進(jìn)行remove，會(huì)拋出ConcurrentModificationException ，這就是單線程狀態(tài)下產(chǎn)生的 fail-fast 機(jī)制。
fail-fast 機(jī)制，即快速失敗機(jī)制，是java集合(Collection)中的一種錯(cuò)誤檢測(cè)機(jī)制。當(dāng)在迭代集合的過程中該集合在結(jié)構(gòu)上發(fā)生改變的時(shí)候，就有可能會(huì)發(fā)生fail-fast，即拋出ConcurrentModificationException異常。fail-fast機(jī)制并不保證在不同步的修改下一定會(huì)拋出異常，它只是盡最大努力去拋出，所以這種機(jī)制一般僅用于檢測(cè)bug。
所以我們建議jdk8情況下使用這種方式進(jìn)行動(dòng)態(tài)移除，即使用removeIf方法，該方法已經(jīng)為我們做好了封裝無論從使用還是語義上，這種寫法更加友好：
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= 10; ++i) {
list.add(i);
}
//移除元素為5的
list.removeIf(integer -> integer == 5);這一點(diǎn)，我們從底層的源碼就可以知道，它為我們做好了：
- 獲取迭代器
- 遍歷元素
- 基于迭代器安全刪除元素
對(duì)應(yīng)我們給出這段源碼實(shí)現(xiàn)，該代碼位于Collection下：
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
//獲取迭代器
final Iterator<E> each = iterator();
//檢查是否有下一個(gè)元素
while (each.hasNext()) {
//如果斷言(即我們外部傳入的判斷條件)返回true，將元素刪除
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}4. 集合去重
集合去重可以利用 Set 元素唯一的特性且通過O(1)級(jí)別的元素定位，可以快速對(duì)一個(gè)集合進(jìn)行去重操作，避免使用 List 的 contains() 進(jìn)行掃描元素的性能開銷:
如下代碼所示，list去重需要調(diào)用contains，要遍歷數(shù)組，而set底層用hash計(jì)算，如果散列良好情況下判重只需要O(1)
int size = 10_0000;
//List元素去重
List<Integer> resultList = new ArrayList<>(size);
long start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
if (!resultList.contains(i)) {
resultList.add(i);
}
}
long end = System.currentTimeMillis();
System.out.println("List去重:" + (end - start));
//set集合去重
start = System.currentTimeMillis();
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < size; i++) {
set.add(i);
}
end = System.currentTimeMillis();
System.out.println("HashSet去重:" + (end - start));對(duì)應(yīng)我們也給出輸出結(jié)果來比對(duì)一下兩個(gè)集合之間的性能差異：
List去重:4353
HashSet去重:85. 集合轉(zhuǎn)數(shù)組
使用集合轉(zhuǎn)數(shù)組的方法，一般使用的是集合的 toArray(T[] array)這個(gè)方法，我們只需傳入數(shù)組首元素引用地址即可：
List<String> list = Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h");
//集合轉(zhuǎn)數(shù)組
String[] array = list.toArray(new String[0]);這一點(diǎn)我們查看Arrays的toArray實(shí)現(xiàn)詳情就知道，該方法會(huì)獲取當(dāng)前需要轉(zhuǎn)為數(shù)組的列表大小，然后從列表首元素地址開始將元素我們傳入的數(shù)組引用空間中：
public <T> T[] toArray(T[] a) {
//獲取列表元素大小
int size = size();
//......
//基于傳入元素地址將元素復(fù)制到傳入的數(shù)組地址空間中
System.arraycopy(this.a, 0, a, 0, size);
//......
return a;
}6. 數(shù)組轉(zhuǎn)集合
使用工具類 Arrays.asList() 把數(shù)組轉(zhuǎn)換成集合時(shí)，轉(zhuǎn)成的集合是Arrays工具類內(nèi)部的ArrayList：
Integer[] nums = new Integer[10];
for (int i = 0; i < 10; i++) {
nums[i] = i;
}
List<Integer> myList = Arrays.asList(nums);需要注意的是AbstractList不能使用其修改集合相關(guān)的方法，它是一個(gè)只讀的容器， 它并沒有重寫 add/remove/clear 方法，所以會(huì)拋出 UnsupportedOperationException 異常，這一點(diǎn)我們查看AbstractList源碼即可知曉這一點(diǎn)：
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
public E remove(int index) {
throw new UnsupportedOperationException();
}二、詳解Java集合工具類
1. 常見集合排序操作API
Java內(nèi)置了很多使用的集合操作的api，這里我們不妨列一下方法清單，讀者可以基于注釋熟悉一下這些API的使用：
void reverse(List list)//反轉(zhuǎn)
void shuffle(List list)//隨機(jī)排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序邏輯
void swap(List list, int i , int j)//交換兩個(gè)索引位置的元素
void rotate(List list, int distance)//旋轉(zhuǎn)。當(dāng)distance為正數(shù)時(shí)，將list后distance個(gè)元素整體移到前面。當(dāng)distance為負(fù)數(shù)時(shí)，將 list的前distance個(gè)元素整體移到后面2. 集合排序
升序排序我們只需將列表傳入sort方法，其底層排序的工作機(jī)制稍微會(huì)做介紹，這里我們先熟悉一下使用方法：
//隨機(jī)生成長(zhǎng)度為10的列表
List<Integer> list = RandomUtil.randomEleList(IntStream.range(0, 100).boxed().collect(Collectors.toList()), 10);
//打印排序前的列表
System.out.println(list);
System.out.println("Collections 升序排序:");
//排序并打印排序后的結(jié)果
Collections.sort(list);
System.out.println(list);對(duì)應(yīng)的輸出結(jié)果如下：
[16, 84, 72, 18, 42, 93, 55, 28, 47, 14]
Collections 升序排序:
[14, 16, 18, 28, 42, 47, 55, 72, 84, 93]sort方法同樣是支持倒敘的排序的，對(duì)應(yīng)的我們給出倒敘的比較器作為參數(shù)即可：
//隨機(jī)生成長(zhǎng)度為10的列表
List<Integer> list = RandomUtil.randomEleList(IntStream.range(0, 100).boxed().collect(Collectors.toList()), 10);
//打印排序前的列表
System.out.println(list);
//倒敘排序并打印
System.out.println("Collections 倒敘排序:");
Collections.sort(list, Comparator.reverseOrder());
System.out.println(list);對(duì)應(yīng)的我們也給出輸出結(jié)果:
[65, 84, 40, 27, 11, 24, 90, 54, 57, 6]
Collections 倒敘排序:
[90, 84, 65, 57, 54, 40, 27, 24, 11, 6]3. 列表翻轉(zhuǎn)
reverse方法就是將我們?cè)貎?nèi)部按照倒敘反轉(zhuǎn)一下，對(duì)應(yīng)我們給出代碼示例：
//隨機(jī)生成長(zhǎng)度為10的列表
List<Integer> list = RandomUtil.randomEleList(IntStream.range(0, 100).boxed().collect(Collectors.toList()), 10);
//打印排序前的列表
System.out.println(list);
//將列表元素翻轉(zhuǎn)一圈并打印
System.out.println("Collections 翻轉(zhuǎn):");
Collections.reverse(list);
System.out.println(list);可以看到，翻轉(zhuǎn)后的數(shù)值按照列表倒敘進(jìn)行排列了：
[17, 84, 53, 20, 70, 29, 15, 61, 63, 82]
Collections 翻轉(zhuǎn):
[82, 63, 61, 15, 29, 70, 20, 53, 84, 17]4. 列表隨機(jī)排列
shuffle顧名思義即洗牌的意思，它會(huì)將列表內(nèi)部元素順序打亂
//隨機(jī)生成長(zhǎng)度為10的列表
List<Integer> list = RandomUtil.randomEleList(IntStream.range(0, 100).boxed().collect(Collectors.toList()), 10);
//打印排序前的列表
System.out.println(list);
//針對(duì)列表進(jìn)行隨機(jī)排序
System.out.println("Collections 隨機(jī)排序:");
Collections.shuffle(list);
System.out.println(list);輸出結(jié)果:
[64, 24, 63, 94, 41, 76, 60, 69, 43, 27]
Collections 隨機(jī)排序:
[63, 64, 27, 41, 60, 24, 94, 69, 43, 76]5. 列表整體移動(dòng)
rotate算是比較少用的api，讀者可以簡(jiǎn)單了解一下，這個(gè)方法會(huì)將列表中所有元素斗向前移動(dòng)，對(duì)于列表末尾的元素會(huì)移動(dòng)到列表首部，具體算法筆者會(huì)在后面的源碼講解進(jìn)行分析，這里我們了解一下其使用效果：
//隨機(jī)生成長(zhǎng)度為10的列表
List<Integer> list = RandomUtil.randomEleList(IntStream.range(0, 100).boxed().collect(Collectors.toList()), 10);
//打印排序前的列表
System.out.println(list);
//將列表元素全部向前移動(dòng)一步
System.out.println("Collections 所有元素向前移動(dòng)一步:");
Collections.rotate(list, 1);
System.out.println(list);輸出結(jié)果：
[4, 80, 35, 52, 28, 79, 17, 61, 33, 11]
Collections 所有元素向前移動(dòng)一步:
[11, 4, 80, 35, 52, 28, 79, 17, 61, 33]6. 兩數(shù)交換
swap可以指定兩數(shù)索引位置元素交換，如下代碼，我們將索引0和索引1位置的元素進(jìn)行交換：
//隨機(jī)生成長(zhǎng)度為10的列表
List<Integer> list = RandomUtil.randomEleList(IntStream.range(0, 100).boxed().collect(Collectors.toList()), 10);
//打印排序前的列表
System.out.println(list);
//打印兩數(shù)交換后的列表
System.out.println("Collections 交換兩個(gè)索引位置元素:");
Collections.swap(list, 0, 1);
System.out.println(list);對(duì)應(yīng)輸出結(jié)果如下：
[24, 8, 91, 59, 34, 13, 78, 44, 84, 86]
Collections 交換兩個(gè)索引位置元素:
[8, 24, 91, 59, 34, 13, 78, 44, 84, 86]三、詳解Java集合工具類算法底層實(shí)現(xiàn)
1. Collections.sort底層實(shí)現(xiàn)
查看sort方法底層實(shí)現(xiàn)可以看出，除非開發(fā)顯式配置歸并排序才會(huì)調(diào)用legacyMergeSort進(jìn)行歸并排序，否則一律使用TimSort進(jìn)行列表排序：
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
//如果配置指定要求才使用歸并排序
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
//默認(rèn)使用TimSort排序
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}而TimSort的sort方法就是排序核心的實(shí)現(xiàn)，TimSort是自適應(yīng)的、混合的、穩(wěn)定的排序算法。是基于歸并和二分插入排序優(yōu)點(diǎn)結(jié)合的排序算法。復(fù)雜度最壞的情況下只有O(nlogn)，最壞的情況下，空間復(fù)雜度為O(n/2)。
這個(gè)方法在基數(shù)閾值的選取和排序的實(shí)現(xiàn)細(xì)節(jié)都做了機(jī)制都做了相對(duì)極致的優(yōu)化，當(dāng)列表元素小于32的情況下，TimSort會(huì)直接通過二分插入排序直接完成排序操作。
二分插入排序法是插入排序法的升級(jí)版本，如下所示，我們都知道插入排序后左邊的元素都是有序的，如果使用常規(guī)二分排序，那么最壞情況下插入時(shí)間是O(n)，所以我們基于左邊有序這個(gè)特點(diǎn)改用二分插入的方式完成排序優(yōu)化了這個(gè)問題。
當(dāng)右邊元素進(jìn)行插入時(shí)，不斷在左邊進(jìn)行二分運(yùn)算定位到mid元素：
- 如果mid索引對(duì)應(yīng)的元素小于插入元素，說明left索引元素值太小，需要向右移動(dòng)找到下一個(gè)折中值。
- 如果mid索引元素值大于待插入的元素值，說明right坐標(biāo)對(duì)應(yīng)的元素值太大，需要讓right坐標(biāo)向左移動(dòng)找到小一點(diǎn)的中間值。
通過這樣的二分運(yùn)算最終會(huì)找到一個(gè)小于或者等于待入元素坐標(biāo)left作為插入索引并將元素插入，然后其余元素全部向后移動(dòng)一位：
對(duì)此我們也給出TimSort排序的前半部分實(shí)現(xiàn)，可以看到這段代碼在進(jìn)行二分排序前會(huì)先定位開頭有序的最小區(qū)間initRunLen ，如下圖所示，這個(gè)數(shù)組索引3之前的元素都是正向元素的，所以排序是從索引4開始：
對(duì)應(yīng)的我們也給出這段代碼的整體實(shí)現(xiàn)：
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
T[] work, int workBase, int workLen) {
int nRemaining = hi - lo; //計(jì)算出待排序的范圍
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// 若小于32則直接調(diào)用`binarySort`
if (nRemaining < MIN_MERGE) {
//計(jì)算出lo 到 hi 范圍找出有序的長(zhǎng)度，若是降序則轉(zhuǎn)為升序后返回
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
//使用二分插入法將hi以內(nèi)未排序的元素插入到數(shù)組中
binarySort(a, lo, hi, lo + initRunLen, c);
//完成后直接返回
return;
}
//......
}countRunAndMakeAscending代碼的實(shí)現(xiàn)，該方法本質(zhì)上就是從頭開始比對(duì)元素：
- 如果一開始runHi 元素大于其后一個(gè)元素，則正序方式先前遍歷，runHi 不斷前行，找到正向有序的最小區(qū)間。
- 如果一開始runHi 元素小于后一個(gè)元素，則按照倒敘方式進(jìn)行編譯，runHi 不斷前行，找到逆序的最小區(qū)間。
private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
Comparator<? super T> c) {
assert lo < hi;
// 待比較的值從lo+1 開始
int runHi = lo + 1;
if (runHi == hi)
return 1;
// 第一次比較若小于0就進(jìn)入循環(huán)，找到最小范圍的降序子數(shù)組，循環(huán)結(jié)束后翻轉(zhuǎn)為升序
if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
runHi++;
//循環(huán)結(jié)束后翻轉(zhuǎn)為升序
reverseRange(a, lo, runHi);
} else {
//反之就尋找升序子數(shù)組
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
runHi++;
}
//runHi - lo即我們本次找到的有序子數(shù)組的長(zhǎng)度
return runHi - lo;
}然后我們?cè)俳榻BbinarySort，如上文所說不斷通過二分運(yùn)算比對(duì)mid和插入元素的值，然后進(jìn)行插入，這里筆者特殊說明一下binarySort對(duì)于二分插入排序的優(yōu)化細(xì)節(jié)，從代碼中可以看到，當(dāng)二分插入排序定位到合適的位置之后，會(huì)判斷這個(gè)位置和插入元素之間的距離，如果兩者距離小于2，則直接通過簡(jiǎn)單的元素交換：
反之，如果待插入的位置和插入元素索引位置大于2，則找到left及其前方元素批量先前移動(dòng)一格，然后騰出一塊空間將元素插入：
對(duì)應(yīng)的我們給出binarySort的代碼實(shí)現(xiàn)細(xì)節(jié)：
private static <T> void binarySort(T[] a, int lo, int hi, int start,
Comparator<? super T> c) {
//......
for ( ; start < hi; start++) {
T pivot = a[start];
// 二分搜索范圍設(shè)置為[lo,start)
int left = lo;
int right = start;
assert left <= right;
//通過二分法，找到合適插入位置
while (left < right) {
//通過位運(yùn)算高效實(shí)現(xiàn)/2得到一個(gè)中間索引mid
int mid = (left + right) >>> 1;
//如果中間值大于插入元素，則right設(shè)置為mid，視圖找到小一點(diǎn)的mid
if (c.compare(pivot, a[mid]) < 0)
right = mid;
else
//如果中間值小于插入元素，則left等于mid找到一個(gè)大一點(diǎn)的mid
left = mid + 1;
}
assert left == right;
int n = start - left; // 計(jì)算需要移動(dòng)的步數(shù)
// 這里正是設(shè)計(jì)者的精華所在，可以看到如果只要移動(dòng)1-2步，直接交換即可，若大于兩步則直接指定數(shù)組范圍進(jìn)行批量拷貝
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
default: System.arraycopy(a, left, a, left + 1, n);
}
a[left] = pivot;
}
}當(dāng)元素大于32的時(shí)候，TimSort排序算法就會(huì)進(jìn)行更近一步的設(shè)計(jì)，即針對(duì)當(dāng)前數(shù)組生成無數(shù)個(gè)子單元進(jìn)行二分插入排序，然后基于每個(gè)有序的子單元進(jìn)行歸并從而得到不斷歸并得到一個(gè)有序集合：
對(duì)應(yīng)的我們給出TimSort后續(xù)代碼，整體邏輯與筆者說明一致，建議讀者結(jié)合筆者說明和注釋理解：
TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
int minRun = minRunLength(nRemaining);
do {
// 計(jì)算出最大的有序范圍的索引
int runLen = countRunAndMakeAscending(a, lo, hi, c);
//若小于minRun，則說明進(jìn)行排序的數(shù)組太小，需要指定一個(gè)范圍排序一下
if (runLen < minRun) {
//nRemaining 為當(dāng)前待排序的范圍大小，minRun 為計(jì)算出來至少要排序的范圍。若nRemaining 小于minRun ，則取nRemaining ，意味需要排序的范圍就剩幾個(gè)了直接用這幾個(gè)值排個(gè)序就好了。反之則取minRun 進(jìn)行二分插入排序
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen, c);
//完成后force的值就代表當(dāng)前經(jīng)歷排序的元素個(gè)數(shù)，存到runLen中，作為后續(xù)合并的依據(jù)
runLen = force;
}
// 將lo到runLen的值存到棧中，后續(xù)歸并會(huì)用到
ts.pushRun(lo, runLen);
//將當(dāng)前排序的范圍數(shù)組歸并到已排序的數(shù)組中
ts.mergeCollapse();
// 起始位置加到runLen之后
lo += runLen;
//待排序的值減去已排序的長(zhǎng)度
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;由于這篇文章主要描述Java集合工具類的使用，所以就不展開細(xì)講了。
2. rotate列表旋轉(zhuǎn)算法的實(shí)現(xiàn)
rotate旋轉(zhuǎn)算法底層也有很多的巧妙設(shè)計(jì)，步入其源碼可以看到：
- 如果是RandomAccess即具備隨機(jī)訪問特性的數(shù)組或者數(shù)組大小小于100時(shí)使用rotate1方法進(jìn)行旋轉(zhuǎn)
- 反之說明該列表是不具備隨機(jī)范文的鏈表則調(diào)用rotate2進(jìn)行元素旋轉(zhuǎn)
對(duì)應(yīng)的我們給出代碼的頂層實(shí)現(xiàn)：
public static void rotate(List<?> list, int distance) {
//如果是具備隨機(jī)訪問特性或者元素小于100則調(diào)用rotate1
if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
rotate1(list, distance);
else //反之調(diào)用rotate2
rotate2(list, distance);
}我們先來說說rotate1方法的實(shí)現(xiàn)，邏輯比較簡(jiǎn)單，計(jì)算出移動(dòng)的步數(shù)之后通過list的set方法將元素設(shè)置到移動(dòng)的位置上，通過set方法得到該位置上原有的元素，再將該元素移動(dòng)到旋轉(zhuǎn)后的的索引上：
對(duì)應(yīng)的我們給出這段實(shí)現(xiàn)的源碼，讀者可結(jié)合說明了解核心流程：
private static <T> void rotate1(List<T> list, int distance) {
int size = list.size();
if (size == 0)
return;
//計(jì)算移動(dòng)的步數(shù)
distance = distance % size;
//若為負(fù)數(shù)則加上數(shù)組大小 即可 (向左走n步)==(向右走數(shù)組大小+n步)
if (distance < 0)
distance += size;
if (distance == 0)
return;
//移動(dòng)
for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
T displaced = list.get(cycleStart);
int i = cycleStart;
do {
i += distance;
//若大于數(shù)組大小則減去數(shù)組大小得出最終要走的步
if (i >= size)
i -= size;
//賦值并返回舊元素進(jìn)行下一次do while旋轉(zhuǎn)
displaced = list.set(i, displaced);
nMoved ++;
} while (i != cycleStart);
}
}走到rotate2這個(gè)函數(shù)則說明這個(gè)數(shù)組為不具備隨機(jī)訪問性的鏈表，為了保證性能，該方法會(huì)通過計(jì)算的方式得到計(jì)算出一個(gè)批量移動(dòng)的區(qū)間，然后基于這兩個(gè)整體進(jìn)行批量的移動(dòng)。
例如我們現(xiàn)在有一個(gè)鏈表，內(nèi)部包含0-100一共101個(gè)元素，元素值為0~100，剛剛好可以執(zhí)行rotate2方法，假設(shè)我們希望全體向前移動(dòng)一步，rotate2算法會(huì)通過-distance % size得到100，即[0,100]區(qū)間是只需先前移動(dòng)的區(qū)間，而[101]是需要移動(dòng)到列表前面的區(qū)間，rotate2的執(zhí)行步驟為：
- 將區(qū)間1翻轉(zhuǎn)，得到99~0。
- 將區(qū)間2翻轉(zhuǎn)，得到100，此時(shí)列表排列為99~0、100。
- 最后將整個(gè)列表進(jìn)行一次翻轉(zhuǎn)，將100移動(dòng)到列表最前面的同時(shí)，也將只需先前移動(dòng)一格的區(qū)間放到100的后面：
對(duì)應(yīng)的我們也給出rotate2的代碼實(shí)現(xiàn)，整體思路和筆者說明的一致，就是通過-distance % size計(jì)算得到只需先前移動(dòng)和要翻轉(zhuǎn)到列表前面的兩個(gè)區(qū)間，然后執(zhí)行：
- 只需向前移動(dòng)的區(qū)間1翻轉(zhuǎn)。
- 移動(dòng)到列表首部的區(qū)間2翻轉(zhuǎn)。
- 整個(gè)列表翻轉(zhuǎn)將區(qū)間2提前。
private static void rotate2(List<?> list, int distance) {
int size = list.size();
if (size == 0)
return;
//[0,mid]只需向前移動(dòng)distance步，(mid,list.size()-1]移動(dòng)到列表前面
int mid = -distance % size;
if (mid < 0)
mid += size;
if (mid == 0)
return;
//翻轉(zhuǎn)[0,mid]
reverse(list.subList(0, mid));
//翻轉(zhuǎn)(mid,list.size()-1]
reverse(list.subList(mid, size));
//整體移動(dòng)，將(mid,list.size()-1]翻轉(zhuǎn)到列表前方，同時(shí)保證[0,mid]有序
reverse(list);
}四、詳解jdk常見搜索比對(duì)函數(shù)
1. 核心api概覽
jdk也為我提供了很多使用的搜索和比較統(tǒng)計(jì)函數(shù)，對(duì)應(yīng)的函數(shù)列表如下：
int binarySearch(List list, Object key)//對(duì)List進(jìn)行二分查找，返回索引，注意List必須是有序的
int max(Collection coll)//根據(jù)元素的自然順序，返回最大的元素。 類比int min(Collection coll)
int max(Collection coll, Comparator c)//根據(jù)定制排序，返回最大元素，排序規(guī)則由Comparatator類控制。類比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//統(tǒng)計(jì)元素出現(xiàn)次數(shù)
int indexOfSubList(List list, List target)//統(tǒng)計(jì)target在list中第一次出現(xiàn)的索引，找不到則返回-1，類比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替換舊元素2. 使用示例
System.out.println("Collections 二分搜索法(注意數(shù)組并需有序):");
Collections.sort(list);
int idx = Collections.binarySearch(list, 1);
System.out.println(idx);
System.out.println("Collections 求最大值:");
System.out.println(Collections.max(list));
System.out.println("Collections 按自定義方式找最大值:");
System.out.println(Collections.max(list, Comparator.reverseOrder()));
System.out.println("Collections 用指定元素替代list中所有的元素:");
Collections.fill(list, 5);
System.out.println(list);
System.out.println("Collections 統(tǒng)計(jì)頻次:");
System.out.println(Collections.frequency(list, 5));
System.out.println("Collections 返回target子集在list中第一次出現(xiàn)的位置:");
List<Integer> list1 = Arrays.asList(1, 2, 3, 4, 5, 6);
List<Integer> target = Arrays.asList(3, 4);
System.out.println(Collections.indexOfSubList(list1, target));//返回target子集在list中第一次出現(xiàn)的位置
System.out.println("Collections replaceAll:");
Collections.replaceAll(list, 5, 6);
System.out.println(list);3. 詳解洗牌算法
這里我們著重說明一下隨機(jī)洗牌算法的實(shí)現(xiàn)，邏輯比較簡(jiǎn)單：
- 如果列表具備隨機(jī)訪問或者size小于100，可以直接從size開始倒敘調(diào)用swap進(jìn)行隨機(jī)元素交換。
- 反之說明當(dāng)前列表是大于100的鏈表，首先將這些元素存到一個(gè)具備隨機(jī)訪問的數(shù)組中，然后基于這個(gè)數(shù)組進(jìn)行隨機(jī)swap交換，再存入鏈表中，所以性能表現(xiàn)會(huì)差一些。
對(duì)應(yīng)的源碼如下：
public static void shuffle(List<?> list, Random rnd) {
int size = list.size();
//若小于SHUFFLE_THRESHOLD 或者是RandomAccess類則從高位索引與隨機(jī)一個(gè)低位索引交換值完成洗牌
if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
for (int i=size; i>1; i--)
//將i-1位置元素和隨機(jī)一個(gè)位置進(jìn)行交換
swap(list, i-1, rnd.nextInt(i));
} else {
//反之轉(zhuǎn)成數(shù)組，再遍歷數(shù)組的值存到list中
Object arr[] = list.toArray();
for (int i=size; i>1; i--)
////將i-1位置元素和隨機(jī)一個(gè)位置進(jìn)行交換
swap(arr, i-1, rnd.nextInt(i));
//然后設(shè)置到鏈表中
ListIterator it = list.listIterator();
for (int i=0; i<arr.length; i++) {
it.next();
it.set(arr[i]);
}
}
}五、同步控制
1. 同步控制常見函數(shù)
注意，非必要不要使用這種API，效率極低
synchronizedCollection(Collection<T> c) //返回指定 collection 支持的同步（線程安全的）collection。
synchronizedList(List<T> list)//返回指定列表支持的同步（線程安全的）List。
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步（線程安全的）Map。
synchronizedSet(Set<T> s) //返回指定 set 支持的同步（線程安全的）set。2. 使用示例
可以看到筆者在下面貼出使用Collections.synchronizedList包裝后的list的add方法，鎖的粒度很大，在多線程操作情況下，性能非常差。
我們就以synchronizedList為例查看其add方法，可以看到其實(shí)現(xiàn)線程安全的方式很簡(jiǎn)單，直接在工作代碼上synchronized ，在高并發(fā)情況下，很可能造成大量線程阻塞
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}示例代碼如下，我們分別開兩個(gè)線程，往數(shù)組中添加1000個(gè)數(shù)組，可以看到筆者注釋代碼中用了普通list，以及通過Collections.synchronizedList后的list，感興趣的讀者可以基于下面代碼測(cè)試是否線程安全
@Test
public void ThreadSafe() {
CountDownLatch latch = new CountDownLatch(1);
// List<Integer> list = new ArrayList<>();
List<Integer> list = Collections.synchronizedList(new ArrayList<>());
ExecutorService threadPool = Executors.newFixedThreadPool(2);
for (int i = 0; i < 2; i++) {
threadPool.submit(() -> {
try {
latch.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
for (int j = 0; j < 1000; j++) {
list.add(j);
}
});
}
latch.countDown();
threadPool.shutdown();
while (!threadPool.isTerminated()) {
}
System.out.println(list.size());
}輸出結(jié)果為2000，說明該方法確實(shí)實(shí)現(xiàn)了線程安全
2000
