数组和集合。

- 日理万妓 2024-02-18 20:36 15阅读 0赞

*  性能考虑，数组是首选

基本类型是在栈内存中操作的，而对象则是在堆内存中操作的，栈内存的特点是速度快，容量小，堆内存的特点是速度慢，容量大（从性能上来讲，基本类型的处理占优势）。

对基本类型进行求和计算时，数组的效率是集合的10倍。

注意：性能要求较高的场景中使用数组替代集合。

*  若有必要，使用变长数组

Arrays数组工具类的copyOf方法，产生了一个newLen长度的新数组，并把原有的值拷贝了进去，之后就可以对超长的元素进行赋值了（依据类型的不同分别赋值为0、false或null）。

在实际开发中，如果确实需要变长的数据集，数组也是在考虑范围之内的，不能因固定长度而将其否定。

*  警惕数组的浅拷贝

通过copyOf方法产生的数组是一个浅拷贝，这与序列化的浅拷贝完全相同：基本类型是直接拷贝值，其他都是拷贝引用地址。需要说明的是，数组的clone方法也是与此相同的，同样是浅拷贝，而且集合的clone方法也都是浅拷贝。

*  在明确的场景下，为集合指定初始容量

ArrayList是一个大小可变的数组，但他在底层使用的是数组存储（也就是elementData变量）。而且数组是定长的，要实现动态长度必然要进行长度的扩展，ensureCapacity方法提供了此功能。

ArrayList的扩容原则：一次扩容太大（比如扩容2.5倍），占用的内存也就越大，浪费的内存也就越多（1.5倍扩容，最多浪费33%的数组空间，而2.5倍则最多可能浪费60%的内存）；而一次扩容太小（比如每次扩容1.1倍），则需要多次对数组重新分配内存，性能消耗严重。经过测试验证，扩容1.5倍即满足了性能要求，也减少了内存消耗。

ArrayList的默认长度：elementData的默认长度是多少呢？答案是10，如果我们使用默认方式声明ArrayList，如new ArrayList()，则elementData的初始长度就是10.

如果我们已经知道一个ArrayList的可能长度，然后对ArrayList设置一个初始容量则可以显著提高系统性能（在大数据量下，是否指定容量会使性能相差5倍以上）。

Vector与ArrayList不同的地方是他提供了递增步长（capacityIncrement变量），其值代表的是每次数组拓长时要增加的长度，不设置此值则是容量翻倍（默认是不设置递增步长的，可以通过构造函数来设置递增步长）。其他集合类的扩容方式与此相似，如HashMap是按照倍数增加的，Stack继承自Vector，所采用的是与其相同的扩容原则等。

*  多种最值算法，适时选择

为什么要先使用clone拷贝再排序呢？那是因为数组也是一个对象，不拷贝不就改变了原有数组元素的顺序吗？除非数组元素的顺序无关紧要。

在实际应用中求最值，包括最大值、最小值、第二大值、倒数第二小值等，使用集合是最简单的方式，当然若从性能方面来考虑，数组是最好的选择。

注意：最值计算时使用集合最简单，使用数组性能最优。

*  避开基本类型数组转换列表陷阱

Arrays.asList方法输入的是一个泛型变长参数，我们知道基本类型是不能泛型化的，也就是说8个基本类型不能作为泛型参数，要想作为泛型参数就必须使用其所对应的包装类型。

在Java中任何一个数组的类都是“\[I”，究其原因就是Java并没有定义数组这一个类，他是在编译器编译的时候生成的，是一个特殊的类，在JDK的帮助中也没有任何数组的信息。

注意：原始类型数组不能作为asList的输入参数，否则会引起程序逻辑混乱。

*  asList方法产生的List对象不可改变（只读）

Arrays的静态内部类ArrayList，他仅仅实现了5个方法：

1、size：元素数量。

2、toArray：转化为数组，实现了数组的浅拷贝。

3、get：获得指定元素。

4、set：重置某一元素值。

5、contains：是否包含元素。

*  不同的列表选择不同的遍历方法

ArrayList数组实现了RandomAccess接口（随机存取接口），这也就标志着ArrayList是一个可以随机存取的列表。在Java中，RandomAccess和Cloneable、Serializable一样，都是标志性接口，不需要任何实现，只是用来表明其实现类具有某种特质的，实现了Cloneable表明可以被拷贝，实现了Serializable接口表明被序列化了，实现RandomAccess则表明这个类可以随机存去，对我们的ArrayList来说也就标志着其数据元素之间没有关联，即两个位置相邻的元素之间没有相互依赖和索引关系，可以随机访问和存储。

*  频繁插入和删除时使用LinkedList

*  列表相等只需关心元素数据

列表只是一个容器，只要是同一种类型的容器（如List），不用关心容器的细节差别（如ArrayList与LinkedList），只要确定所有的元素数据相等，那这两个列表就是相等的。

其他的集合类型，如Set、Map等与此相同，也是只关心集合元素，不用考虑集合类型。

注意：判断集合是否相等时只须关注元素是否相等即可。

*  子列表只是原列表的一个视图

List的subList方法是由AbstractList实现的，他会根据是不是可以随机存取来提供不同的SubList实现方式，不过，随机存储的使用频率比较高，而且RandomAccessSubList也是SubList子类，所以所有的操作都是由SubList类实现的（除了自身的SubList方法外）。

List的subList方法的实现原理了：他返回的SubList类也是AbstractList的子类，其所有的方法如get、set、add、remove等都是在原始列表上的操作，他自身并没有生成一个数组或是链表，也就是子列表只是原列表的一个视图（View），所有的修改动作都反映在了原列表上。

*  推荐使用subList处理局部列表

List的subList方法的具体实现方式，所有的操作都是在原始列表上进行的那我们就用subList先取出一个子列表，然后情空。因为subList返回的List是原始列表的一个视图，删除这个视图的所有元素，最终就会反映到原始字符串上，那么一行代码即解决问题了。

*  生成子列表后不要再操作原列表

List的subList取出的列表是原列表的一个视图，原数据集修改了，但是subList取出的子列表不会重新生成一个新列表（这点与数据集视图是不相同的），后面在对子列表继续操作时，就会检测到修改计数器与预期的不相同，于是就抛出了并发修改异常。

对于子列表操作，因为视图是动态生成的，生成子列表后再操作原列表，必然会导致“视图”的不稳定，最有效的办法就是通过Collections.unmodifiableList方法设置列表为只读状态。防御式编程就是教我们如此做的。

注意：subList生成子列表后，保持原列表的只读状态。

*  使用Comparator进行排序

在Java中，要给数据排序，有两种实现方式，一种是实现Comparable接口，一种是实现Comparator接口。

在JDK中，对Collections.sort方法的解释是按照自然顺序进行升序排列，这种说法其实不太准确的，sort方法的排序方式并不是一成不变的升序，也可能是倒序，这依赖于compareTo的返回值。

在Java中，为什么要有两个排序接口呢？

实现了Comparable接口的类表明自身是可以比较的，有了比较才能排序；而Comparator接口是一个工具类接口，他的名字（比较器）也已经表明他的总用：用作比较，他与原有类的逻辑没有关系，只是实现两个类的比较逻辑，从这方面来说，一个类可以有很多的比较器，只要有业务需求就可以产生比较器，有比较器就可以产生N多种排序，而Comparable接口的排序只能说是实现类的默认排序算法，一个类稳定、成熟后其comparteTo方法基本不会改变，也就是说一个类只能有一个固定的、由compareTo方法提供的默认排序算法。

注意：Comparable接口可以作为实现类的默认排序法，Comparator接口则是一个类的扩展排序工具。

*  不推荐使用binarySearch对列表进行检索

对一个列表进行检索时，我们使用的最多的是indexOf方法，他简单、好用，而且也不会出错，虽然他只能检索到第一个符合条件的值，但是我们可以生成子列表后再检索，这样也就可以查找出所有符合调价你的值了。

二分法查询的一个首要前提是：数据集已经实现升序排列，否则二分法查找的值是不准确的。拷贝一个数组，然后再排序，再使用binarySearch查找指定值，也可以解决该问题。

使用binarySearch的二分法查找比indexOf的遍历算法性能上高很多，特别是在大数据集而且目标值又接近尾部时，binarySearch方法与indexOf相比，性能上会提升几十倍，因此在性能的角度考虑时可以选择binarySearch。

*  集合中的元素必须做到compareTo和equals同步

1、indexOf依赖equals方法查找，binarySearch则依赖compareTo方法查找。

2、equals是判断元素是否相等，compareTo是判断元素在排序中的位置是否相同。

注意：实现了compareTo方法，就应该覆写equals方法，确保两者同步。

*  集合运算时使用更优雅的方式

并集：也叫做合集，把这两个集合加起来即可。list.addAll()。

交集：计算两个集合的共有元素，也就是你有我也有的元素集合，list.retainAll()。

差集：由所有属于A但不属于B的元素组成的集合，list.removeAll()。

无重复的并集：list.removeAll()，然后list.addAll()。

*  使用shuffle打乱列表

Collections的swap方法，该方法会交换两个位置的元素值。

Collections的shuffle方法，该方法打乱一个列表的顺序，不用我们费尽心思的遍历、替换元素了。

shuffle方法应用的地方：

1、可以用在程序的“伪装”上：比如标签云，或者是游戏中的打怪、修行、群殴时宝物的分配策略。

2、可以用在抽奖程序中：比如年会的抽奖程序，先使用shuffle把员工排序打乱，每个员工的中将几率就是相等的了，然后就可以抽取第一名，第二名。

3、可以用在安全传输方面：比如发送端发送一组数据，先随机打乱顺序，然后加密发送，接收端解密，然后自行排序，即可实现即使是相同的数据源，也会产生不同密文的效果，加强了数据的安全性。

*  减少HashMap中元素的数量

HashMap在底层也是以数组方式保存元素的，其中每一个键值对就是一个元素，也就是说HashMap把键值对封装成了一个Entry对象，然后再把Entry放到了数组中。

HashMap底层的数组变量名叫table，他是Entry类型的数组，保存的是一个一个的键值对。

HashMap的扩容机制：在插入键值对时，会做长度校验，如果大于或等于阀值（threshold变量），则数组长度增大一倍。不过，默认的阀值是多大的呢？默认实当前长度与加载因子的乘机。默认的加载因子（loadFactor变量）是0.75。

*  集合中的哈希码不要重复

遍历最快的还要数以Hash开头的集合（如HashMap、HashSet等类）查找。

在没有哈希冲突的情况下，HashMap的查找则是依赖hashCode定位的，因为是直接定位，那效率当然高了；如果哈希码相同，他的查找效率就与ArrayList没什么两样了，遍历对比，性能会大打折扣。

*  多线程使用Vector或HashTable

Vector是ArrayList的多线程版本，HashTable是HashMap的多线程版本。

基本上所有的集合类都有一个叫做快速失败（Fail-Fast）的校验机制，当一个集合在被多个线程修改并访问时，就可能会出现ConcurrentModificationException异常，这是为了确保集合方法一致而设置的保护措施，他的实现原理就是我们经常提到的modeCount修改计数器；如果在读列表时，modCount发生变化（也就是有其他线程修改）则会抛出ConcurrentModificationException异常。这与线程同步是两码事，线程同步是为了保护几何中的数据不被脏读、脏写而设置的。

在系统开发中我们一再说明，除非必要，否则不要使用synchronized，这时从性能的角度考虑的，但是一旦涉及多线程时（注意这里说的是真正的多线程，不是并发修改的时间，比如一个线程增加，一个线程删除，这不属于多线程的范畴），Vector会是最佳选择，当然自己在程序中加synchronized也是可行的办法。

*  非稳定排序推荐使用List

Set与List的最大区别就是Set中的元素不可以重复（这个重复指的equals方法的返回值相等）。

TreeSet，该类实现了类默认排序为升序的Set集合，如果插入一个元素，默认会按照升序排列（当然是根据Comparable接口的compareTo的返回值确定排序位置了）。

SortedSet接口（TreeSet实现了该接口）只是定义了在给集合加入元素时将其进行排序，并不能保证元素修改后的排序结果，因此TreeSet适用于不变量的集合数据排序，比如String、Integer等类型，但不适用于可变量的排序，特别是不确定何时元素会发生变化的数据集合。

解决重排序问题的两种方式：

1、Set集合重排序

2、彻底重构掉TreeSet，使用List解决问题

对于不变量的排序，例如直接量（也就是8个基本类型）、String类型等，推荐使用TreeSet，而对于可变量，例如我们自己写的类，可能会在逻辑处理中改变其排序关键值的，则建议使用List自行排序。

注意：SortedSet中的元素被修改后可能会影响其排序位置。