數(shù)據(jù)結(jié)構(gòu)

?????? Java中的數(shù)組有差不多一樣的語法沛厨。只是java中處理8種基本類型，數(shù)組也是作為對象處理的用爪，所以創(chuàng)建對象時也需要使用new關(guān)鍵字粉渠。和大多數(shù)編程語言一樣分冈，數(shù)組一旦創(chuàng)建，大小便不可變渣叛。

Java中有一個Arrays類丈秩，專門用來操作array。

Arrays中擁有一組static函數(shù)淳衙，

-equals()：比較兩個array是否相等蘑秽。array擁有相同元素個數(shù)，且所有對應(yīng)元素兩兩相等箫攀。

-fill()：將值填入array中肠牲。

-sort()：用來對array中尋找元素。

-System.arraycopy()：array的復(fù)制靴跛。

?int[] intArr = new int[10];

Array時Java中隨機(jī)訪問一連串對象最有效率的數(shù)據(jù)結(jié)構(gòu)缀雳，但很不靈活，大小固定梢睛，且不知道里面有多少元素肥印。為此JDK已經(jīng)為我們提供了一系列相應(yīng)的類來實現(xiàn)功能強(qiáng)大且更靈活的基本數(shù)據(jù)結(jié)構(gòu)识椰。這些類均在java.util包中。其繼承結(jié)構(gòu)如下：

Collection

├List

│├LinkedList

│├ArrayList

│└Vector

│　└Stack

└Set

│? ? └SortedSet

└Queue

-Map

├HashTable

├HashMap

└WeakHashMap

List

List是一個接口深碱，不能實例化腹鹉，需要實例化一個ArrayList或者LinkedList。

ArrayList里面的內(nèi)部實現(xiàn)敷硅，是通過一定的增長規(guī)則動態(tài)復(fù)制增加數(shù)組長度來實現(xiàn)動態(tài)增加元素的功咒。如果在大數(shù)據(jù)量的情況下，在某一個位置隨機(jī)插入或者刪除元素绞蹦，就會產(chǎn)生性能問題力奋。LinkedList可以解決這類問題，但LinkedList在通過下標(biāo)取元素的時候幽七，需要遍歷整個鏈表節(jié)點匹配景殷，數(shù)據(jù)量大的情況下，效率不高锉走。Vector是一種老的動態(tài)數(shù)組滨彻，是線程同步的藕届，效率很低挪蹭，一般不贊成使用。Stack是Java實現(xiàn)了一個堆棧休偶，先進(jìn)后出結(jié)構(gòu)梁厉。

遍歷時刪除問題

使用增強(qiáng)for循環(huán)遍歷List（所有實現(xiàn)子類ArrayList，Stack等）元素對其中的元素進(jìn)行刪除踏兜，會拋出java.util.ConcurrentModificationException的異常词顾。若使用下面這種方式：

for(int i = 0; i < list.size(); i++) {????

???? list.remove(i);

}

則會刪除下標(biāo)為偶數(shù)的元素，因為每次刪除后碱妆，后面的元素的下標(biāo)全部減1肉盹，相當(dāng)于元素位置全部左移一位，再次刪除時疹尾，會跳過一個元素進(jìn)行刪除上忍。這是非常不好的。如果非要這樣刪除纳本，可以倒著來：

for(int i = list.size() - 1; i >= 0; i--){

???? list.remove(i);

}

或者新建一個要刪除的List窍蓝，最后一起刪除。list.removeAll(deleteList);

Set

Set接口繼承Collection接口繁成，最大的特點是集合中的元素都是唯一的吓笙，沒有重復(fù)，它有兩個子類巾腕，HashSet和TreeSet面睛。

HashSet

?? 1.不允許重復(fù)元素絮蒿；

?? 2.不保證集合中元素的順序，哈希算法來的叁鉴；

?? 3.允許包含值為null的元素歌径，但最多只能有一個null元素；

TreeSet

?? 1.不允許出現(xiàn)重復(fù)元素亲茅；

?? 2.集合中元素的順序按照某種規(guī)則進(jìn)行排序回铛；

?? 3.不允許包含值為null的元素；

Map

Map接口克锣，沒有繼承Collection接口茵肃，它是獨(dú)立的一個接口。它使用key-value的鍵值對存儲數(shù)據(jù)袭祟。常用兩個子類是HashMap和TreeMap验残。

-HashMap：Map基于散列表的實現(xiàn)。插入和查詢“鍵值對”的開銷是固定的巾乳∧唬可以通過構(gòu)造器設(shè)置容量capacity和負(fù)載因子load facor，以調(diào)整容器的性能胆绊。

-LinkedHashMap：類似于HashMap氨鹏，但是迭代遍歷它時，取得“鍵值對”的順序是其插入的順序压状，或者是最近最少使用（LRU）的次序仆抵。只比HashMap慢一點。它使用鏈表維護(hù)內(nèi)部次序种冬。

-TreeMap：基于紅黑樹數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)镣丑。查看“鍵”或“鍵值對”時，它們會被排序(次序由Comparabel或Comparator決定)娱两。TreeMap的特點在 于莺匠，你得到的結(jié)果是經(jīng)過排序的。TreeMap是唯一的帶有subMap()方法的Map十兢，它可以返回一個子樹趣竣。

-WeakHashMap：弱鍵(weak key)Map，Map中使用的對象也被允許釋放: 這是為解決特殊問題設(shè)計的纪挎。如果沒有map之外的引用指向某個“鍵”期贫，則此“鍵”可以被垃圾收集器回收。

-IdentifyHashMap：使用==代替equals()對“鍵”作比較的hash map异袄。專為解決特殊問題而設(shè)計通砍。

線程安全

Vector是線程同步的，也就是線程安全的，對多線程的操作采用了synchronized處理封孙，但因為效率低迹冤，已不建議使用。ArrayList和LinkedList都是線程不安全的虎忌，在多線程環(huán)境中泡徙，對數(shù)據(jù)的修改造成錯誤的結(jié)果。有兩種解決方案：

使用同步包裝器

List safedList = Collections.synchronizedList(new ArrayList());

Set safedSet = Collections.synchronizedSet(new HashSet());

Map safedMap = Collections.synchronizedMap(new HashMap());

查看其源碼膜蠢，發(fā)現(xiàn)是Collections類給不安全的集合類包裝了一層堪藐，然后生成一個新的類，新類里面采用了synchronized對集合的操作進(jìn)行了同步處理挑围。

使用安全的集合類

Java5.0新加入的ConcurrentLinkedQueue礁竞、ConcurrentHashMap、CopyOnWriteArrayList和CopyOnWriteArraySet杉辙，這些集合類都是線程安全的模捂。這些類在java.util.concurrent包下。

Android中的List蜘矢、Map替代方案

SimpleArrayMap

SparseArray與SparseArrayCompat和LongSparseArray

這3個類中狂男，前2個基本上是同一類，只不過第二個類有removeAt方法品腹，第三個是Long類型的岖食。

這3個類也是用來代替HashMap,只不過他們的鍵(key)的類型是整型Integer或者Long類型，在實際開發(fā)中珍昨，如月份縮寫的映射县耽，或者進(jìn)行文件緩存映射，ViewHolder都特別適用

AtomicFile

AtomicFile首先不是用來代替File的镣典，而是作為File的輔助類存在， AtomicFile的作用是實現(xiàn)事務(wù)性原子操作唾琼，即文件讀寫必須完整兄春，適合多線程中的文件讀寫操作。

用來實現(xiàn)多線程中的文件讀寫的安全操作

算法

二分查找

對于有序數(shù)組锡溯，二分查找的效率在大數(shù)據(jù)量的情況下赶舆，效率明顯：

private static int find(int [] arr,int searchKey) {

??????????? int lowerBound = 0;

??????????? int upperBound = arr.length -1;

??????????? int curIn;

??????????? while(lowerBound <= upperBound) {

???????????????????? curIn = (lowerBound + upperBound) / 2;

???????????????????? if(arr[curIn] == searchKey) {

??????????????????????????? return curIn;

???????????????????? }else{

??????????????????????????? if(arr[curIn] < searchKey) {

???????????????????????????????????? lowerBound = curIn + 1;

??????????????????????????? }else {

???????????????????????????????????? upperBound = curIn - 1;

??????????????????????????? }

??????????????????? }

????????? }

????????????????? return -1;

}

使用遞歸的方式編寫救恨，貌似看起來好理解點：

private static int recursiveFind(int[] arr,int start,int end,int searchKey) {

??????????? if (start <= end) {

??????????????? // 中間位置

??????????????? int middle = (start + end) / 2;

??????????????? if (searchKey == arr[middle]) {

??????????????????? // 等于中值直接返回

??????????????????? return middle;

???????????????? } else if (searchKey < arr[middle]) {

???????????????????? // 小于中值時在中值前面找

??????????????????? return recursiveFind(arr, start, middle - 1, searchKey);

??????????????? } else {

???????????????????? // 大于中值在中值后面找

???????????????????? return recursiveFind(arr, middle + 1, end, searchKey);

?????????????? }

??????? } else {

???????????? // 找不到

???????????? return -1;

?? }

}

排序

簡單排序

冒泡排序

對亂序的數(shù)組封拧，很常見的排序方法是冒泡排序：

private static void bubbleSrot(int[] arr) {

??????????? for (int i = 0; i < arr.length - 1; i++) {

?????????????????? for (int j = i + 1; j < arr.length; j++) {

???????????????????????? if(arr[i] > arr[j]) {

????????????????????????????? int temp = arr[i];

????????????????????????????? arr[i] = arr[j];

????????????????????????????? arr[j] = temp;

????????????????????????? }

???????????????????? }

???????????? }

}

這種排序方法速度是很慢的，運(yùn)行時間為O（N2）級产镐。

選擇排序改進(jìn)了冒泡排序倡蝙，將必要的交換次數(shù)從O（N2）減少到O（N）九串，不幸的是比較次數(shù)依然是O（N2）級。

然而，選擇排序依然為大記錄量的排序提出了一個非常重要的改進(jìn)猪钮，因為這些大量的記錄需要在內(nèi)存中移動品山，這就使交換的時間和比較的時間相比起來，交換的時間更為重要烤低。（一般來說肘交，Java語言中不是這種情況，Java中只是改變了引用位置扑馁，而實際對象的位置并沒有發(fā)生改變）

選擇排序

private static void chooseSort(int[] arr) {

??????????? for (int i = 0; i < arr.length; i++) {

????????????????? int least = i;

????????????????? for (int j = i + 1; j < arr.length; j++) {

??????????????????????? if (arr[j] < arr[least]) {

??????????????????????????? least = j;

???????????????????????? }

?????????????????? }

????????????? // 將當(dāng)前第一個元素與它后面序列中的最小的一個 元素交換涯呻，也就是將最小的元素放在最前端

?????????????? int temp = arr[i];

?????????????? arr[i] = arr[least];

?????????????? arr[least] = temp;

????????? }

}

選擇排序的效率：選擇排序和冒泡排序執(zhí)行了相同次數(shù)的比較：N*(N-1)/2。對于10個數(shù)據(jù)項腻要，需要45次比較魄懂，然而，10個數(shù)據(jù)項只需要少于10次的交換闯第。對于100個數(shù)據(jù)項市栗，需要4950次比較，但只進(jìn)行不到100次交換咳短。N值很大時填帽，比較的次數(shù)是主要的，所以結(jié)論是選擇排序和冒泡排序一樣運(yùn)行了O（N2）時間咙好。但是篡腌，選擇排序無疑更快，因為它進(jìn)行的交換少得多勾效。

插入排序

插入排序嘹悼，在一般情況下，比冒泡排序快一倍层宫，比選擇排序快一點杨伙。

private static void insertionSort(int[] arr) {

??????????? int in = 0;

??????????? int out = 0;

??????????? for(out = 1 ; out < arr.length ; out ++) {

???????????????? int temp = arr[out];

???????????????? in = out;

???????????????? while(in > 0 && arr[in-1] >= temp) {

????????????????????????? arr[in] = arr[in - 1];

????????????????????????? --in;

???????????????? }

???????????????? arr[in] = temp;

???????????? }

}

在外層的for循環(huán)中，out變量從1開始萌腿，向右移動限匣。它標(biāo)記了未排序部分的最左端數(shù)據(jù)。而在內(nèi)層的while循環(huán)中毁菱，in變量從out變量開始米死，向左移動，直到temp變量小于in所指的數(shù)組數(shù)據(jù)項贮庞，或者它已經(jīng)不能再向左移動為止峦筒。while循環(huán)的每一趟都向左移動了一個已排序的數(shù)據(jù)項。

插入排序的效率：這個算法中窗慎，第一趟排序，最多比較一次，第二趟排序脯丝，最多比較兩次商膊，以此類推，最后一趟最多比較N-1次宠进，因此有1+2+3+…+N-1 = N*(N-1)/2晕拆。然而，因為在每一趟排序發(fā)現(xiàn)插入點之前材蹬，平均只有全體數(shù)據(jù)項的一半真的進(jìn)行了比較实幕，所以除以2最后是N*(N-1)/4。

對于隨機(jī)順序的數(shù)據(jù)堤器，插入排序也需要O（N2）的時間級昆庇。當(dāng)數(shù)據(jù)基本有序，插入排序幾乎只需要O(N)的時間闸溃，這對把一個基本有序的文件進(jìn)行排序是一個簡單而有效的方法整吆。

對于逆序排列的數(shù)據(jù)，每次比較和移動都會執(zhí)行辉川，所以插入排序不比冒泡排序快表蝙。

歸并排序

歸并排序比簡單排序要有效的多，至少在速度上是這樣的乓旗。冒泡排序府蛇、選擇排序、插入排序要用O（N2）的時間屿愚，而歸并排序只需要O(N*logN)的時間汇跨。

歸并排序的一個缺點是它需要在存儲器中有另一個大小等于被排序的數(shù)據(jù)項數(shù)目的數(shù)組。如果初始數(shù)組幾乎占滿整個存儲器妆距，那么歸并排序?qū)⒉荒芄ぷ髑钏臁５牵绻凶銐虻目臻g毅厚，歸并排序會是一個很好的選擇塞颁。

原理是合并兩個已排序的數(shù)組到一個數(shù)組：

//將兩個已排序的數(shù)組合并到第三個數(shù)組上。

private static void merge(int[] arrA, int[] arrB, int[] arrC) {

??????????? int aDex = 0;

??????????? int bDex = 0;

??????????? int cDex = 0;

??????????? int sizeA = arrA.length;

??????????? int sizeB = arrB.length;

??????????? // A數(shù)組和B數(shù)組都不為空

??????????? while (aDex < sizeA && bDex < sizeB) {

????????????????????? if (arrA[aDex] < arrB[bDex]) {

????????????????????????? arrC[cDex++] = arrA[aDex++];

?????????????????????? } else {

????????????????????????? arrC[cDex++] = arrB[bDex++];

?????????????????????? }

????????????? }

????????????? //A數(shù)組不為空吸耿，B數(shù)組為空

????????????? while (aDex < sizeA) {

??????????????????????? arrC[cDex++] = arrA[aDex++];

????????????? }

???????????? //A數(shù)組為空，B數(shù)組不為空

???????????? while (bDex < sizeB) {

?????????????????????? arrC[cDex++] = arrB[bDex++];

???????????? }

}

于是酷窥，詳細(xì)的完整實現(xiàn)如下：

static class DArray{

???????? private int [] theArray;

???????? public DArray(int[] theArray) {

??????????????????? this.theArray = theArray;

???????? }

???????? //執(zhí)行歸并排序

???????? public void mergeSort() {

??????? ? ? ? ? ?? //復(fù)制一份出來

?????????????????? int [] workSpace = new int [theArray.length];

?????????????????? reMergeSort(workSpace, 0, theArray.length-1);

??????? }

??????? private void reMergeSort(int [] workSpace,int lowerBound,int upperBound) {

??????????????????? if(lowerBound == upperBound){

?????????????????????? return;

??????????????????? }else{

?????????????????????? int mid = (lowerBound + upperBound) / 2;

?????????????????????? reMergeSort(workSpace, lowerBound, mid);

?????????????????????? reMergeSort(workSpace, mid + 1, upperBound);

?????????????????????? merge(workSpace, lowerBound, mid + 1,upperBound);

??????????????????? }

????????? }

????????? private void merge(int [] workSpace,int lowPtr,int highPtr,int upperBound){

????????????????????? int j= 0; //workSpace's index

????????????????????? int lowerBound = lowPtr;

????????????????????? int mid = highPtr -1;

????????????????????? int n = upperBound - lowerBound + 1;

????????????????????? while(lowPtr <= mid && highPtr <= upperBound) {

??????????????????????????????? if(theArray[lowPtr] < theArray[highPtr]) {

?????????????????????????????????? workSpace[j++] = theArray[lowPtr++];

??????????????????????????????? }else{

?????????????????????????????????? workSpace[j++] = theArray[highPtr++];

??????????????????????????????? }

?????????????????????? } while(lowPtr <= mid) {

????????????????????????????????? workSpace[j++] = theArray[lowPtr++];

?????????????????????? } while(highPtr <= upperBound) {

?????????????????????????????????? workSpace[j++] = theArray[highPtr++];

??????????????????????? }

?????????????????????? for(j = 0;j < n ;j++) {

??????????????????????????? theArray[lowerBound+j] = workSpace[j];

?????????????????????? }

????????? }

}

高級排序

有2個高級的排序算法咽安，希爾排序和快速排序。這兩種排序算法都比簡單排序算法快得多：希爾排序大約需要O(N*(logN)2)時間蓬推，快速排序需要O(N*logN)時間妆棒。這兩種排序算法都和歸并排序不同，不需要大量的輔助存儲空間。希爾排序幾乎和歸并排序一樣容易實現(xiàn)糕珊，而快速排序是所有通用排序算法中最快的一種排序算法动分。

還有一種基數(shù)排序，是一種不常用但很有趣的排序算法红选。

希爾排序

希爾排序是基于插入排序的澜公。

private static void shellSort(int[] arr) {

??????????? int inner, outer;

??????????? int temp;

??????????? int h = 1;

??????????? int nElem = arr.length;

??????????? while (h <= nElem / 3) {

????????????????????? h = h * 3 + 1;

??????????? }

??????????? while (h > 0) {

????????????????????? for (outer = h; outer < nElem; outer++) {

??????????????????????????? temp = arr[outer];

??????????????????????????? inner = outer;

??????????????????????????? while (inner > h - 1 && arr[inner - h] >= temp) {

????????????????????????????????????? arr[inner] = arr[inner - h];

????????????????????????????????????? inner -= h;

???????????????????????????? }

???????????????????????????? arr[inner] = temp;

?????????????????????? }

?????????????????????? h = (h - 1) / 3;

??????????? }

}

快速排序

快速排序是最流行的排序算法，在大多數(shù)情況下喇肋，快速排序都是最快的坟乾，執(zhí)行時間是O(N*logN)級。

劃分

劃分是快速排序的根本機(jī)制蝶防。劃分本身也是一個有用的操作甚侣。

劃分?jǐn)?shù)據(jù)就是把數(shù)據(jù)分為兩組，使所有關(guān)鍵字大于特定值的數(shù)據(jù)項在一組间学，所有關(guān)鍵字小于特定值的數(shù)據(jù)項在另一組殷费。

private static int partitionIt(int[] arr ,int left,int right,int pivot){

??????????? int leftPtr = left - 1;

??????????? int rightPtr = right + 1;

??????????? while(true) {

??????????????????? while(leftPtr < right && arr[++leftPtr] < pivot);

??????????????????? while(rightPtr > 0 && arr[--rightPtr] > pivot);

??????????????????? if(leftPtr >= rightPtr) {

?????????????????????? break;

????????????????? ? }else{

?????????????????????? //交換leftPtr和rightPtr位置的元素

????????????????????? int temp = arr[leftPtr];

????????????????????? arr[leftPtr] = arr[rightPtr];

????????????????????? arr[rightPtr] = temp;

?????????????? ? ? }

???????? }

??????? return leftPtr;//返回樞紐位置

}

快速排序(應(yīng)用)

private static void recQuickSort(int arr [] ,int left,int right) {

??????????? if(right - left <= 0){

??????????????????? return;

??????????? }else{

??????????????????? int pivot = arr[right];//一般使用數(shù)組最右邊的元素作為樞紐

??????????????????? int partition = partitionIt(arr, left, right, pivot);

??????????????????? recQuickSort(arr, left, partition-1);

??????????????????? recQuickSort(arr, partition+1, right);

??????????? }

}

//劃分

private static int partitionIt(int[] arr ,int left,int right,int pivot) {

??????????? int leftPtr = left - 1;

?????????? //int rightPtr = right + 1;

??????????? int rightPtr = right ; //使用最右邊的元素作為樞紐，劃分時就要將最右端的數(shù)據(jù)項排除在外

??????????? while(true) {

??????????????????? while(arr[++leftPtr] < pivot);

??????????????????? while(rightPtr > 0 && arr[--rightPtr] > pivot);

??????????????????? if(leftPtr >= rightPtr) {

??????????????????????????? break;

??????????????????? }else {

??????????????????????????? //交換leftPtr和rightPtr位置的元素

??????????????????????????? int temp = arr[leftPtr];

??????????????????????????? arr[leftPtr] = arr[rightPtr];

??????????????????????????? arr[rightPtr] = temp;

??????????????????? }

?????????? }

?????????? //交換leftPtr和right位置的元素

?????????? int temp = arr[leftPtr];

?????????? arr[leftPtr] = arr[right];

?????????? arr[right] = temp;

?????????? return leftPtr;//返回樞紐位置

}

最后測試低葫，10萬條隨機(jī)數(shù)據(jù)详羡，排序完成耗時18~25ms。希爾排序耗時差不多氮采，而簡單排序中的插入排序和選擇排序耗時3500ms以上殷绍，冒泡排序最慢，超過17000ms以上才完成鹊漠；歸并排序比希爾排序和快速排序稍微慢點主到，在30ms左右。