Java數(shù)據(jù)結(jié)構(gòu)與算法初級篇之?dāng)?shù)組、集合和散列表> 數(shù)據(jù)是基礎(chǔ)筑凫，算法是靈魂
本文出自門心叼龍的博客滑沧，屬于原創(chuàng)類容，轉(zhuǎn)載請注明出處巍实。https://blog.csdn.net/geduo_83/article/details/86385566
源碼下載地址：https://download.csdn.net/download/geduo_83/10913510
初級篇：Java數(shù)據(jù)結(jié)構(gòu)與算法初級篇之?dāng)?shù)組滓技、集合和散列表
中級篇：Java數(shù)據(jù)結(jié)構(gòu)與算法中級篇之棧、隊列棚潦、鏈表
高級篇：Java數(shù)據(jù)結(jié)構(gòu)與算法高級篇之樹令漂、圖
理論篇：Java數(shù)組、集合丸边、散列表常見算法淺析
理論篇：Java棧叠必、隊列、鏈表常見算法淺析
理論篇：Java樹妹窖、圖常見算法淺析
1. 前言
2. 數(shù)組
2.1 概念
2.2 特點
2.3 存儲結(jié)構(gòu)
2.4 使用場景
2.5 相關(guān)算法
3. 集合
3.1 概念
3.2 特點
3.3 適用場景
3.4 相關(guān)算法
3.5 性能分析
4. 散列表
4.1 概念
4.2 哈希算法
4.3 哈希沖突
4.4 存儲結(jié)構(gòu)
4.5 特點
4.6 適用場景
4.7 性能分析
5. 小結(jié)
****1. 前言****
之前沒有寫過關(guān)于數(shù)據(jù)結(jié)構(gòu)的文章纬朝，那么今天我們將在本文中介紹最基礎(chǔ)、最簡單的數(shù)據(jù)結(jié)構(gòu)骄呼。
數(shù)組共苛，作為數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的一個存儲方式，是我們學(xué)習(xí)一切數(shù)據(jù)結(jié)構(gòu)蜓萄、算法的基石隅茎。大部分的數(shù)據(jù)結(jié)構(gòu)可以用數(shù)組來實現(xiàn)。接下來我們會介紹數(shù)組的概念绕德、存儲結(jié)構(gòu)患膛、特點和使用場景。
集合算是升級版的數(shù)組耻蛇，在本文當(dāng)中我們會介紹集合的概念踪蹬、特點、實現(xiàn)以及的它的適用場景臣咖。
散列表又叫哈希表跃捣，在很多語言中都是在數(shù)組的基礎(chǔ)上實現(xiàn)的，當(dāng)然散列表也有其他的實現(xiàn)形式夺蛇，本文我們會介紹散列表的基本概念疚漆、特點、實現(xiàn)方式等。
****2. 數(shù)組****
****2.1 概念****
數(shù)組是內(nèi)存中有序的元素序列
****2.2 特點****
定長娶聘、按順序訪問闻镶、索引快、插入刪除慢
****2.3 存儲結(jié)構(gòu)****
[圖片上傳失敗...(image-f51670-1553424312385)]
?[圖片上傳失敗...(image-1f1cb-1553424312387)]
?
****2.4 使用場景****
數(shù)組其實是非常簡單的一個數(shù)據(jù)結(jié)構(gòu)丸升，用起來也比較簡單铆农，他是其他所有數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，所以只有掌握好數(shù)組狡耻，才能學(xué)習(xí)好其他的數(shù)據(jù)結(jié)構(gòu)和算法墩剖。
什么時候使用數(shù)組，通過數(shù)據(jù)的特點我們就可以想到夷狰，數(shù)據(jù)的長度是固定的岭皂，所以不會出現(xiàn)長度變化的業(yè)務(wù)上比較適合使用數(shù)組
如果我們在app開發(fā)中非常常見的菜單按鈕，它的個數(shù)一般都是固定的不會發(fā)生變化沼头，如下圖這個界面有首頁爷绘、報表、消息进倍、我的揉阎，我們就可以用數(shù)組來存儲。
[圖片上傳失敗...(image-c4b201-1553424312385)]
?[圖片上傳失敗...(image-fa42a-1553424312387)]
?
****2.5 相關(guān)算法****
****2.5.1 冒泡排序****
通過相鄰的兩個數(shù)兩兩相比來進(jìn)行排序背捌，其中有兩個循環(huán)，第一個循環(huán)控制循環(huán)的輪次洞斯，第二個循環(huán)控制每一個輪次循環(huán)的次數(shù)毡庆，第一輪循環(huán)確定的最后一個元素，第二輪循環(huán)確定的是倒數(shù)第二個元素烙如，照這樣下去么抗，直到確定了第一個元素，則循環(huán)排序完畢亚铁。
需要注意的是蝇刀，第一個循環(huán)它的結(jié)束條件是i < len-1; 第二個循環(huán)的結(jié)束條件是j < len - i - 1;
package A數(shù)組.A001冒泡排序;
/**
* Description: <冒泡排序><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] arg) {
int[] arr = {1, 3, 10, 1, 34, 5, 21};
sortBubbling(arr);
int i = 0;
while (i < arr.length) {
System.out.println(arr[i]);
i++;
}
}
// 冒泡排序：兩個循環(huán)，通過兩兩相比徘溢，進(jìn)行排序
private static void sortBubbling(int[] arr) {
// 第一輪確定最后一個吞琐，第二輪確定倒數(shù)第二個...
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
// 兩兩相比，就像魚吐水泡一樣...
if (arr[j] > arr[j + 1]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}
}
****2.5.2 選擇排序****
第一步拿出第一個元素和剩余的元素進(jìn)行比較然爆，確定了第一個元素站粟，第二步拿出第二個元素和剩余元素進(jìn)行比較，確定了第二個元素曾雕，照這樣下去奴烙，直到確定了最后一個元素，則循環(huán)排序完畢。和冒泡排序一樣切诀，也是通過兩個循環(huán)來完成的揩环，第一個循環(huán)是控制循環(huán)的輪次，第二個循環(huán)是控制每一輪循環(huán)的次數(shù)幅虑。
需要注意的是丰滑，第一個循環(huán)它的結(jié)束條件是i < len-1和冒泡排序一樣，第二個循環(huán)的開始條件是j = i + 1; 結(jié)束條件是j < len 翘单。
通過分析我們不難得出結(jié)論吨枉，無論是冒泡排序還是選擇排序，第一個控制輪次的循環(huán)的結(jié)束條件都是一樣的都是len - 1; 第二個控制每一輪循環(huán)次數(shù)的條件是相反的哄芜，冒泡排序控制的是結(jié)束條件j < len - i - 1貌亭，而選擇排序控制的是開始條件j = i + i。
這是我們哲學(xué)中講的矛盾认臊，而冒泡和選擇就是我們矛盾的兩個方面圃庭。
package A數(shù)組.A002選擇排序;
/**
* Description: <選擇排序><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] arg) {
int[] arr = {1, 3, 10, 1, 34, 5, 21};
sortChange(arr);
int i = 0;
while (i < arr.length) {
System.out.println(arr[i]);
i++;
}
}
// 選擇排序，選擇第一個元素和剩下的n-1個比較
private static void sortChange(int[] arr) {
// 第一輪確定第一個元素失晴，第二輪確定第二個元素
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
// 選擇第一i個元素和剩余的元素進(jìn)行比較
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
}
****2.5.3 桶排序****
桶排序的核心思想就是以源數(shù)組的值作為新數(shù)組的下標(biāo)找到這個新元素剧腻，然后對該元素進(jìn)行加1賦值。通過遍歷源數(shù)組對新數(shù)組進(jìn)行加1操作涂屁，一輪循環(huán)完书在，排序也就確定了，然后對新數(shù)組進(jìn)行遍歷只要發(fā)現(xiàn)值大于0的元素就打印它的下標(biāo)拆又，而打印的值就是我們想要的結(jié)果儒旬。
需要我們注意的是桶排序是有前提條件的必須要知道源數(shù)組中的最大元素才行，因為只有知道最大元素才能確定新數(shù)組的長度帖族。
桶排序的效率是非常高的栈源，但是如果源數(shù)組的值是不均勻的那么勢必會造成空間的浪費，桶排序就是典型的以空間換時間的最佳范例竖般。
package A數(shù)組.A003桶排序;
/**
* Description: <桶排序><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] arg) {
int[] arr = {1, 3, 10, 1, 34, 5, 21};
sortBucket(arr);
// int i = 0;
// while (i < arr.length) {
// System.out.println(arr[i]);
// i++;
// }
}
// 桶排序甚垦，聲明一個以 最大元素+1 為長度的數(shù)組，遍歷原數(shù)組涣雕，桶數(shù)組計數(shù)
private static void sortBucket(int[] arr) {
int[] arr1 = new int[34 + 1];
for (int i = 0; i < arr.length; i++) {
arr1[arr[i]]++;
}
for (int i = 0; i < arr1.length; i++) {
int count = arr1[i];
while (count > 0) {
System.out.println(i);
count--;
}
}
}
}
****2.5.4 數(shù)組中是否有重復(fù)元素****
說到元素重復(fù)我們自然會想到數(shù)組艰亮、集合，這兩種數(shù)據(jù)結(jié)構(gòu)都是允許重復(fù)數(shù)據(jù)的挣郭，而散列表是不允許有重復(fù)數(shù)據(jù)的垃杖。
我們想了如果我們遍歷數(shù)組中的元素，把這些元素存儲在散列表當(dāng)中將會何如丈屹？有的人會說去重復(fù)了调俘，是的沒有錯伶棒，但更重要的是我們在將數(shù)組的元素往散列表里面存入的時候加一個是否該元素在散列表中是否存在的判斷不就完了嗎？如果散列表中沒有耶就直接存儲了彩库，如果有也就直接返回了肤无，就這么簡單。
這一招需要我們對散列表的知識非常的了解骇钦，其實對于集合和散列表都有contains這個方法宛渐。
package A數(shù)組.A004數(shù)組是否有重復(fù)元素;
import java.util.HashSet;
/**
* Description: <數(shù)組是否有重復(fù)元素><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] arg) {
int[] arr = {11, 3, 10, 11, 34, 5, 21};
System.out.println(checkRepeat(arr));
}
// 查找一個數(shù)組里面有沒有重復(fù)元素
private static boolean checkRepeat(int[] arr) {
// 1.聲明一個散列表表
// 2.遍歷這個數(shù)組
// 3.對遍歷的元素依次進(jìn)行判斷，如果散列表里面沒有就往散列表里面塞眯搭，有就直接退出了
HashSet<Integer> hashSet = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
if (hashSet.contains(arr[i])) {
return true;
} else {
hashSet.add(arr[i]);
}
}
return false;
}
}
****2.5.5 刪除數(shù)組中的重復(fù)元素****
通過我們對上面判斷一個數(shù)組中是否有重復(fù)元素的分析秩伞，再做這個題就非常的簡單了道媚，直接用用一個散列表就ok了。
有沒有其他的解決方案？有沒有不借助其他的數(shù)據(jù)結(jié)構(gòu)直接就能實現(xiàn)的方案空入？有锁孟，其實方案的中心思想就是選擇排序有點像斤寂，就是取出當(dāng)前元素和其他剩余的元素進(jìn)行對比林螃，如果有相等的則將后面的所有元素往前移動一個位置，移動完畢在對源數(shù)組的長度進(jìn)行減1的壓縮處理借笙，壓縮完畢在從頭開始循環(huán)判斷扒怖。
這個方法就注意兩點，首先只要相等就把后面的所有元素往前移位业稼，然后移動完畢在對源數(shù)組長度進(jìn)行減1的壓縮處理盗痒，壓縮完畢重新開始循環(huán)。
package A數(shù)組.A005刪除數(shù)組重復(fù)元素;
import java.util.Arrays;
/**
* Description: <刪除數(shù)組重復(fù)元素><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAgorithm {
public static void main(String[] arg) {
int[] arr = {1, 3, 10, 1, 34, 5, 21};
arr = removeRepeat(arr);
int i = 0;
while (i < arr.length) {
System.out.println(arr[i]);
i++;
}
}
// 查找一個數(shù)組里面有沒有重復(fù)元素低散，如果有則刪除重復(fù)元素
private static int[] removeRepeat(int[] arr) {
// 取出第一個元素和剩余的其他元素進(jìn)行對比
// 一旦發(fā)現(xiàn)相等积糯，則后面的元素都往前移動一個，移動完畢數(shù)組
loop: for (int i = 0; i < arr.length; i++) {
for (int k = i + 1; k < arr.length; k++) {
// 如果相等則后面的元素同意往前移動
if (arr[i] == arr[k]) {
int head = k;
while (head < arr.length - 1) {
arr[head] = arr[head + 1];
head++;
}
// 對數(shù)組進(jìn)行壓縮處理
arr = Arrays.copyOf(arr, arr.length - 1);
i = 0;
// 壓縮完畢谦纱，重頭開始執(zhí)行
continue loop;
}
}
}
return arr;
}
}
****2.5.6 兩數(shù)求和****
說到兩數(shù)之和，那么就會想到數(shù)組中的任意兩個元素都會碰一下求和和我們的目標(biāo)數(shù)對比一下如果相等就把這兩個元素的下標(biāo)返回君编，這就把問題解決了跨嘉。
任意兩個元素都要碰一下，此時我們又想到了選擇排序吃嘿，通過這個算法我們就能實現(xiàn)兩兩相碰祠乃。兩個循環(huán)一個判斷就能問題解決。
還有另外一種算法兑燥，首先我們可以新建一個新的數(shù)據(jù)對象亮瓷，還對象有兩個字段，一個存下標(biāo)降瞳，一個存元素的值嘱支，接著通過源數(shù)組建立一個以新數(shù)據(jù)對象為元素的數(shù)組并對該數(shù)組進(jìn)行排序蚓胸，然后聲明兩個指針，一個頭指針除师，一個尾指針沛膳，這兩個指針分別從數(shù)組的頭和尾進(jìn)行前進(jìn)移動和回退移動，每移動一步求和汛聚，和目標(biāo)數(shù)進(jìn)行對比锹安，如果小于目標(biāo)數(shù)則頭指針往前移動，然后再求和對比倚舀，如果大于目標(biāo)數(shù)則尾指針回退移動再求和對比叹哭，直到相等就將兩個對象的下標(biāo)返回就解決問題了。
這兩種算法各有優(yōu)劣痕貌，方案1當(dāng)然代碼量最少是最簡單的风罩，方案2讓我們感受到了指針在運算中神奇作用，雖然代碼量有些大芯侥，但是思路還是很清晰的泊交。
package A數(shù)組.A006兩數(shù)求和;
import java.util.Arrays;
/**
* Description: <><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args) {
int[] arr = {1, 23, 12, 2, 11, 22};
int[] res = get(arr, 33);
System.out.println(Arrays.toString(res));
}
static class Data implements Comparable<Data>{
int index;
int data;
public Data(int index, int data) {
this.index = index;
this.data = data;
}
@Override
public int compareTo(Data o) {
return data - o.data;
}
@Override
public String toString() {
return "Data{" + "index=" + index + ", data=" + data + '}';
}
}
// 指定一個目標(biāo)數(shù)，查找其中兩個數(shù)之和等于目標(biāo)數(shù)的下標(biāo)
public static int[] get(int[] arr, int sum) {
int[] result = {0, 0};
// 1.首先對原數(shù)組排序
Data[] arr1 = new Data[arr.length];
int i = 0;
while( i < arr.length){
arr1[i] = new Data(i,arr[i]);
i++;
}
Arrays.sort(arr1);
System.out.println(Arrays.toString(arr1));
// 2.聲明兩個指針柱查，head廓俭，tail
int head = 0;
int tail = arr.length - 1;
while (head < tail) {
if ((arr1[head].data + arr1[tail].data) == sum) {
result[0] = arr1[head].index;
result[1] = arr1[tail].index;
return result;
} else if ((arr1[head].data + arr1[tail].data) < sum) {
head++;
} else {
tail--;
}
}
return null;
}
}
****2.5.7 求從左上到右下的路徑數(shù)****
這道題大意是這樣的，已知給定了一個m*n的二維數(shù)組唉工，以第一個元素作為開始點研乒，以最后一個元素作為結(jié)束點，然后開始點開始移動淋硝，并且只能往右往下移動直到到達(dá)結(jié)束點雹熬，求一共有多少條路徑數(shù)？
看到這道算法題想必有很多人都會懵圈谣膳，真是老虎吃天無從下手竿报，這背后到底有什么樣的邏輯關(guān)系？會用到哪些數(shù)據(jù)結(jié)構(gòu)继谚？用到什么樣的循環(huán)烈菌？用到什么樣的判斷？
其實具體的思路是這樣的花履，聲明一個m*n的二維數(shù)組芽世，初始化賦值都為0，接著給數(shù)組的第一行賦值為1诡壁，然后給數(shù)組的第一列賦值為1济瓢，最后一步給數(shù)組中剩余的其他所有元素賦值，其他元素的值為它正上方元素的值和它正左方元素的值之和妹卿，賦值完成之后最后一個元素arr[m-1][n-1]的值就是我們所要計算的路徑數(shù)旺矾，一臉懵逼蔑鹦，為什么？為什么通過這樣的賦值就是我們想要的計算結(jié)果路徑數(shù)宠漩？其實這就是算法中動態(tài)規(guī)劃的問題举反。
我們把第一行個第一列都賦值為1，為什么扒吁？火鼻，如果只有一行或只有一列這兩種情況都只有一條路，因此賦值為1沒毛病雕崩，這是合乎邏輯的魁索，然后我們開始移動，每走一步無外乎有兩種方案盼铁，要么往前走粗蔚，要么往下走，那么走到當(dāng)前格子就有兩種方案饶火，而這個值正是它正上方元素和正左方元素的和鹏控，那么同樣道理其他格子的值以此類推，而最后一個元素arr[m-1][n-1]的值就是我們所要計算的路徑數(shù)肤寝。
這就是動態(tài)規(guī)劃其中的奧妙之處当辐，通過三個循環(huán)簡簡單單的解決了我們的問題。
package A數(shù)組.A007左上到右下路徑數(shù);
/**
* Description: <在一個m*n的矩形方格中鲤看， 機(jī)器人在最左上的格子里缘揪，一次只能挪動一步，只能往右往下移動 目標(biāo)地點在最右下方的方格里义桂，問共有幾條路徑 ><br>
* Author: 門心叼龍<br>
* Date: 2018/11/23<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args) {
int path = getPath(3, 3);
System.out.println(path);
int[][] arr = new int[2][3];
System.out.println("length:"+arr.length);
}
// 動態(tài)規(guī)劃問題
public static int getPath(int m, int n) {
int[][] arr = new int[m][n];
// 將第一行都賦值為1
for (int i = 0; i < n; i++) {
arr[0][i] = 1;
}
// 將第一列都賦值為1
for (int i = 0; i < m; i++) {
arr[i][0] = 1;
}
// 給其他單元格賦值
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
}
}
return arr[m - 1][n - 1];
}
}
****2.5.8 求左上到右下的路徑最小值****
這個問題是上面求路徑數(shù)問題的擴(kuò)展找筝，求最小路徑數(shù)，不同的是現(xiàn)在還是一個m*n的二維數(shù)組慷吊，不過這個數(shù)組每個元素都已經(jīng)賦值了袖裕，讓你求路徑上所有元素的和的最小值，從左上到右下的路徑有n多條溉瓶，但是肯定有一條的和值是最小的急鳄。其實這還是一個動態(tài)規(guī)劃的問題。
具體解決思路如下嚷闭，首先聲明一個大小完全相同二維數(shù)組，現(xiàn)在要給其賦值赖临，賦值完畢我們要的結(jié)果也就出來了胞锰，第一個元素的值就是源數(shù)組第一個元素的值，第一行其他元素的值就是當(dāng)前元素的前導(dǎo)元素的值和源數(shù)組這個位置元素的值的和兢榨，第一列其他元素的值就是他的前導(dǎo)元素的值與源數(shù)組這個位置元素的值的和嗅榕，然后其他元素的值就是當(dāng)前元素上方元素和左方元素取最小值和源數(shù)組這個位置元素的值求和顺饮，其他元素得計算方式以此類推，直到賦值完成凌那，而最后一個元素的值就是我們要計算的左上到右下路徑的最小值兼雄。
通過分析我們不難發(fā)現(xiàn)，不管是求路徑數(shù)帽蝶，還是求路徑的最小值赦肋，其背后的核心思想都是動態(tài)規(guī)劃。通過對數(shù)組的動態(tài)的賦值計算励稳，從而得到我們要計算的結(jié)果佃乘。
package A數(shù)組.A008左上到右下路徑中的最小值;
/**
* Description: <在一個m*n的矩形方格中， 機(jī)器人在最左上的格子里驹尼，一次只能挪動一步趣避，只能往右往下移動 目標(biāo)地點在最右下方的方格里，問共有幾條路徑新翎，求路徑中的最小值><br>
* Author: 門心叼龍<br>
* Date: 2018/11/23<br>
* Version: V1.0.2<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args) {
int[][] grid = new int[][] {{1, 1, 8}, {3, 1, 4}, {6, 2, 1}};
int minvalue = getMinvalue(grid);
System.out.println(minvalue);
}
private static int getMinvalue(int[][] grid) {
int[][] result = new int[grid.length][grid[0].length];
// 給result[0][0]賦值
result[0][0] = grid[0][0];
// 給第一行賦值
for (int i = 1; i < result[0].length; i++) {
result[0][i] = result[0][i - 1] + grid[0][i];
}
// 給第一列賦值
for (int i = 1; i < result.length; i++) {
result[i][0] = result[i - 1][0] + grid[i][0];
}
// 給其他元素賦值
for (int i = 1; i < result.length; i++) {
for (int j = 1; j < result[0].length; j++) {
result[i][j] = Math.min(result[i - 1][j], result[i][j - 1]) + grid[i][j];
}
}
return result[result.length - 1][result[0].length - 1];
}
}
****3. 集合****
****3.1 概念****
大家知道數(shù)據(jù)的致命缺點就是長度固定程帕，如果我們要存儲的數(shù)據(jù)長度不固定，該怎么辦地啰？這時候就要用集合了愁拭，其實集合也是基于數(shù)組實現(xiàn)的，不過它是一個變長數(shù)組髓绽，想放入多少就可以放入多少敛苇。集合就是一個變長數(shù)組或者叫做動態(tài)數(shù)組。
****3.2 特點****
1.它的長度是可變的
2.他會浪費一定內(nèi)存空間
3.數(shù)據(jù)的拷貝會浪費一定的時間
****3.3 適用場景****
集合的適用場景非常多顺呕，如果博客的文章列表枫攀、評論列表等，只要有列表就有集合的身影株茶。
?
****3.4 常見的算法****
****3.4.1 自定義實現(xiàn)一個集合****
集合我們知道他是一個變長數(shù)組来涨，只有變長才能源源不斷的往里面存放數(shù)據(jù)，通過集合元素添加流程圖我們也能看到启盛，首先需要初始化一個數(shù)組蹦掐，然后在添加元素的時候如果源數(shù)組滿了就需要擴(kuò)容了，當(dāng)然擴(kuò)容的系數(shù)有的是2倍僵闯，有的是0.75倍卧抗，這由自己定，不管是數(shù)組的擴(kuò)容還是壓縮都用到了數(shù)組工具類中非常重要的一個方法Arrays.copy(),有了添加的方法鳖粟，必然少不了刪除方法社裆，刪除的思路也很簡單，就是把要刪除的元素之后的元素都往回移動一位向图，然后再把最后一個元素賦值為0再退出循環(huán)就ok了泳秀。
現(xiàn)在我們不妨畫個流程圖方便大家理解集合的工作原理：
?
代碼實現(xiàn)如下：
package B集合.A001自定義實現(xiàn)一個ArrayList;
import java.util.Arrays;
/**
* Description: <自定義實現(xiàn)一個ArrayList><br>
* Author: 門心叼龍<br>
* Date: 2018/11/19<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MyArrayList {
private int[] arr;
private int initsize = 5;
private int size = 0;
public MyArrayList() {
arr = new int[initsize];
}
public int get(int index) {
return arr[index];
}
public boolean add(int value) {
// 說明此時數(shù)組已經(jīng)滿了标沪，要擴(kuò)容了
if (size == arr.length) {
System.out.println("數(shù)組要擴(kuò)容了...");
arr = Arrays.copyOf(arr, size * 2);
}
arr[size++] = value;
return true;
}
public boolean remove(int value) {
if (arr.length > 0) {
loop: for (int i = 0; i < arr.length; i++) {
if (arr[i] == value) {
int temp = i;
while (temp < arr.length - 1) {
arr[temp] = arr[temp + 1];
temp++;
}
arr[--size] = 0;
break loop;
}
}
}
return true;
}
public int size() {
return size;
}
}
****3.4.2 刪除集合中的偶數(shù)****
很多初學(xué)者看到這個問題都覺的太簡單了，不就一個循環(huán)就解決問題了嗎嗜傅？其實這是有大問題的金句，問什么？你想了循環(huán)開始的時候循環(huán)結(jié)束的條件就已經(jīng)確定了吕嘀，如果你在循環(huán)的過程中刪除了一個元素违寞，那么數(shù)組長度就變短了，而我們循環(huán)并沒有停止币他，當(dāng)循環(huán)走到最后的時候勢必會造成數(shù)組下標(biāo)越界的空指針異常坞靶，怎么辦？其實我們通過集合迭代器來做這個刪除的工作就可以完美的規(guī)避這個問題蝴悉。因為迭代器不需要下標(biāo)彰阴，也就不存在數(shù)組下標(biāo)越界的問題。
package B集合.A002刪除集合中的偶數(shù);
import java.util.ArrayList;
import java.util.Iterator;
/**
* Description: <刪除集合中的偶數(shù)><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] arg) {
ArrayList<Integer> list = new ArrayList() {
{
add(1);
add(2);
add(3);
add(4);
}
};
removeEvenNumber(list);
int i = 0;
while (i < list.size()) {
System.out.println(list.get(i));
i++;
}
}
// 刪除集合中的偶數(shù)元素
private static void removeEvenNumber(ArrayList<Integer> myArrayList) {
Iterator<Integer> iterator = myArrayList.iterator();
while (iterator.hasNext()) {
Integer next = iterator.next();
if (next % 2 == 0) {
iterator.remove();
}
}
}
}
****3.5 性能分析****
在算法中拍冠，每種算法的性能指標(biāo)一般都有兩個尿这，即時間復(fù)雜度和空間復(fù)雜度。
時間復(fù)雜度：它定量的描述了該算法的運行時間庆杜。常常用大寫的O表示射众。
空間復(fù)雜度：是對一個算法在運行過程中臨時占用的存儲空間大小的度量。
雖然集合這個變長數(shù)組比普通的數(shù)組高級一些晃财，但是本質(zhì)上它還是基于數(shù)組實現(xiàn)的叨橱，所以它和數(shù)組的性能差不多。
對于數(shù)組的操作断盛，并不像我們看到的那么直觀罗洗，計算機(jī)需要根據(jù)我們具體操作的位置，從頭到尾一個一個地尋找到指定的位置钢猛，所以我們在數(shù)組中增加元素伙菜、修改元素、獲取元素等操作的時間復(fù)雜度都為O(n)命迈。
變長數(shù)據(jù)也有性能損耗的問題贩绕，如果插入的元素發(fā)現(xiàn)其中固定的數(shù)組的長度不夠，則需要建立一個新的更長的數(shù)組壶愤，還要拷貝元素到新的數(shù)組淑倾，這都會造成性能損耗。
****4. 散列表****
****4.1 概念****
前面我們講了數(shù)組和集合征椒，他們都有一個共同的特點娇哆，他們在內(nèi)存中的存儲順序是有序的，如果數(shù)據(jù)量很大我們需要在數(shù)組或者集合中查找一個元素，或者在數(shù)組或集合的頭部添加或者刪除一個元素迂尝，它的性能就會大大降低。
此時散列表就應(yīng)運而生了剪芥，散列表是一種以空間換時間的數(shù)據(jù)結(jié)構(gòu)垄开。
讓我們想一下，若在手機(jī)的通信錄中查找一個人税肪，那我們應(yīng)該不會從第1個人一直的查找下去溉躲，因為這樣實在是太慢了。我們其實是這樣做的：首先看這個人的名字的首字母是什么益兄，比如姓趙锻梳，那么我們會點擊字母z，列表里以字母z開始的人名都會迅速的查找出來净捅，就很快的查找到我們要查找的那個人疑枯。
還有我們在查字典的時候，需要查找一個單詞蛔六，肯定不會從頭翻到尾荆永，而是通過這字的首字母，查找到對應(yīng)的那一頁国章，這樣可以速度的跳到那個字所在的頁面具钥。
其實這里就用到了散列表的思想。
散列表又叫哈希表液兽，能通過給定的關(guān)鍵字的值直接訪問到具體對應(yīng)的值的一個數(shù)據(jù)結(jié)構(gòu)骂删。也就是說，通過關(guān)鍵字映射到一個表中的位置來直接訪問記錄四啰，以加速訪問的速度宁玫。
而這個關(guān)鍵字就是我通常所說的key，把對應(yīng)的記錄稱為value拟逮，所以可以說也是通過這個key訪問一個映射表來得到value的值撬统，而這個映射表就是所說的散列表，也叫哈希表敦迄。
****4.2 哈希算法****
剛才我們說到恋追，通過關(guān)鍵字映射到一個表中的位置來直接訪問記錄，這個映射到表中的位置就是通過哈希算法來實現(xiàn)的罚屋，目前這個哈希算法的實現(xiàn)的方法比較多苦囱，主要有以下一種：
1.直接尋址法
2.數(shù)字分析法
3.平方取中法
4.隨機(jī)數(shù)法
5.除留取余法
****4.3 哈希沖突****
會有這樣一種情況，有多個不同的Key通過哈希函數(shù)可能會得到相同的地址脾猛，這樣就會造成對數(shù)據(jù)的覆蓋撕彤、丟失。那么解決哈希沖突的處理方式也有很多種，主要有以下幾種方法：
1.開放地址法
2.再哈希法
3.鏈接地址法
****4.4 存儲結(jié)構(gòu)****
一個好的散列表設(shè)計羹铅，除了需要選擇一個性能較好的哈希函數(shù)蚀狰，還要選擇一個好的沖突解決方式。這里我們選擇除留取余法作為哈希算法职员，選擇鏈接地址法作為沖突的處理方式麻蹋。
?
****4.5 特點****
散列表有兩種用法，一種是key的值和Value的值一樣焊切，一般我們稱這種數(shù)據(jù)結(jié)構(gòu)為Set集合扮授；如果Key的值和Value的值不一樣，我們稱這種情況為Map专肪。
1.增啥改查的速度都很快
2.無序
****4.6 適用場景****
1.數(shù)據(jù)緩存
2.快速查找
****4.7 性能分析****
散列表的訪問刹勃，如果沒有碰撞，那么我們完全可以認(rèn)為對元素的訪問的時間復(fù)雜度為O(1)
但是實際上不可能沒有碰撞嚎尤，Java中使用鏈表來解決荔仁，而碰撞之后的訪問需要遍歷鏈表，所以時間的復(fù)雜度將變?yōu)镺(L),其中L為鏈表的長度芽死。
****5. 小結(jié)****
數(shù)組咕晋，作為數(shù)據(jù)結(jié)構(gòu)中最為基礎(chǔ)的、常用的一個結(jié)構(gòu)收奔。而集合與散列表他們都是在數(shù)組的基礎(chǔ)上進(jìn)行稍微高級點的擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)掌呜，通過對比這三種數(shù)據(jù)結(jié)構(gòu)，我們更加清楚他們之間的區(qū)別和應(yīng)用場景了坪哄，對數(shù)組的應(yīng)用有了更加深入的理解质蕉。
源碼下載地址：https://download.csdn.net/download/geduo_83/10913510
初級篇：Java數(shù)據(jù)結(jié)構(gòu)與算法初級篇之?dāng)?shù)組、集合和散列表
中級篇：Java數(shù)據(jù)結(jié)構(gòu)與算法中級篇之棧翩肌、隊列模暗、鏈表
高級篇：Java數(shù)據(jù)結(jié)構(gòu)與算法高級篇之樹、圖
理論篇：Java數(shù)組念祭、集合兑宇、散列表常見算法淺析
理論篇：Java棧、隊列粱坤、鏈表常見算法淺析
理論篇：Java樹隶糕、圖常見算法淺析
問題反饋
有任何問題，請在文章下方留言站玄。
關(guān)于作者
var geduo_83 = {
nickName : "門心叼龍",
site : "http://www.weibo.com/geduo83"
}
