本帖最后由 三木猿 于 2020-9-18 11:17 编辑
每日名言
学者须先立志。今日所以悠悠者，只是把学问不曾做一件事看，遇事则且胡乱恁地打过了，此只是志不立。
——朱熹
工作中经常会用到一些工具类，本次我们对这些工具类进行解析讲解。
工具类的特征：
1.构造器必须是私有的，私有后就不能被new出来，因为使用时都是直接调用的，所以不开放构造器
2.工具类的方法必须是static或final修饰的，这样可以保证方法不可变，使用时也可以直接使用
1，Arrays工具类
Arrays 主要对数组提供了一些高效的操作，比如说排序、查找、填充、拷贝、相等判断等等。
| 方法声明 | 功能描述 | | public static List asList(T… a) | 返回由指定数组支持的固定大小的列表 | | public static String toString(int[] a) | 返回指定数组的内容的字符串表示形式 | | public static void sort(int[] a) | 按照数字顺序排列指定的数组 | | public static void fill(Object[] a, Object val) | 将指定的对象引用分配给指定的对象数组的每个元素 | | public static int binarySearch(Object[] a, Object key) | 使用二叉搜索算法搜索指定对象的指定数组 | | public static int[] copyOfRange(int[] original, int from, int to) | 将指定数组的指定范围复制到新数组中 |
1.1排序（Arrays.sort）
Arrays.sort 方法主要用于排序，入参支持 int、long、double 等各种基本类型的数组，也支持自定义类的数组，这里写一个自定义类的小demo
[Java] 纯文本查看 复制代码 public class test { // 自定义类
class SortDTO {
private Integer sortTarget;
public SortDTO(Integer sortTarget) {
this.sortTarget = sortTarget;
}
public Integer getSortTarget() {
return sortTarget;
}
public void setSortTarget(Integer sortTarget) {
this.sortTarget = sortTarget;
}
}
@Test
public void testSort() {
List<SortDTO> list = ImmutableList.of(
new SortDTO(300),
new SortDTO(50),
new SortDTO(200),
new SortDTO(220)
);
// 我们先把数组的大小初始化成 list 的大小，保证能够正确执行 toArray
SortDTO[] array = new SortDTO[list.size()];
list.toArray(array);
System.out.println("排序之前：" + JSON.toJSONString(array));
Arrays.sort(array, Comparator.comparing(SortDTO::getSortTarget));
System.out.println("排序之后：" + JSON.toJSONString(array));
}
}
这是sort默认调用的核心源码
[Java] 纯文本查看 复制代码 static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
assert a != null && lo >= 0 && lo <= hi && hi <= a.length;
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // array的大小为0或者1就不用排了
// 当数组大小小于MIN_MERGE(32)的时候，就用一个"mini-TimSort"的方法排序，jdk1.7新加
if (nRemaining < MIN_MERGE) {
//这个方法比较有意思，其实就是将我们最长的递减序列，找出来，然后倒过来
int initRunLen = countRunAndMakeAscending(a, lo, hi);
//长度小于32的时候，是使用binarySort的
binarySort(a, lo, hi, lo + initRunLen);
return;
}
//先扫描一次array，找到已经排好的序列，然后再用刚才的mini-TimSort，然后合并，这就是TimSort的核心思想
ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen);
runLen = force;
}
// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);
ts.mergeCollapse();
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}
1.2.二分查找法
Arrays.binarySearch 方法主要用于快速从数组中查找出对应的值。其支持的入参类型非常多，如 byte、int、long 各种类型的数组。
返回参数是查找到的对应数组下标的值，如果查询不到，则返回负数。我们来写个demo
[Java] 纯文本查看 复制代码 public class test {
// 自定义类
class SortDTO {
private Integer sortTarget;
public SortDTO(Integer sortTarget) {
this.sortTarget = sortTarget;
}
public Integer getSortTarget() {
return sortTarget;
}
public void setSortTarget(Integer sortTarget) {
this.sortTarget = sortTarget;
}
}
@Test
public void testSort() {
List<SortDTO> list = ImmutableList.of(
new SortDTO(300),
new SortDTO(50),
new SortDTO(200),
new SortDTO(220)
);
SortDTO[] array = new SortDTO[list.size()];
list.toArray(array);
System.out.println("搜索之前："+JSON.toJSONString(array));
Arrays.sort(array, Comparator.comparing(SortDTO::getSortTarget));
System.out.println("先排序，结果为："+ JSON.toJSONString(array));
int index = Arrays.binarySearch(array, new SortDTO(200),
Comparator.comparing(SortDTO::getSortTarget));
if(index<0){
throw new RuntimeException("没有找到 200");
}
System.out.println("搜索结果："+ JSON.toJSONString(array[index]));
}
}
从上述代码中我们需要注意两点：
1. 如果被搜索的数组是无序的，一定要先排序，否则二分搜索很有可能搜索不到，我们 demo里面也先对数组进行了排序；
2. 搜索方法返回的是数组的下标值。如果搜索不到，返回的下标值就会是负数，这时我们需要判断一下正负。如果是负数，还从数组中获取数据的话，
会报数组越界的错误。demo 中对这种情况进行了判断，如果是负数，会提前抛出明确的异常
我们再来看看二分查找法的源码
[Java] 纯文本查看 复制代码 // a：我们要搜索的数组，fromIndex：从那里开始搜索，默认是0； toIndex：搜索到何时停止，默认
// key：我们需要搜索的值 c：外部比较器
private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
T key, Comparator<? super T> c) {
// 如果比较器 c 是空的，直接使用 key 的 Comparable.compareTo 方法进行排序
// 假设 key 类型是 String 类型，String 默认实现了 Comparable 接口，就可以直接使用 compar
if (c == null) {
// 这是另外一个方法，使用内部排序器进行比较的方法
return binarySearch0(a, fromIndex, toIndex, key);
}
int low = fromIndex;
int high = toIndex - 1;
// 开始位置小于结束位置，就会一直循环搜索
while (low <= high) {
// 假设 low =0，high =10，那么 mid 就是 5，所以说二分的意思主要在这里，每次都是计算索
int mid = (low + high) >>> 1;
T midVal = a[mid];
// 比较数组中间值和给定的值的大小关系
int cmp = c.compare(midVal, 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.
}
二分的主要意思是每次查找之前，都找到中间值，然后拿我们要比较的值和中间值比较，根据结果修改比较的上限或者下限，通过循环最终找到相等的位置索引
1.3数组拷贝
数组拷贝我们经常遇到，有时需要拷贝整个数组，有时需要拷贝部分，比如 ArrayList 在add（扩容） 或 remove（删除元素不是最后一个） 操作时，会进行一些拷贝。拷贝整个数组
我们可以使用 copyOf 方法，拷贝部分我们可以使用 copyOfRange 方法，以 copyOfRange为例，看下底层源码的实现：
[Java] 纯文本查看 复制代码 // original 原始数组数据
// from 拷贝起点
// to 拷贝终点
public static char[] copyOfRange(char[] original, int from, int to) {
// 需要拷贝的长度
int newLength = to - from;
if (newLength < 0)
throw new IllegalArgumentException(from + " > " + to);
// 初始化新数组
char[] copy = new char[newLength];
// 调用 native 方法进行拷贝，参数的意思分别是：
// 被拷贝的数组、从数组那里开始、目标数组、从目的数组那里开始拷贝、拷贝的长度
System.arraycopy(original, from, copy, 0,
Math.min(original.length - from, newLength));
return copy;
}
从源码中，我们发现，Arrays 的拷贝方法，实际上底层调用的是 System.arraycopy 这个native 方法，如果你自己对底层拷贝方法比较熟悉的话，也可以直接使用。
参考链接：https://blog.csdn.net/xsj_blog/article/details/78824045
https://www.cnblogs.com/williamjie/p/9103469.html | 
发表于 2020-9-18 10:59
学习学习学习
