讀書，收獲，分享
建議后面的五角星僅代表筆者個人需要注意的程度。
Talk is cheap.Show me the code
建議60：性能考慮，數(shù)組是首選★★★☆☆
在Java中由于數(shù)組沒有List、Set、Map這些集合類用起來方便，于是數(shù)組在實際的系統(tǒng)開發(fā)中用得越來越少了，我們通常只有在閱讀一些開源項目時才會看到它們的身影。但是在基本類型處理方面，數(shù)組還是占優(yōu)勢的，而且集合類的底層也都是通過數(shù)組實現(xiàn)的。
如例：
//對數(shù)組求和
public static int sum1(int[] arr) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
//對列表求和
public static int sum2(List<Integer> list) {
int sum = 0;
for (int i = 0; i < list.size(); i++) {
//此處做了自動拆箱操作
sum += list.get(i);
}
return sum;
}
//所以，效率：sum1() > sum2();
//在實際測試中發(fā)現(xiàn)：對基本類型進行求和計算時，數(shù)組的效率是集合的10倍。
基本類型是在棧內(nèi)存中操作的，而對象則是在堆內(nèi)存中操作的，棧內(nèi)存的特點是速度快，容量小，堆內(nèi)存的特點是速度慢，容量大（從性能上來講，基本類型的處理占優(yōu)勢）。
注意：性能要求較高的場景中使用數(shù)組替代集合。
建議61：若有必要，使用變長數(shù)組★★☆☆☆
Java中的數(shù)組是定長的，經(jīng)過初始化聲明就不可改變長度，這在實際使用中非常不方便。但是可以通過對數(shù)組擴容“婉轉”地解決該問題，代碼如下：
public static <T> T[] expandCapacity(T[] datas, int newLen) {
newLen = newLen < 0 ? 0 : newLen;
//生成一個新數(shù)組，并拷貝原值
return Arrays.copyOf(datas, newLen);
}
注意：在實際開發(fā)中，如果確實需要變長的數(shù)據(jù)集，數(shù)組也是在考慮范圍之內(nèi)的，不能因固定長度而將其否定。
建議62：警惕數(shù)組的淺拷貝★★★☆☆
通過 Arrays.copyOf()方法產(chǎn)生的數(shù)組是一個淺拷貝，這與序列化的淺拷貝完全相同：基本類型是直接拷貝值，其他都是拷貝引用地址。數(shù)組的clone()方法也是與此相同的，同樣是淺拷貝，而且集合的clone()方法也都是淺拷貝。
注意：雖然很多時候淺拷貝可以解決業(yè)務問題，但更多時候會留下隱患，需要我們提防又提防
建議63：在明確的場景下，為集合指定初始容量★★★☆☆
通過閱讀ArrayList的 add()方法來看，它是怎么自動管理長度的，代碼如下：
public boolean add(E e) {
//擴展長度
ensureCapacity(size + 1);
//追加元素
elementData[size++] = e;
return true;
}
public void ensureCapacity(int minCapacity) {
//修改計數(shù)器
modCount++;
//上次（原始）定義的數(shù)組長度
int oldCapacity = elementData.length;
//當前需要的長度超過了數(shù)組長度
if (minCapacity > oldCapacity) {
Object[] oldData = elementData;
//計算新數(shù)組長度
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
//數(shù)組拷貝,形成新數(shù)組
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
/**
* 注意看新數(shù)組的長度計算方法，并不是增加一個元素，elementData的長度就加1，
* 而是在達到elementData長度的臨界點時，才將elementData擴容1.5倍，
* 這樣實現(xiàn)有什么好處呢？好處是避免了多次調用copyOf方法的性能開銷，
* 否則每加一個元素都要擴容一次，那性能豈不是非常糟糕？！
* 這里為什么是1.5倍，而不是2.5倍、3.5倍？
* 原因是一次擴容太大（比如擴容2.5倍），占用的內(nèi)存也就越大，浪費的內(nèi)存也就越多
* （1.5倍擴容，最多浪費33%的數(shù)組空間，而2.5倍則最多可能浪費60%的內(nèi)存）；
* 而一次擴容太?。ū热缑看螖U容1.1倍），則需要多次對數(shù)組重新分配內(nèi)存，性能消耗嚴重。
* 經(jīng)過測試驗證，擴容1.5倍即滿足了性能要求，也減少了內(nèi)存消耗。
*/
elementData的初始容量為10，代碼如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity.
* 默認初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
// ***省略***
}
從ArrayList的擴容機制可以看出，如果不設置初始容量，系統(tǒng)就按照1.5倍的規(guī)則擴容，每次擴容都是一次數(shù)組的拷貝，如果數(shù)據(jù)量很大，這樣的拷貝會非常耗費資源，而且效率非常低下。如果我們已經(jīng)知道一個ArrayList的可能長度，然后對ArrayList設置一個初始容量則可以顯著提高系統(tǒng)性能（在大數(shù)據(jù)量下，是否指定容量會使性能相差5倍以上）。
其他類型集合的擴容處理方式與ArrayList相似，只是數(shù)組的長度計算方式不同而已。
注意：非常有必要在集合初始化時聲明容量。
建議64：多種最值算法，適時選擇★★☆☆☆
對一批數(shù)據(jù)進行排序，然后找出其中的最大值或最小值，有多種實現(xiàn)方式，示例如下：
//（1）自行實現(xiàn)，快速查找最大值
public static int max1(int[] data) {
int max = data[0];
for (int i : data) {
max = max > i ? max : i;
}
return max;
}
//（2）先排序，后取值
public static int max2(int[] data) {
//先排序，clone()是為了不改變數(shù)組原有順序
Arrays.sort(data.clone());
return data[data.length - 1];
}
//增加復雜度，查找僅次于最大值的元素的實現(xiàn)
public static int getSecond(Integer[] data) {
//先轉為列表
List<Integer> dataList = Arrays.asList(data);
//在轉為TreeSet,去重并升序排列
TreeSet<Integer> ts = new TreeSet<Integer>(dataList);
return ts.lower(ts.last());
}
首先max1()的效率肯定是高于max2()，但在實際測試中我們發(fā)現(xiàn)，如果數(shù)組數(shù)量少于1萬，兩者基本上沒有差別，在同一個毫秒級別里，此時就可以不用自己寫算法了，直接使用數(shù)組先排序后取值的方式。
至于getSecond()的要求稍微復雜些，使用集合是最簡單的方式，若從性能方面來考慮，數(shù)組是最好的選擇。
注意：最值計算時使用集合最簡單，使用數(shù)組性能最優(yōu)，需適時選擇。
建議65：避開基本類型數(shù)組轉換列表陷阱★☆☆☆☆
示例如下：
public static void main(String[] args) {
int[] data = {1, 2, 3, 4, 5};
List list = Arrays.asList(data);
System.out.println(list.size());
//運行結果1
}
//asList源代碼
public static <T> List<T> asList(T... a) {
return new Arrays.ArrayList<>(a);
}
/**
* asList方法輸入的是一個泛型變長參數(shù)，但基本類型是不能泛型化的
* 于是在main()中把data（一個int類型的數(shù)組）作為了T的類型。
* 所以，在上述例子中，用基本類型的包裝類即可。
* */
注意：基本類型數(shù)組不能作為
asList()的輸入?yún)?shù)，否則會引起程序邏輯混亂。
建議66：asList方法產(chǎn)生的List對象不可更改★☆☆☆☆
asList()源碼：
public static <T> List<T> asList(T... a) {
//此ArrayList非java.util.ArrayList，而是Arrays工具類的一個內(nèi)置類
return new ArrayList<>(a);
}
//內(nèi)置類
private static class ArrayList<E> extends AbstractList<E> implements
RandomAccess, java.io.Serializable {
//存儲列表元素的數(shù)組
private final E[] a;
//唯一的構造函數(shù)
ArrayList(E[] array) {
if (array == null)
throw new NullPointerException();
a = array;
}
//***省略余下源碼***
/**
* 1. ArrayList是一個靜態(tài)私有內(nèi)部類，除了Arrays能訪問外，其他類都不能訪問
* 2. List.add和List.remove方法它都沒有實現(xiàn), 于是數(shù)組是多長，轉換成的列表也就是多長（不可變性）
*/
}
建議67：不同的列表選擇不同的遍歷方法★★☆☆☆
以ArrayList和LinkedList為例：
//測試得出，使用最優(yōu)的遍歷方式，性能提升了60%以上
public static int avg(List<Integer> list) {
int sum = 0;
if (list instanceof RandomAccess) {//ArrayList數(shù)組實現(xiàn)了RandomAccess接口（隨機存取接口）
//可以隨機存取，則使用下標遍歷
for (int i = 0; i < list.size(); i++) {
sum += list.get(i);
}
} else {
//有序存取，使用foreach方式
for (int i : list) {
sum += i;
}
}
return sum / list.size();
}
RandomAccess接口（隨機存取接口） : 實現(xiàn)了RandomAccess則表明這個類可以隨機存取，對ArrayList來說也就標志著其數(shù)據(jù)元素之間沒有關聯(lián)，即兩個位置相鄰的元素之間沒有相互依賴和索引關系，可以隨機訪問和存儲。
Java中的foreach語法是iterator（迭代器）的變形用法，也就是說對于ArrayList，需要先創(chuàng)建一個迭代器容器，然后屏蔽內(nèi)部遍歷細節(jié)，對外提供hasNext、next等方法。問題是ArrayList實現(xiàn)了RandomAccess接口，已表明元素之間本來沒有關系，可是，為了使用迭代器就需要強制建立一種互相“知曉”的關系，比如上一個元素可以判斷是否有下一個元素，以及下一個元素是什么等關系，這也就是通過foreach遍歷耗時的原因。
LinkedList類不是隨機存取的，而是有序存取的，它實現(xiàn)了雙向鏈表，每個數(shù)據(jù)結點中都有三個數(shù)據(jù)項：前節(jié)點的引用（Previous Node）、本節(jié)點元素（Node Element）、后繼節(jié)點的引用（Next Node），也就是說在LinkedList中的兩個元素本來就是有關聯(lián)的，我知道你的存在，你也知道我的存在，使用foreach也就是迭代器方式效率更高。
注意：列表遍歷不是那么簡單的，其中很有“學問”，適時選擇最優(yōu)的遍歷方式，不要固化為一種
建議68：頻繁插入和刪除時使用LinkedList★☆☆☆☆
下面以ArrayList和LinkedList的元素插入算法為例：
ArrayList的插入（add方法）算法：
public void add(int index, E element) {
/*省略校驗代碼*/
//若需要擴容，則增大底層數(shù)組的長度
ensureCapactiy(size + 1);
//給index下標之后的元素（包括當前的元素）的下標加1，空出index位置
System.arraycopy(elementData, index, elementData, index + 1, size - index);
//賦值index位置元素
elementData[index] = element;
//列表長度+1
size++;
}
/**
* 注意看arraycopy方法，只要是插入一個元素，其后的元素就會向后移動一位，
* 雖然arraycopy是一個本地方法，效率非常高，但頻繁的插入，每次后面的元素都要拷貝一遍，效率就變低了，
* 特別是在頭位置插入元素時。
* */
LinkedList的插入（add方法）算法：
public void add(int index, E element) {
///調用了私有addBefore方法
addBefore(element, (index == size ? header : entry(index)));
}
//該方法實現(xiàn)了在一個元素之前插于元素的算法
private Entry<E> addBefore(E e, Entry<E> entry) {
//組裝一個新節(jié)點，previous指向節(jié)點的前節(jié)點，next指向原節(jié)點
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
//前節(jié)點next指向自己
newEntry.previous.next = newEntry;
//后節(jié)點的previous指向自己
newEntry.next.previous = newEntry;
//長度+1
size++;
//修改計數(shù)器+1;
modCount++;
return newEntry;
}
/**
* 這是一個典型的雙向鏈表插入算法，把自己插入到鏈表，
* 然后再把前節(jié)點的next和后節(jié)點的previous指向自己。
* 這樣一個插入元素（也就是Entry對象）的過程中，沒有任何元素會有拷貝過程，只是引用地址改變了，
* 那效率當然就高了。
* */
經(jīng)過實際測試得知，LinkedList的插入效率比ArrayList快50倍以上
LinkedList刪除和插入效率高，ArrayList修改元素效率高，具體源碼，不再粘貼。
得出，如果有大量的寫操作（更多的是插入和刪除動作），推薦使用LinkedList，不過何為少量，何為大量呢？畢竟80%的性能是消耗在20%的代碼上的，所以還是要適時選擇，比如一個實時交易的系統(tǒng)，即使寫作操再少，使用LinkedList也比ArrayList合適，因為此類系統(tǒng)是爭分奪秒的，多N個毫秒可能就會造成交易數(shù)據(jù)不準確；而對于一個批量系統(tǒng)來說，幾十毫秒、幾百毫秒，甚至是幾千毫秒的差別意義都不大，這時是使用LinkedList還是ArrayList就看個人愛好了，當然，如果系統(tǒng)已經(jīng)處于性能臨界點了那就必須使用LinkedList。
建議69：列表相等只需關心元素數(shù)據(jù)★★☆☆☆
示例代碼：
public static void main(String[] args) {
ArrayList<String> strs = new ArrayList<>();
strs.add("A");
Vector<String> strs2 = new Vector<>();
strs2.add("A");
System.out.println(strs.equals(strs2));
//運行結果：true
}
//AbstractList中equals的源代碼：
public boolean equals(Object o) {
if (o == this)
return true;
//判斷是否是列表，注意：只需要實現(xiàn)List接口
if (!(o instanceof List))
return false;
//通過迭代器訪問所有元素
ListIterator<E> e1 = listIterator();
ListIterator<?> e2 = ((List<?>) o).listIterator();
//遍歷兩個list的元素
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
//只要存在不相等就退出
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
//長度是否相等
return !(e1.hasNext() || e2.hasNext());
}
得出，列表只是一個容器，只要是同一種類型的容器（如List），不用關心容器的細節(jié)差別（如ArrayList與LinkedList），只要確定所有的元素數(shù)據(jù)相等，那這兩個列表就是相等的。
其他的集合類型，如Set、Map等與此相同，也是只關心集合元素，不用考慮集合類型。
注意：判斷集合是否相等時只須關注元素是否相等即可。
建議70：子列表只是原列表的一個視圖★★☆☆☆
List的subList方法示例：
public static void main(String[] args) {
//定義一個列表list
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
//構造一個包含list的列表list1
List<String> list1 = new ArrayList<>(list);
//subList生成與list相同的列表list2
List<String> list2 = list.subList(0, list.size());
//list2增加一個元素
list2.add("C");
System.out.println(list.equals(list1));
System.out.println(list.equals(list2));
//運行結果：
//false,true
}
為什么subList生成的新列表，在添加了新元素后，還與原列表相等呢？
subList源碼：
public List<E> subList(int fromIndex, int toIndex) {
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}
/**
*subList方法是由AbstractList實現(xiàn)的，它會根據(jù)是不是可以隨機存取來提供不同的SubList實現(xiàn)方式，
* 不過，隨機存儲的使用頻率比較高，而且RandomAccessSubList也是SubList子類，
* 所以所有的操作都是由SubList類實現(xiàn)的（除了自身的SubList方法外）
* */
//SubList類的代碼
class SubList<E> extends AbstractList<E> {
//原始列表
private final AbstractList<E> l;
//偏移量
private final int offset;
private int size;
//構造函數(shù)，list參數(shù)就是我們的原始列表
SubList(AbstractList<E> list, int fromIndex, int toIndex) {
/***省略校驗代碼***/
//傳遞原始列表
l = list;
offset = fromIndex;
//子列表的長度
size = toIndex - fromIndex;
this.modCount = l.modCount;
}
//獲取指定位置的元素
public E get(int index) {
/***省略校驗代碼***/
//從原始字符串中獲得指定位置的元素
return l.get(index+offset);
}
//增加或插入
public void add(int index, E element) {
/***省略校驗代碼***/
//直接增加到原始字符串上
l.add(index+offset, element);
this.modCount = l.modCount;
size++;
}
/***其他代碼省略***/
}
從源碼得出：subList方法的實現(xiàn)原理，它返回的SubList類也是AbstractList的子類，其所有的方法如get、set、add、remove等都是在原始列表上的操作，它自身并沒有生成一個數(shù)組或是鏈表，也就是子列表只是原列表的一個視圖（View），所有的修改動作都反映在了原列表上。
最后，為什么變量list與list1不相等?
因為通過ArrayList構造函數(shù)創(chuàng)建的List對象list1實際上是新列表，它是通過數(shù)組的copyOf動作生成的，所生成的列表list1與原列表list之間沒有任何關系（雖然是淺拷貝，但元素類型是String，也就是說元素是深拷貝的），雖然此時equals是相等的，但是隨后list又增加了元素，因此equals比較肯定不相等了。
注意：subList產(chǎn)生的列表只是一個視圖，所有的修改動作直接作用于原列表。
建議71：推薦使用subList處理局部列表★★☆☆☆
示例代碼：
//需求：一個列表有10個元素，現(xiàn)在要刪除索引位置為2～6的元素
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(i);
}
//一行代碼就解決問題(subList方法所有的操作都是在原始列表上進行的)
list.subList(2, 6).clear();
}
建議72：生成子列表后不要再操作原列表★★☆☆☆
前面說了，subList生成的子列表是原列表的一個視圖，那在subList執(zhí)行完后，如果修改了原列表的內(nèi)容會怎樣呢？
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
//子列表
List<String> subList = list.subList(0, 2);
//原列表增加一個元素
list.add("D");
System.out.println("list長度:" + list.size());
System.out.println("subList長度:" + subList.size());
}
運行結果：subList的size方法異常 （并發(fā)修改異常）
list長度:4
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1231)
at java.util.ArrayList$SubList.size(ArrayList.java:1040)
at com.jyswm.demo1.t151.Client.main(Client.java:19)
/**
* 因為subList取出的列表是原列表的一個視圖，原數(shù)據(jù)集（代碼中的list變量）修改了，
* 但是subList取出的子列表不會重新生成一個新列表（這點與數(shù)據(jù)庫視圖是不相同的），
* 后面在對子列表繼續(xù)操作時，就會檢測到修改計數(shù)器與預期的不相同，
* 于是就拋出了并發(fā)修改異常。
*/
SubList的size方法的源碼
private class SubList extends AbstractList<E> implements RandomAccess {
public int size() {
checkForComodification();
return this.size;
}
//checkForComodification方法就是用于檢測是否并發(fā)修改的
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
}
解決辦法：
public static void main(String[] args) {
List<String> list = new ArrayList<>();
//子列表
List<String> subList = list.subList(0, 2);
//設置原列表list為只讀狀態(tài)
list = Collections.unmodifiableList(list);
}
注意：
subList生成子列表后，保持原列表的只讀狀態(tài)。
建議73：使用Comparator進行排序★★☆☆☆
在Java中，要想給數(shù)據(jù)排序，有兩種實現(xiàn)方式，一種是實現(xiàn)Comparable接口，一種是實現(xiàn)Comparator接口，這兩者有什么區(qū)別呢？示例代碼：
/**
* 員工類
*/
@Data
public class Employee implements Comparable<Employee> {
/**
* 工號
*/
private int id;
/**
* 職位
*/
private Position position;
public Employee(int id, Position position) {
this.id = id;
this.position = position;
}
@Override
public int compareTo(Employee o) {
return new CompareToBuilder()
.append(id, o.id).toComparison();
}
}
public enum Position {
Boss, Manager, Staff
}
先按id工號來排序
public static void main(String[] args) {
List<Employee> list = new ArrayList<>(5);
list.add(new Employee(1001, Position.Boss));
list.add(new Employee(1005, Position.Manager));
list.add(new Employee(1003, Position.Staff));
list.add(new Employee(1002, Position.Staff));
list.add(new Employee(1004, Position.Staff));
//按工號排序
Collections.sort(list);
for (Employee employee : list) {
System.out.println(employee);
}
/**
* 運行結果:
* Employee(id=1001, position=Boss)
* Employee(id=1002, position=Staff)
* Employee(id=1003, position=Staff)
* Employee(id=1004, position=Staff)
* Employee(id=1005, position=Manager)
*/
}
此時，我們希望按照職位來排序，并不重構Employee類，那怎么做呢？
Collections.sort方法，它有一個重載方法Collections. sort(List<T> list, Comparator<?super T>c)，可以接受一個Comparator實現(xiàn)類，用法如下：
class PositionComparator implements Comparator<Employee> {
@Override
public int compare(Employee o1, Employee o2) {
//按照職位降序
return o1.getPosition().compareTo(o2.getPosition());
}
}
//擴展: 按職位臨時倒序排列呢？注意只是臨時的，是否要重寫一個排序器？完全不用，有兩個解決辦法：
//1.直接使用Collections. reverse(List<?>list)方法實現(xiàn)倒序排列。
//2.通過Collections.sort(list, Collections.reverseOrder(new PositionComparator()))也可以實現(xiàn)倒序排列。
回到原題：在Java中，為什么要有兩個排序接口呢？
實現(xiàn)了Comparable接口的類表明自身是可比較的，有了比較才能進行排序；
而Comparator接口是一個工具類接口，它的名字（比較器）也已經(jīng)表明了它的作用：用作比較，它與原有類的邏輯沒有關系，只是實現(xiàn)兩個類的比較邏輯。
從這方面來說，一個類可以有很多的比較器，只要有業(yè)務需求就可以產(chǎn)生比較器，有比較器就可以產(chǎn)生N多種排序，而Comparable接口的排序只能說是實現(xiàn)類的默認排序算法，一個類穩(wěn)定、成熟后其compareTo方法基本不會改變，也就是說一個類只能有一個固定的、由compareTo方法提供的默認排序算法。
注意:
Comparable接口可以作為實現(xiàn)類的默認排序法，Comparator接口則是一個類的擴展排序工具。
建議74：不推薦使用binarySearch對列表進行檢索★★☆☆☆
示例代碼：
public static void main(String[] args) {
List<String> cities = new ArrayList<>();
cities.add("上海");
cities.add("廣州");
cities.add("廣州");
cities.add("北京");
cities.add("天津");
//indexOf方法取得索引值
System.out.println("indexOf索引值："+cities.indexOf("廣州"));
//binarySearch方法取得索引值
System.out.println("binarySearch索引值："+Collections.binarySearch(cities, "廣州"));
/**
* 運行結果：
* indexOf索引值：1
* binarySearch索引值：2
*/
}
binarySearch方法返回結果錯誤了，為什么？
JDK上對binarySearch的描述：使用二分搜索法搜索指定列表，以獲得指定對象。
但是二分法查詢的一個首要前提是：數(shù)據(jù)集已經(jīng)實現(xiàn)升序排列，否則二分法查找的值是不準確的。
簡單解決辦法：使用Collections.sort排下序，再用binarySearch檢索。
需要注意的場景：元素數(shù)據(jù)是從Web或數(shù)據(jù)庫中傳遞進來的，原本是一個有規(guī)則的業(yè)務數(shù)據(jù)，我們?yōu)榱瞬檎乙粋€元素對它進行了排序，也就是改變了元素在列表中的位置，那誰來保證業(yè)務規(guī)則此時的正確性呢？所以說，binarySearch方法在此處受限了。當然，拷貝一個數(shù)組，然后再排序，再使用binarySeach查找指定值，也可以解決該問題（除非處于性能的的考慮，否則使用indexOf簡單、好用，而且也不會出錯）。
binarySearch的二分法查找比indexOf的遍歷算法性能上高幾十倍。
注意從：性能方面考慮，
binarySearch是最好的選擇。
建議75：集合中的元素必須做到compareTo和equals同步★★☆☆☆
示例代碼：
@Data
static class City implements Comparable<City> {
private String code;
private String name;
public City(String code, String name) {
this.code = code;
this.name = name;
}
@Override
public int compareTo(City o) {
//安裝城市名稱排序
return new CompareToBuilder()
.append(name, o.name).toComparison();
}
@Override
public boolean equals(Object obj) {
/***省略其他判斷***/
City city = (City) obj;
//根據(jù)code判斷是否相等
return new EqualsBuilder()
.append(code, city.code).isEquals();
}
}
public static void main(String[] args) {
//把多個城市對象放在一個List中，然后使用不同的方法查找同一個城市，看看返回值有什么異常。
List<City> cities = new ArrayList<>();
cities.add(new City("021", "上海"));
cities.add(new City("021", "滬"));
//排序
Collections.sort(cities);
//查找對象
City city = new City("021", "滬");
//indexOf方法取得索引值
System.out.println("indexOf索引值：" + cities.indexOf(city));
//binarySearch方法取得索引值
System.out.println("binarySearch索引值：" + Collections.binarySearch(cities, city));
/**
* 運行結果：
* indexOf索引值：0
* binarySearch索引值：1
*/
}
indexOf返回的是第一個元素，而binarySearch返回的是第二個元素，怎么回事呢？
這是因為indexOf是通過equals方法判斷的，equals等于true就認為找到符合條件的元素了，而binarySearch查找的依據(jù)是compareTo方法的返回值，返回0即認為找到符合條件的元素。
從這個例子中，我們可以理解兩點：
-
indexOf依賴equals方法查找，binarySearch則依賴compareTo方法查找。 -
equals是判斷元素是否相等，compareTo是判斷元素在排序中的位置是否相同。
注意：實現(xiàn)了
compareTo方法，就應該覆寫equals方法，確保兩者同步。
建議76：集合運算時使用更優(yōu)雅的方式★☆☆☆☆
public static void main(String[] args) {
List<String> list1 = new ArrayList<>();
list1.add("A");
List<String> list2 = new ArrayList<>();
list2.add("B");
}
-
并集
list1.addAll(list2); -
交集
list1.retainAll(list2); -
差集
list1.removeAll(list2); -
無重復并集
//刪除list1中出現(xiàn)的元素 list2.removeAll(list1); //把剩余的list2元素加到list1 list1.addAll(list2);
建議77：使用shuffle打亂列表★☆☆☆☆
示例代碼：
public static void main(String[] args) {
int num = 10;
List<String> tags = new ArrayList<>(num);
for (int i = 0; i < num; i++) {
tags.add(i+"");
}
//打亂順序
Collections.shuffle(tags);
}
建議78：減少HashMap中元素的數(shù)量★★★☆☆
問題描述：同一環(huán)境中，分別向HashMap和List中添加40萬個字符串元素，向Map中添加元素的程序報內(nèi)存溢出，向List中添加元素的程序卻正常。
原因一：內(nèi)部存儲結構，代碼如下：
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
//鍵
final K key;
//值
V value;
//相同哈希碼的下一個元素
Entry<K,V> next;
/***省略其他代碼***/
}
HashMap底層的數(shù)組變量名叫table，它是Entry類型的數(shù)組，保存的是一個一個的鍵值對（在我們的例子中Entry是由兩個String類型組成的）。HashMap在底層雖然也是以數(shù)組方式保存元素的，其中每一個鍵值對就是一個元素，但是HashMap把鍵值對封裝成了一個Entry對象，然后再把Entry放到了數(shù)組中。HashMap比ArrayList多了一次封裝，把String類型的鍵值對轉換成Entry對象后再放入數(shù)組，這就多了40萬個對象
原因二：它的擴容機制，代碼如下：
//在插入鍵值對時，會做長度校驗，如果大于或等于閥值（threshold變量），則數(shù)組長度增大一倍
if (size++ >= threshold) {
resize(2 * table.length)
}
//也就是說只要HashMap的size大于數(shù)組長度的0.75倍時，就開始擴容
threshold = (int) (newCapacity * 0.75)
由上得出，Map在擴容的時候預留了太多空間。在內(nèi)存占用的臨界點，由于內(nèi)存剩余不足，無法提供下次擴容所需要的內(nèi)存，導致擴容失敗。但真正需要添加的數(shù)據(jù)，可能只是需要再擴容一個單位就可以放下。所以有時會產(chǎn)生，在我們看來，系統(tǒng)所分配的內(nèi)存完全可以存放下這些數(shù)據(jù)，但是在用Map存儲時卻內(nèi)存溢出了。
注意：盡量讓HashMap中的元素少量并簡單。
**建議79：集合中的哈希碼不要重復★☆☆☆☆
以HashMap的查找元素為例：
- 以
key的hashCode定位元素的位置，所以查找元素比較快（比List快）。 - 當
hashCode沖突時，則遍歷對比（和List的遍歷對比類似），所以當hashCode沖突時，查找元素的效率會大大降低。
注意：HashMap中的hashCode應避免沖突。
建議80：多線程使用Vector或HashTable★★☆☆☆
Vector是ArrayList的多線程版本，Vector的每個方法前都加上了synchronized關鍵字，同時只會允許一個線程進入該方法，確保了程序的可靠性。
HashTable是HashMap的多線程版本，它的實現(xiàn)與Vector相同。
建議81：非穩(wěn)定排序推薦使用List★☆☆☆☆
Set與List的最大區(qū)別就是Set中的元素不可以重復（這個重復指的equals方法的返回值相等），其他方面則沒有太大的區(qū)別了，在Set的實現(xiàn)類中有一個比較常用的類：TreeSet，該類實現(xiàn)了類默認排序為升序的Set集合，如果插入一個元素，默認會按照升序排列（是根據(jù)Comparable接口的compareTo的返回值確定排序位置了）
注意： SortedSet接口（TreeSet實現(xiàn)了該接口）只是定義了在給集合加入元素時將其進行排序，并不能保證元素修改后的排序結果，因此TreeSet適用于不變量的集合數(shù)據(jù)排序，比如String、Integer等類型，但不適用于可變量的排序，特別是不確定何時元素會發(fā)生變化的數(shù)據(jù)集合。
注意：
SortedSet中的元素被修改后可能會影響其排序位置。
建議82：由點及面，一葉知秋—集合大家族★☆☆☆☆
Java中的集合類實在是太豐富了，有常用的ArrayList、HashMap，也有不常用的Stack、Queue，有線程安全的Vector、HashTable，也有線程不安全的LinkedList、TreeMap，有阻塞式的ArrayBlockingQueue，也有非阻塞式的PriorityQueue等，整個集合家族非常龐大，而且也是錯綜復雜，可以劃分為以下幾類：
（1）List
實現(xiàn)List接口的集合主要有：ArrayList、LinkedList、Vector、Stack，其中ArrayList是一個動態(tài)數(shù)組，LinkedList是一個雙向鏈表，Vector是一個線程安全的動態(tài)數(shù)組，Stack是一個對象棧，遵循先進后出的原則。
（2）Set
Set是不包含重復元素的集合，其主要的實現(xiàn)類有：EnumSet、HashSet、TreeSet，其中EnumSet是枚舉類型的專用Set，所有元素都是枚舉類型；HashSet是以哈希碼決定其元素位置的Set，其原理與HashMap相似，它提供快速的插入和查找方法；TreeSet是一個自動排序的Set，它實現(xiàn)了SortedSet接口。
（3）Map
Map是一個大家族，它可以分為排序Map和非排序Map，排序Map主要是TreeMap類，它根據(jù)Key值進行自動排序；非排序Map主要包括：HashMap、HashTable、Properties、EnumMap等，其中Properties是HashTable的子類，它的主要用途是從Property文件中加載數(shù)據(jù)，并提供方便的讀寫操作；EnumMap則是要求其Key必須是某一個枚舉類型。
Map中還有一個WeakHashMap類需要說明，它是一個采用弱鍵方式實現(xiàn)的Map類，它的特點是：WeakHashMap對象的存在并不會阻止垃圾回收器對鍵值對的回收，也就是說使用WeakHashMap裝載數(shù)據(jù)不用擔心內(nèi)存溢出的問題，GC會自動刪除不用的鍵值對，這是好事。但也存在一個嚴重問題：GC是靜悄悄回收的（何時回收？God knows!），我們的程序無法知曉該動作，存在著重大的隱患。
（4）Queue
隊列，它分為兩類，一類是阻塞式隊列，隊列滿了以后再插入元素則會拋出異常，主要包括：ArrayBlockingQueue、PriorityBlockingQueue、LinkedBlockingQueue，其中ArrayBlockingQueue是一個以數(shù)組方式實現(xiàn)的有界阻塞隊列，PriorityBlockingQueue是依照優(yōu)先級組建的隊列，LinkedBlockingQueue是通過鏈表實現(xiàn)的阻塞隊列；另一類是非阻塞隊列，無邊界的，只要內(nèi)存允許，都可以持續(xù)追加元素，我們最經(jīng)常使用的是PriorityQueue類。
還有一種隊列，是雙端隊列，支持在頭、尾兩端插入和移除元素，它的主要實現(xiàn)類是：ArrayDeque、LinkedBlockingDeque、LinkedList。
（5）數(shù)組
數(shù)組與集合的最大區(qū)別就是數(shù)組能夠容納基本類型，而集合就不行，更重要的一點就是所有的集合底層存儲的都是數(shù)組。
（6）工具類
數(shù)組的工具類是java.util.Arrays和java.lang.reflect.Array，集合的工具類是java.util.Collections，有了這兩個工具類，操作數(shù)組和集合會易如反掌，得心應手。
（7）擴展類
集合類當然可以自行擴展了，想寫一個自己的List？沒問題，但最好的辦法還是“拿來主義”，可以使用Apache的commons-collections擴展包，也可以使用Google的google-collections擴展包，這些足以應對我們的開發(fā)需要。
注意：
commons-collections、google-collections是JDK之外的優(yōu)秀數(shù)據(jù)集合工具包，使用拿來主義即可。
