写在文章开头
在编程的广袤领域中，集合是一个至关重要的概念，它犹如数据的魔法盒子，承载着各种元素的有序或无序组合。而集合工具类，则像是一把神奇的钥匙，为我们开启了高效处理和操作这些集合的大门。
Hi，我是 sharkChili ，是个不断在硬核技术上作死的技术人，是 CSDN的博客专家 ，也是开源项目 Java Guide 的维护者之一，熟悉 Java 也会一点 Go ，偶尔也会在 C源码 边缘徘徊。写过很多有意思的技术博客，也还在研究并输出技术的路上，希望我的文章对你有帮助，非常欢迎你关注我的公众号： 写代码的SharkChili 。
同时也非常欢迎你star我的开源项目mini-redis:https://github.com/shark-ctrl/mini-redis
因为近期收到很多读者的私信，所以也专门创建了一个交流群，感兴趣的读者可以通过上方的公众号获取笔者的联系方式完成好友添加，点击备注 “加群” 即可和笔者和笔者的朋友们进行深入交流。
详解Java集合常用的方法
集合判空
日常业务功能开发，为保证程序的健壮性，判空操作是必不可少的，笔者在日常审查代码时候会看到很多开发会使用size方法进行判空，这种方案在常规集合容器下没有任何问题，但是在某些特殊场景下，这个判空就可能存在性能问题：
if (list.size() == 0) {
//do something
}
最典型的就是ConcurrentLinkedQueue
，打开其内部源码即可看到，该容器获取元素数时是从头节点开始遍历获取的：
public int size() {
int count = 0;
//从头节点开始遍历累加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
，该方法无论从语义还是实现上，都避免了扫描容器的开销，是笔者比较推荐的一种判空方式：
public boolean isEmpty() {
return size == 0;
}
列表集合转Map
集合转Map
时可以直接使用java8
版本的流编程，对应代码示例如下：
ArrayList<Person> list = new ArrayList<>();
list.add(new Person("jack", 18));
list.add(new Person("rose", 16));
//用流编程进行转换
list.stream().collect(Collectors.toMap(Person::getName, Person::getAge));
对应的我们也给出输出结果：
16:17:35.383 [main] INFO com.sharkChili.Main - [Person(name=jack, age=18), Person(name=rose, age=16)]
需要注意一点，我们使用的时候尽可能保证value
非空，要知道toMap
底层用到了HashMap
的方法，该方法中如果判断value
为空会抛出空指针异常：
@Override
public V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
//如果value为空则抛出空指针异常
if (value == null)
throw new NullPointerException();
//......
}
集合遍历时移除元素(重点)
不建议使用for
循环等方式进行remove
，会抛出ConcurrentModificationException
，这就是单线程状态下产生的 fail-fast
机制。
fail-fast 机制，即快速失败机制，是java集合(Collection)中的一种错误检测机制。当在迭代集合的过程中该集合在结构上发生改变的时候，就有可能会发生fail-fast，即抛出ConcurrentModificationException异常。fail-fast机制并不保证在不同步的修改下一定会抛出异常，它只是尽最大努力去抛出，所以这种机制一般仅用于检测bug。
所以我们建议jdk8
情况下使用这种方式进行动态移除，即使用removeIf方法，该方法已经为我们做好了封装无论从使用还是语义上，这种写法更加友好：
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= 10; ++i) {
list.add(i);
}
//移除元素为5的
list.removeIf(integer -> integer == 5);
这一点，我们从底层的源码就可以知道，它为我们做好了：
获取迭代器 遍历元素 基于迭代器安全删除元素
对应我们给出这段源码实现，该代码位于Collection
下：
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
//获取迭代器
final Iterator<E> each = iterator();
//检查是否有下一个元素
while (each.hasNext()) {
//如果断言(即我们外部传入的判断条件)返回true，将元素删除
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}
集合去重
集合去重可以利用 Set 元素唯一的特性且通过O(1)级别的元素定位，可以快速对一个集合进行去重操作，避免使用 List
的 contains()
进行扫描元素的性能开销:
如下代码所示，list
去重需要调用contains
，要遍历数组，而set底层用hash计算，如果散列良好情况下判重只需要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));
对应我们也给出输出结果来比对一下两个集合之间的性能差异：
List去重:4353
HashSet去重:8
集合转数组
使用集合转数组的方法，一般使用的是集合的 toArray(T[] array)
这个方法，我们只需传入数组首元素引用地址即可：
List<String> list = Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h");
//集合转数组
String[] array = list.toArray(new String[0]);
这一点我们查看Arrays
的toArray
实现详情就知道，该方法会获取当前需要转为数组的列表大小，然后从列表首元素地址开始将元素我们传入的数组引用空间中：
public <T> T[] toArray(T[] a) {
//获取列表元素大小
int size = size();
//......
//基于传入元素地址将元素复制到传入的数组地址空间中
System.arraycopy(this.a, 0, a, 0, size);
//......
return a;
}
数组转集合
使用工具类 Arrays.asList()
把数组转换成集合时，转成的集合是Arrays
工具类内部的ArrayList
：
Integer[] nums = new Integer[10];
for (int i = 0; i < 10; i++) {
nums[i] = i;
}
List<Integer> myList = Arrays.asList(nums);
需要注意的是AbstractList
不能使用其修改集合相关的方法，它是一个只读的容器， 它并没有重写 add/remove/clear
方法，所以会抛出 UnsupportedOperationException
异常，这一点我们查看AbstractList源码即可知晓这一点：
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
public E remove(int index) {
throw new UnsupportedOperationException();
}
详解Java集合工具类
常见集合排序操作API
Java内置了很多使用的集合操作的api，这里我们不妨列一下方法清单，读者可以基于注释熟悉一下这些API的使用：
void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面
集合排序
升序排序我们只需将列表传入sort方法，其底层排序的工作机制稍微会做介绍，这里我们先熟悉一下使用方法：
//随机生成长度为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);
System.out.println(list);
对应的输出结果如下：
[16, 84, 72, 18, 42, 93, 55, 28, 47, 14]
Collections 升序排序:
[14, 16, 18, 28, 42, 47, 55, 72, 84, 93]
sort方法同样是支持倒叙的排序的，对应的我们给出倒叙的比较器作为参数即可：
//随机生成长度为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);
对应的我们也给出输出结果:
[65, 84, 40, 27, 11, 24, 90, 54, 57, 6]
Collections 倒叙排序:
[90, 84, 65, 57, 54, 40, 27, 24, 11, 6]
列表翻转
reverse方法就是将我们元素内部按照倒叙反转一下，对应我们给出代码示例：
//随机生成长度为10的列表
List<Integer> list = RandomUtil.randomEleList(IntStream.range(0, 100).boxed().collect(Collectors.toList()), 10);
//打印排序前的列表
System.out.println(list);
//将列表元素翻转一圈并打印
System.out.println("Collections 翻转:");
Collections.reverse(list);
System.out.println(list);
可以看到，翻转后的数值按照列表倒叙进行排列了：
[17, 84, 53, 20, 70, 29, 15, 61, 63, 82]
Collections 翻转:
[82, 63, 61, 15, 29, 70, 20, 53, 84, 17]
列表随机排列
shuffle顾名思义即洗牌的意思，它会将列表内部元素顺序打乱
//随机生成长度为10的列表
List<Integer> list = RandomUtil.randomEleList(IntStream.range(0, 100).boxed().collect(Collectors.toList()), 10);
//打印排序前的列表
System.out.println(list);
//针对列表进行随机排序
System.out.println("Collections 随机排序:");
Collections.shuffle(list);
System.out.println(list);
输出结果:
[64, 24, 63, 94, 41, 76, 60, 69, 43, 27]
Collections 随机排序:
[63, 64, 27, 41, 60, 24, 94, 69, 43, 76]
列表整体移动
rotate算是比较少用的api，读者可以简单了解一下，这个方法会将列表中所有元素斗向前移动，对于列表末尾的元素会移动到列表首部，具体算法笔者会在后面的源码讲解进行分析，这里我们了解一下其使用效果：
//随机生成长度为10的列表
List<Integer> list = RandomUtil.randomEleList(IntStream.range(0, 100).boxed().collect(Collectors.toList()), 10);
//打印排序前的列表
System.out.println(list);
//将列表元素全部向前移动一步
System.out.println("Collections 所有元素向前移动一步:");
Collections.rotate(list, 1);
System.out.println(list);
输出结果：
[4, 80, 35, 52, 28, 79, 17, 61, 33, 11]
Collections 所有元素向前移动一步:
[11, 4, 80, 35, 52, 28, 79, 17, 61, 33]
两数交换
swap可以指定两数索引位置元素交换，如下代码，我们将索引0和索引1位置的元素进行交换：
//随机生成长度为10的列表
List<Integer> list = RandomUtil.randomEleList(IntStream.range(0, 100).boxed().collect(Collectors.toList()), 10);
//打印排序前的列表
System.out.println(list);
//打印两数交换后的列表
System.out.println("Collections 交换两个索引位置元素:");
Collections.swap(list, 0, 1);
System.out.println(list);
对应输出结果如下：
[24, 8, 91, 59, 34, 13, 78, 44, 84, 86]
Collections 交换两个索引位置元素:
[8, 24, 91, 59, 34, 13, 78, 44, 84, 86]
详解Java集合工具类算法底层实现
Collections.sort底层实现
查看sort
方法底层实现可以看出，除非开发显式配置归并排序才会调用legacyMergeSort
进行归并排序，否则一律使用TimSort
进行列表排序：
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
//如果配置指定要求才使用归并排序
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
//默认使用TimSort排序
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
而TimSort
的sort
方法就是排序核心的实现，TimSort
是自适应的、混合的、稳定的排序算法。是基于归并和二分插入排序优点结合的排序算法。复杂度最坏的情况下只有O(nlogn)
，最坏的情况下，空间复杂度为O(n/2)
。
这个方法在基数阈值的选取和排序的实现细节都做了机制都做了相对极致的优化，当列表元素小于32的情况下，TimSort
会直接通过二分插入排序直接完成排序操作。
二分插入排序法是插入排序法的升级版本，如下所示，我们都知道插入排序后左边的元素都是有序的，如果使用常规二分排序，那么最坏情况下插入时间是O(n)，所以我们基于左边有序这个特点改用二分插入的方式完成排序优化了这个问题。
当右边元素进行插入时，不断在左边进行二分运算定位到mid元素：
如果mid索引对应的元素小于插入元素，说明left索引元素值太小，需要向右移动找到下一个折中值。 如果mid索引元素值大于待插入的元素值，说明right坐标对应的元素值太大，需要让right坐标向左移动找到小一点的中间值。
通过这样的二分运算最终会找到一个小于或者等于待入元素坐标left作为插入索引并将元素插入，然后其余元素全部向后移动一位：
对此我们也给出TimSort
排序的前半部分实现，可以看到这段代码在进行二分排序前会先定位开头有序的最小区间initRunLen
，如下图所示，这个数组索引3之前的元素都是正向元素的，所以排序是从索引4开始：
对应的我们也给出这段代码的整体实现：
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
T[] work, int workBase, int workLen) {
int nRemaining = hi - lo; //计算出待排序的范围
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// 若小于32则直接调用`binarySort`
if (nRemaining < MIN_MERGE) {
//计算出lo 到 hi 范围找出有序的长度，若是降序则转为升序后返回
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
//使用二分插入法将hi以内未排序的元素插入到数组中
binarySort(a, lo, hi, lo + initRunLen, c);
//完成后直接返回
return;
}
//......
}
countRunAndMakeAscending
代码的实现，该方法本质上就是从头开始比对元素：
如果一开始runHi 元素大于其后一个元素，则正序方式先前遍历，runHi 不断前行，找到正向有序的最小区间。 如果一开始runHi 元素小于后一个元素，则按照倒叙方式进行编译，runHi 不断前行，找到逆序的最小区间。
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就进入循环，找到最小范围的降序子数组，循环结束后翻转为升序
if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
runHi++;
//循环结束后翻转为升序
reverseRange(a, lo, runHi);
} else {
//反之就寻找升序子数组
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
runHi++;
}
//runHi - lo即我们本次找到的有序子数组的长度
return runHi - lo;
}
然后我们再介绍binarySort
，如上文所说不断通过二分运算比对mid
和插入元素的值，然后进行插入，这里笔者特殊说明一下binarySort对于二分插入排序的优化细节，从代码中可以看到，当二分插入排序定位到合适的位置之后，会判断这个位置和插入元素之间的距离，如果两者距离小于2，则直接通过简单的元素交换：
反之，如果待插入的位置和插入元素索引位置大于2，则找到left及其前方元素批量先前移动一格，然后腾出一块空间将元素插入：
对应的我们给出binarySort
的代码实现细节：
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];
// 二分搜索范围设置为[lo,start)
int left = lo;
int right = start;
assert left <= right;
//通过二分法，找到合适插入位置
while (left < right) {
//通过位运算高效实现/2得到一个中间索引mid
int mid = (left + right) >>> 1;
//如果中间值大于插入元素，则right设置为mid，视图找到小一点的mid
if (c.compare(pivot, a[mid]) < 0)
right = mid;
else
//如果中间值小于插入元素，则left等于mid找到一个大一点的mid
left = mid + 1;
}
assert left == right;
int n = start - left; // 计算需要移动的步数
// 这里正是设计者的精华所在，可以看到如果只要移动1-2步，直接交换即可，若大于两步则直接指定数组范围进行批量拷贝
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;
}
}
当元素大于32的时候，TimSort
排序算法就会进行更近一步的设计，即针对当前数组生成无数个子单元进行二分插入排序，然后基于每个有序的子单元进行归并从而得到不断归并得到一个有序集合：
对应的我们给出TimSort
后续代码，整体逻辑与笔者说明一致，建议读者结合笔者说明和注释理解：
TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
int minRun = minRunLength(nRemaining);
do {
// 计算出最大的有序范围的索引
int runLen = countRunAndMakeAscending(a, lo, hi, c);
//若小于minRun，则说明进行排序的数组太小，需要指定一个范围排序一下
if (runLen < minRun) {
//nRemaining 为当前待排序的范围大小，minRun 为计算出来至少要排序的范围。若nRemaining 小于minRun ，则取nRemaining ，意味需要排序的范围就剩几个了直接用这几个值排个序就好了。反之则取minRun 进行二分插入排序
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen, c);
//完成后force的值就代表当前经历排序的元素个数，存到runLen中，作为后续合并的依据
runLen = force;
}
// 将lo到runLen的值存到栈中，后续归并会用到
ts.pushRun(lo, runLen);
//将当前排序的范围数组归并到已排序的数组中
ts.mergeCollapse();
// 起始位置加到runLen之后
lo += runLen;
//待排序的值减去已排序的长度
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
由于这篇文章主要描述Java集合工具类的使用，所以就不展开细讲了，感兴趣的朋友可以参考这两篇文章
世界上最快的排序算法——Timsort :https://www.cnblogs.com/sunshuyi/p/12680918.html
TimSort源码详解:https://www.cnblogs.com/hejiayang/p/14119741.html
rotate列表旋转算法的实现
rotate
旋转算法底层也有很多的巧妙设计，步入其源码可以看到：
如果是 RandomAccess
即具备随机访问特性的数组或者数组大小小于100
时使用rotate1
方法进行旋转反之说明该列表是不具备随机范文的链表则调用 rotate2
进行元素旋转
对应的我们给出代码的顶层实现：
public static void rotate(List<?> list, int distance) {
//如果是具备随机访问特性或者元素小于100则调用rotate1
if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
rotate1(list, distance);
else //反之调用rotate2
rotate2(list, distance);
}
我们先来说说rotate1
方法的实现，逻辑比较简单，计算出移动的步数之后通过list
的set
方法将元素设置到移动的位置上，通过set方法得到该位置上原有的元素，再将该元素移动到旋转后的的索引上：
对应的我们给出这段实现的源码，读者可结合说明了解核心流程：
private static <T> void rotate1(List<T> list, int distance) {
int size = list.size();
if (size == 0)
return;
//计算移动的步数
distance = distance % size;
//若为负数则加上数组大小 即可 (向左走n步)==(向右走数组大小+n步)
if (distance < 0)
distance += size;
if (distance == 0)
return;
//移动
for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
T displaced = list.get(cycleStart);
int i = cycleStart;
do {
i += distance;
//若大于数组大小则减去数组大小得出最终要走的步
if (i >= size)
i -= size;
//赋值并返回旧元素进行下一次do while旋转
displaced = list.set(i, displaced);
nMoved ++;
} while (i != cycleStart);
}
}
走到rotate2
这个函数则说明这个数组为不具备随机访问性的链表，为了保证性能，该方法会通过计算的方式得到计算出一个批量移动的区间，然后基于这两个整体进行批量的移动。
例如我们现在有一个链表，内部包含0-100一共101个元素，元素值为0~100
，刚刚好可以执行rotate2方法，假设我们希望全体向前移动一步，rotate2算法会通过-distance % size
得到100，即[0,100]
区间是只需先前移动的区间，而[101]是需要移动到列表前面的区间，rotate2的执行步骤为：
将区间1翻转，得到99~0。 将区间2翻转，得到100，此时列表排列为99~0、100。 最后将整个列表进行一次翻转，将100移动到列表最前面的同时，也将只需先前移动一格的区间放到100的后面：
对应的我们也给出rotate2的代码实现，整体思路和笔者说明的一致，就是通过-distance % size计算得到只需先前移动和要翻转到列表前面的两个区间，然后执行：
只需向前移动的区间1翻转。 移动到列表首部的区间2翻转。 整个列表翻转将区间2提前。
private static void rotate2(List<?> list, int distance) {
int size = list.size();
if (size == 0)
return;
//[0,mid]只需向前移动distance步，(mid,list.size()-1]移动到列表前面
int mid = -distance % size;
if (mid < 0)
mid += size;
if (mid == 0)
return;
//翻转[0,mid]
reverse(list.subList(0, mid));
//翻转(mid,list.size()-1]
reverse(list.subList(mid, size));
//整体移动，将(mid,list.size()-1]翻转到列表前方，同时保证[0,mid]有序
reverse(list);
}
详解jdk常见搜索比对函数
核心api概览
jdk也为我提供了很多使用的搜索和比较统计函数，对应的函数列表如下：
int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素
使用示例
System.out.println("Collections 二分搜索法(注意数组并需有序):");
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 统计频次:");
System.out.println(Collections.frequency(list, 5));
System.out.println("Collections 返回target子集在list中第一次出现的位置:");
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中第一次出现的位置
System.out.println("Collections replaceAll:");
Collections.replaceAll(list, 5, 6);
System.out.println(list);
详解洗牌算法
这里我们着重说明一下随机洗牌算法的实现，逻辑比较简单：
如果列表具备随机访问或者size小于100，可以直接从size开始倒叙调用swap进行随机元素交换。 反之说明当前列表是大于100的链表，首先将这些元素存到一个具备随机访问的数组中，然后基于这个数组进行随机swap交换，再存入链表中，所以性能表现会差一些。
对应的源码如下：
public static void shuffle(List<?> list, Random rnd) {
int size = list.size();
//若小于SHUFFLE_THRESHOLD 或者是RandomAccess类则从高位索引与随机一个低位索引交换值完成洗牌
if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
for (int i=size; i>1; i--)
//将i-1位置元素和随机一个位置进行交换
swap(list, i-1, rnd.nextInt(i));
} else {
//反之转成数组，再遍历数组的值存到list中
Object arr[] = list.toArray();
for (int i=size; i>1; i--)
////将i-1位置元素和随机一个位置进行交换
swap(arr, i-1, rnd.nextInt(i));
//然后设置到链表中
ListIterator it = list.listIterator();
for (int i=0; i<arr.length; i++) {
it.next();
it.set(arr[i]);
}
}
}
同步控制
同步控制常见函数
注意，非必要不要使用这种API
，效率极低
synchronizedCollection(Collection<T> c) //返回指定 collection 支持的同步（线程安全的）collection。
synchronizedList(List<T> list)//返回指定列表支持的同步（线程安全的）List。
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步（线程安全的）Map。
synchronizedSet(Set<T> s) //返回指定 set 支持的同步（线程安全的）set。
使用示例
可以看到笔者在下面贴出使用Collections.synchronizedList
包装后的list
的add
方法，锁的粒度很大，在多线程操作情况下，性能非常差。
我们就以synchronizedList
为例查看其add
方法，可以看到其实现线程安全的方式很简单，直接在工作代码上synchronized
，在高并发情况下，很可能造成大量线程阻塞
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
示例代码如下，我们分别开两个线程，往数组中添加1000个数组，可以看到笔者注释代码中用了普通list，以及通过Collections.synchronizedList
后的list，感兴趣的读者可以基于下面代码测试是否线程安全
@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());
}
输出结果为2000，说明该方法确实实现了线程安全
2000
小结
我是 sharkchili ，CSDN Java 领域博客专家，mini-redis的作者，我想写一些有意思的东西，希望对你有帮助，如果你想实时收到我写的硬核的文章也欢迎你关注我的公众号： 写代码的SharkChili 。
同时也非常欢迎你star我的开源项目mini-redis:https://github.com/shark-ctrl/mini-redis
因为近期收到很多读者的私信，所以也专门创建了一个交流群，感兴趣的读者可以通过上方的公众号获取笔者的联系方式完成好友添加，点击备注 “加群” 即可和笔者和笔者的朋友们进行深入交流。
参考
Java集合使用注意事项总结：https://javaguide.cn/java/collection/java-collection-precautions-for-use.html#集合判空
面经手册 · 第10篇《扫盲java.util.Collections工具包，学习排序、二分、洗牌、旋转算法》:https://bugstack.cn/md/java/interview/2020-09-10-面经手册 · 第10篇《扫盲java.util.Collections工具包，学习排序、二分、洗牌、旋转算法》.html#_3-collections-shuffle-洗牌算法
