（最近剛來到簡書平臺，以前在CSDN上寫的一些東西，也在逐漸的移到這兒來，有些篇幅是很早的時候?qū)懴碌?，因此可能會看到一些?nèi)容雜亂的文章，對此深感抱歉，以下為正文）
引子
眾所周知，數(shù)據(jù)結(jié)構(gòu)和算法對于一個開發(fā)人員是多么的重要，一個好的數(shù)據(jù)結(jié)構(gòu)和算法，可以讓你在實現(xiàn)同一個功能的時候，提升非常多的效率。筆者作為一個初入IT業(yè)的菜鳥，覺得也很有必要在這方面下一番功夫，所以特開此篇作為學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的開篇，后面會繼續(xù)記錄分享我的學(xué)習(xí)經(jīng)歷。
因為筆者主要做Java這塊兒的工作，所以前期寫的東西大多都是以Java作為基礎(chǔ)語言來進行描述的，不過數(shù)據(jù)結(jié)構(gòu)和算法這種東西，其實跟語言的關(guān)聯(lián)性不是特別大。想學(xué)習(xí)算法，那么必須對數(shù)據(jù)結(jié)構(gòu)有一定的了解，一些好的算法難免要結(jié)合一些數(shù)據(jù)結(jié)構(gòu)的知識來實現(xiàn)。本篇講述的是最基礎(chǔ)最簡單的數(shù)據(jù)結(jié)構(gòu)(數(shù)組，集合和散列表)，盡管它們很基礎(chǔ)，但我們?nèi)孕枰煤玫娜チ私馑鼈儭?/p>
正文
數(shù)組
數(shù)組是數(shù)據(jù)結(jié)構(gòu)中最為基礎(chǔ)的一個結(jié)構(gòu)，是我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的基石，事實上大部分的數(shù)據(jù)結(jié)構(gòu)都可以用數(shù)組來進行實現(xiàn)。就像在前面Java IO筆記的篇幅中，我們可以經(jīng)常在源碼中看到數(shù)組的存在，靈活的運用它們可以為我們解決很多事情。
那么數(shù)組是什么呢，在我看來數(shù)組就是有限個數(shù)的同類型數(shù)據(jù)，按照順序排列，組合在一起的一個有序集合。當(dāng)然在一些弱語言中，數(shù)組對內(nèi)部元素的數(shù)據(jù)類型沒有強制要求，如JavaScript中我們可以使用var來聲明變量而不用指定數(shù)據(jù)類的類型，但在Java中，數(shù)組要求數(shù)據(jù)元素必須是同一種類型。數(shù)組可以分為一維數(shù)組和多維數(shù)組，事實上多維數(shù)組就是一維數(shù)組的擴展，就是一維數(shù)組中的元素還是數(shù)組，如是而已。
數(shù)組有一個最為明顯的特征，那就是它是定長的，在使用前我們需要先行明確它需要在內(nèi)存中開辟出多大的空間，如果開辟的空間過小，那么我們無法將所需要的數(shù)據(jù)完整的存儲到數(shù)組之中，如果我們開辟的過大，那么除了裝載我們所需的數(shù)據(jù)之外，其它的空間將會被浪費掉。所以我們在使用數(shù)組的過程中必須要結(jié)合使用的場景謹(jǐn)慎使用，合理初始化。下面將結(jié)合一些Java的代碼以及圖示來簡單地描述數(shù)組的使用。
在Java中，數(shù)組（一維）的創(chuàng)建方式如下，筆者為了方便，之后的實例中都將以int類型數(shù)組作為描述對象：
public class Test {
@org.junit.Test
public void initArray() {
// 該種方法先聲明數(shù)組，然后為其賦值
int[] array1 = new int[5];
for (int i = 0; i < array1.length; i++) {
array1[i] = i + 1;
}
System.out.print("先聲明后賦值： ");
printArray(array1);
// 該種方法在聲明的同時就為其賦值
int[] array2 = new int[] { 1, 2, 3, 4, 5 };
System.out.print("聲明同時直接賦值：");
printArray(array2);
}
private void printArray(int[] arrays) {
for (int temp : arrays) {
System.out.print(temp + " ");
}
System.out.println();
}
}
執(zhí)行上述代碼后可以在控制臺看到如下打?。?/p>
上面展示的示例代碼演示了在Java中創(chuàng)建數(shù)組的過程。第一種是先聲明再賦值，執(zhí)行時，會先在內(nèi)存中開辟出指定的空間，此時數(shù)組中沒有賦值，JVM會自動為其在內(nèi)存中賦上默認(rèn)初始值，初始值根據(jù)數(shù)組類型來分配，在Java中，引用型數(shù)據(jù)類型默認(rèn)初始為null，基本數(shù)據(jù)類型的默認(rèn)初始值如下圖所示：
之后再將需要存儲的值放入開辟好的空間之中，下面筆者將通過畫圖的方式更形象地來描述這個過程。
如上圖所示，我截取了initArray方法中的一部分代碼并畫圖分析。程序運行，首先JVM會將Test.class文件加載到方法區(qū)中，本例中，首先被壓入棧內(nèi)存的是initArray方法，方法中定義了一個局部變量array1，該變量是個int類型數(shù)組，初始化時，采用了先開辟空間后賦值的方式，因此當(dāng)執(zhí)行完第一條語句后，JVM會在堆空間中開辟出一個可以容納5個int型數(shù)據(jù)的空間，此時數(shù)組空間中因為沒有指定初始化值，JVM會自動向內(nèi)填充初始值，賦值規(guī)則在上面已經(jīng)提到過，不同類型數(shù)據(jù)的默認(rèn)初始值是不同的，本例中，因為使用的是int型數(shù)組，所以默認(rèn)的初始值為0，然后array1變量便指向了這片內(nèi)存。之后通過一個for循環(huán)為數(shù)組重新賦值，堆空間中使用新的值替換掉之前的默認(rèn)值，接著執(zhí)行printArray方法，該方法進棧，因為我們是將array1變量作為參數(shù)傳入了該方法，所以該方法中的arrays參數(shù)也是指向著array1所在的這片內(nèi)存，然后方法內(nèi)通過一個循環(huán)遍歷了該數(shù)組中的元素，并將它們打印了出來。
采用第二種方式其實在本質(zhì)上跟第一種方式?jīng)]有區(qū)別，都會經(jīng)歷默認(rèn)初始化值這一步，只是給人的感官上是省略了默認(rèn)初始化這一步。通過上面的描述，對數(shù)組有了初步的認(rèn)識，我們知道了數(shù)組擁有著定長的特性，除了定長的特性，數(shù)組還有著順序訪問的特性，盡管在編程中我們可以使用索引來獲取數(shù)組中指定位置的值，但計算機在執(zhí)行時，其實還是一個一個的按順序訪問的，直到訪問到指定索引的位置。
因為數(shù)組的特性，所以數(shù)組的適用場景主要是那些業(yè)務(wù)不會出現(xiàn)變化的場景。筆者曾經(jīng)寫過一個小的象棋游戲，當(dāng)時的棋盤就是用二維數(shù)組來表示的，因為棋盤上可以落子的位置個數(shù)是固定的，正好符合數(shù)組的特性。盡管數(shù)組的作用很強大，但也有這其劣勢，因為定長的特性，導(dǎo)致如果業(yè)務(wù)出現(xiàn)變化時，需要重新改變程序，所以下面就來說說數(shù)組的延伸運用。
動態(tài)數(shù)組
正如前面所說，數(shù)組雖然比較高效，但是因為其定長的特性導(dǎo)致了其應(yīng)用場景的局限性。神說要有光，于是便有了光，因為有著需求，所以有了創(chuàng)新。為了解決數(shù)組定長的問題，集合這類數(shù)據(jù)結(jié)構(gòu)誕生了，因為集合的概念比較寬泛，所以暫且將其理解為一個用于存儲元素的容器，并且其是變長的。
集合的出現(xiàn)，解決了數(shù)組因為定長特性而不能解決的應(yīng)用場景。集合跟數(shù)組一樣也有著其一些屬于自己的特性：
- 集合的容量是非固定的。當(dāng)集合的當(dāng)前容量不足以裝載新的元素時，它會自動擴展容量以裝納新的元素。這點是跟數(shù)組最明顯的區(qū)別。
- 集合中存放的為引用性數(shù)據(jù)類型，因為自動裝箱拆箱的原因，也可以存放基本數(shù)據(jù)類型，但本質(zhì)上在存儲時基本數(shù)據(jù)類型已經(jīng)自動裝箱為其對應(yīng)的引用型數(shù)據(jù)類型進行存儲。
- 集合在不適用泛型約束的時候，一個集合中是可以存放多種類型的數(shù)據(jù)的。數(shù)組只能存放單一類型數(shù)據(jù)。
集合是一種比較寬泛的定義，為了解決各種不同的需求，它可以細(xì)化成很多獨有的數(shù)據(jù)結(jié)構(gòu)：
- 列表：列表是集合的一種，它是一種順序結(jié)構(gòu)，常見的有鏈表、隊列、棧等。
- 集：集也是集合的一種，它是一種無序的結(jié)構(gòu)，并且其中的存儲的元素是不能重復(fù)的。
- 多重集：多重集也是集合的一種，一般來說它也是無序的，但相較集而言，它是可以存儲重復(fù)的值的。
- 關(guān)聯(lián)數(shù)組：關(guān)聯(lián)數(shù)組同樣也是集合的一種，它也是無需的，但它多了一種鍵-值的概念，通過鍵可以獲得值。
- 樹、圖等等。
在Java中，其已經(jīng)為我們內(nèi)置了很多常用的集合結(jié)構(gòu)，它們都位于java.util包下，在之后的學(xué)習(xí)中將會對其進行進一步的了解。
本節(jié)的標(biāo)題是動態(tài)數(shù)組也可以叫其動態(tài)列表。其實集合這類結(jié)構(gòu)大多數(shù)都可以通過數(shù)組來實現(xiàn)的，如果讀者有過c語言的基礎(chǔ)，對此看法肯定會表示一定的贊同。下面將展示如何基于數(shù)組去建立一個動態(tài)數(shù)組。
在開始動手之前，我們可以進行簡單的分析。我們之所以想構(gòu)建動態(tài)數(shù)組的原因僅僅只是因為數(shù)組定長的特性。那么如何解決這個問題呢，好比正常生活中我們現(xiàn)在使用著一部內(nèi)存16g的手機，隨著我們使用時間的增長，發(fā)現(xiàn)手機內(nèi)存不足以滿足我們的需求，這時你會怎么做呢？刪掉一些東西繼續(xù)使用？這個方法只是臨時的緩解當(dāng)前的困境，隨著時間的增長，仍然會發(fā)生一樣的問題。大部分的人應(yīng)該會直接購買一個內(nèi)存容量更大的手機，當(dāng)然你還會把原來手機上重要的數(shù)據(jù)拷貝到新手機之上。
說到這里，我們是不是也找到了問題的解決辦法了呢。因為數(shù)組定長的特性，當(dāng)我們遇到所要裝載數(shù)據(jù)量大于其數(shù)組空間的時候，我們完全可以創(chuàng)建一個容量足夠大的數(shù)組用以裝載數(shù)據(jù)，同時將原數(shù)組的數(shù)據(jù)拷貝過來就行了。動態(tài)數(shù)組便是基于這個原理實現(xiàn)的。下面可以通過一副簡單的流程圖來描述動態(tài)數(shù)組的工作流程。
了解了工作原理之后，接下來就是動手開始擼碼了，我們對于該變長數(shù)組的實現(xiàn)，可以參考Java中為我們提功的ArrayList類，該類是Java為我們封裝好的集合類之一。下面貼上利用數(shù)組簡單實現(xiàn)動態(tài)列表的代碼：
package Arraylist;
import java.util.Arrays;
public class MyArrayList{
//定義了一個常量值，表示內(nèi)置數(shù)組的初始長度為10
private static final int INITIAL_SIZE = 10;
//該變量用于表示內(nèi)置數(shù)組中實際使用的數(shù)量
private int size = 0;
//定義了一個Object類型數(shù)組，用于存儲元素
private Object[] data;
/**
* 一個無參構(gòu)造函數(shù)，為內(nèi)置數(shù)組進行初始化，初始化容量為默認(rèn)的初始值10
*/
public MyArrayList(){
data = new Object[INITIAL_SIZE];
}
/**
* 一個帶一個參數(shù)的構(gòu)造函數(shù)
* @param initial 默認(rèn)的列表初始化容量
*/
public MyArrayList(int initial){
if(initial <= 0){
throw new IllegalArgumentException("輸入的容量初始值必須大于0");
}
data = new Object[initial];
}
/**
* 該方法用于向動態(tài)列表中插入數(shù)據(jù)
* @param obj 插入的元素
*/
public void add(Object obj){
if(size == data.length){
data = Arrays.copyOf(data, size*2);
System.out.println("內(nèi)置數(shù)組自動擴容1倍");
}
data[size++] = obj;
}
/**
* 該方法用于獲取指定索引處的元素值
* @param index 指定的索引值
* @return
*/
public Object get(int index){
if(index < 0){
throw new IllegalArgumentException("傳入的索引值必須大于0");
}else if(index >= size){
throw new IndexOutOfBoundsException("傳入的參數(shù)值大于了內(nèi)置數(shù)組的最大長度");
}
return data[index];
}
/**
* 設(shè)置指定位置的元素值
* @param index
* @param obj
*/
public void set(int index,Object obj){
data[index] = obj;
}
/**
* 獲得當(dāng)前動態(tài)列表中存入數(shù)據(jù)的長度
* @return
*/
public int size(){
return size;
}
/**
* 獲得當(dāng)前動態(tài)列表中內(nèi)置數(shù)組的容量
* @return
*/
public int length(){
return data.length;
}
public static void main(String[] args) {
MyArrayList list = new MyArrayList();
System.out.println("初始化時動態(tài)列表中存儲的元素為"+list.size());
System.out.println("初始化時動態(tài)列表中的容量大小為"+list.length());
for(int i = 0; i < 11; i++){
list.add(i);
}
System.out.println("賦值后動態(tài)列表中存儲的元素為"+list.size());
System.out.println("賦值后動態(tài)列表中的容量大小為"+list.length());
System.out.print("列表中的元素為：");
for(int i = 0; i < list.size(); i++){
System.out.print(list.get(i)+"\t");
}
}
}
執(zhí)行上述代碼，可以在控制臺看到如下打?。?/p>
從控制臺的打印中可以看出，我們創(chuàng)建的動態(tài)列表成功的將數(shù)據(jù)存儲了起來，并且當(dāng)自身空間不夠使用的時候，自動進行了擴容的操作。盡管這個動態(tài)列表是基于數(shù)組創(chuàng)建的，內(nèi)置的數(shù)組仍然保有定長的特性，但在外部使用時，完全感受不到其定長的特性，擴容的操作已經(jīng)在內(nèi)部便消化了。
在上面的代碼中，最關(guān)鍵的擴容步驟中，筆者使用了一個工具類方法Arrays.copyOf方法，該方法的內(nèi)部其實是調(diào)用了System.arraycopy方法，該方法是一個native方法，執(zhí)行效率非常高，遠(yuǎn)比我們使用循環(huán)賦值的方式來拷貝舊數(shù)據(jù)要效率的多。
因為此動態(tài)數(shù)組的實現(xiàn)是基于數(shù)組的，所以它的執(zhí)行效率相對數(shù)組而言也沒有什么提升，只是解決了定長的問題。并且在擴容和拷貝舊數(shù)據(jù)的時候甚至還會增加系統(tǒng)的開銷，所以在使用時也要根據(jù)實際場景來判斷如何使用，定義一個合理的初始化容量，以及一個合理的擴容倍數(shù)都可以提升該結(jié)構(gòu)在實際場景中應(yīng)用的效率。
散列表
前面提到了集合，并且建立了一個動態(tài)數(shù)組來擺脫數(shù)組定長的約束，但它在使用時，仍然有一些限制。因為動態(tài)數(shù)組其本身仍然是順序存儲的，所以當(dāng)我們要查詢其中的某個元素時，我們需要順序地遍歷其中的每個元素，直到找到了要指定的元素。當(dāng)動態(tài)數(shù)組中元素總量很大，并且我們所要查找的元素在動態(tài)數(shù)組中的位置相對靠后時，此時的查詢效率是比較慢的。所以散列表就這么應(yīng)運而生了，散列表同樣是集合中的一種，它是一種使用空間去置換時間的存儲結(jié)構(gòu)。正所謂魚和熊證二者不可兼得，在我們使用的過程中，我們要根據(jù)實際的情況去選用合適的數(shù)據(jù)結(jié)構(gòu)，如果只是因為看到散列表的效率比較高并且其又能解決數(shù)組定長的問題就一昧的去使用它，那么你會發(fā)現(xiàn)占用過多的存儲空間也是一件令人頭疼的事情。
上面描述了這么多，并沒能描述出散列表到底是什么，實在是罪過罪過，小生在這兒給各位大俠賠禮了。
舉個生活中的小例子來描述一樣吧。查字典，這個經(jīng)典的動作就可以很好地對其進行詮釋。當(dāng)我們查字典時，如果使用動態(tài)數(shù)組的方式去查詢的話，那么意味著我們需要從第一頁一頁一頁的不停往后翻，直到我們查到了想要查找到的字。可以想象一下，如果我們所要查詢的字在字典的最后一頁上，那意味著我們需要將整本字典都翻上一遍。如果我們使用散列表，那么我們的操作流程如下，我們會先通過字典的索引表上找到我們要查找的字所在的頁數(shù)，然后通過查詢到的頁數(shù)，便可以直接翻至我們所要查找的字所在的頁，事實上，我們在生活中也確實是使用這種方式來查詢字典的。
通過上面的描述，此時對散列表也就有了一些初步的了解。散列表也叫做哈希表，它能通過給定的關(guān)鍵字直接訪問到具體的值 ，即可以把關(guān)鍵字映射到某一個表中位置上來直接訪問記錄。這樣的操作方式大大加快了訪問的速度。
一般上述的關(guān)鍵字我們稱其key，將其對應(yīng)的值稱為value。我們可以通過key值通過映射表直接訪問到對應(yīng)的value值。這里的映射表一般稱作散列函數(shù)或者哈希函數(shù)。而存儲數(shù)據(jù)的數(shù)組稱其散列表。
使用散列表時，我們通過一個key值，必定能訪問到一個唯一的value地址，理想狀態(tài)下，key值和value地址值是一一對應(yīng)的，但實際情況下，不同的key值經(jīng)散列函數(shù)計算之后可能會指向同一個value地址，這便發(fā)生了碰撞，在下面的篇幅中，會講述一些解決碰撞問題的方法。
散列函數(shù)在散列表中起到了至關(guān)重要的作用，一個好的散列函數(shù)，可以極大程度的提高散列表的效率。下面就來介紹一些簡單的散列函數(shù)：
- 直接尋址法
直接尋址法是直接取關(guān)鍵字或者關(guān)鍵字的某個線性函數(shù)作為散列地址。即address = key 或者 address = a*key+b。 - 數(shù)字分析法
數(shù)字分析法是指通過對數(shù)據(jù)進行分析，找出數(shù)據(jù)中沖突比較少的部分作為散列地址，即取關(guān)鍵字中的部分位作為散列地址，該種方法一般是在散列表中的關(guān)鍵字事先知道的情況下可以選擇的一種方式。比如學(xué)校中學(xué)生的學(xué)號，學(xué)生的學(xué)號一般包含入學(xué)年份，所修系的編號，所修專業(yè)的編號，班級號，班級中的編號等，我們可以剔除入學(xué)年份，系編號這種存在大可能性雷同的數(shù)據(jù)字段，采用后面剩余的字段來作為散列地址。 - 平方取中法
平方取中法是指當(dāng)我們無法確定關(guān)鍵字中哪幾位的分布相對比較均勻時，可以先求出關(guān)鍵字的平方值，然后取平方值的中間幾位作為散列地址。因為計算平方之后的中間幾位基本和關(guān)鍵字中的每一位值都息息相關(guān)，這樣可以使得散列地址的分配是隨機的，至于是取中間幾位作為散列地址，這個主要看表的長度來決定的。 - 取隨機數(shù)法
使用隨機數(shù)算法為關(guān)鍵字分配散列地址。 - 除留取余法
除留取余法是指取關(guān)鍵字被某個不大于散列表表長m的數(shù)n除后所得的余數(shù)p來作為散列地址。該種方法可以再使用了上述其它方法后再次使用。該種方式對數(shù)n的要求比較高，一般取素數(shù)或者直接使用表長m，若選擇不好，則很容易產(chǎn)生碰撞。
上述的5種散列函數(shù)是比較基礎(chǔ)易懂的。事實上你完全可以自己設(shè)計出屬于自己的散列函數(shù)，當(dāng)然你得參考一些關(guān)鍵因素：關(guān)鍵字的長度，哈希表的大小，關(guān)鍵字的分布狀況，記錄的查找頻率等等。
前面有提到過，當(dāng)我們向散列表中裝載數(shù)據(jù)時，同一個關(guān)鍵字key值經(jīng)過散列函數(shù)的計算過后，可能會分配至同一個地址空間，從而產(chǎn)生了碰撞，在這種情況下，我們就可能會覆蓋掉原有的數(shù)據(jù)，從而造成了數(shù)據(jù)丟失，這是萬萬無法接受的。既然發(fā)現(xiàn)了問題，那我們自然要去解決問題。下面就簡單介紹幾種常見的解決沖突的方法：
- 開放尋址法
開放尋址法就是當(dāng)關(guān)鍵字經(jīng)過散列函數(shù)計算獲取到一個地址后，首先會判斷當(dāng)前地址是否已經(jīng)被使用了，如果當(dāng)前地址沒有被使用，那么便將需要存儲的數(shù)據(jù)放入該地址下，如果發(fā)現(xiàn)當(dāng)前地址已經(jīng)被使用了，那么需要對該地址進行探索再哈希。比如向后移動一個地址，直到找到未被占用的地址，然后將要存儲的數(shù)據(jù)放入其中。其中探索再哈希這個過程可以通過一些算法來增加我們的效率，該方面有機會的話再其它的篇幅中描述。開放尋址法與后面的鏈地址法是相對應(yīng)的，開放尋址法是將所有的元素都存放在散列表中，而不像鏈地址法通過加入鏈表結(jié)構(gòu)來解決沖突。 - 鏈地址法
鏈地址法就是當(dāng)產(chǎn)生沖突時，同一個地址放置需要裝載多個數(shù)據(jù)的時候，多個數(shù)據(jù)采用鏈表的形式裝載進指定的地址之中，該種方法在很多高級語言中均有實現(xiàn)，之后代碼演示的自定義的散列表中解決沖突的方式便是采用這種方式的。 - 創(chuàng)建一個公共溢出區(qū)
該種方式就是單獨創(chuàng)建一個公共溢出區(qū)，當(dāng)?shù)刂反嬖跊_突后，將新的地址放到公共溢出區(qū)里。
理想狀態(tài)下，散列表的搜索時間復(fù)雜度為O(1)，影響該時間復(fù)雜度的主要原因就是是否產(chǎn)生沖突。因此影響散列表效率的主要因素就是是否有一個好的散列函數(shù)，是否一個好的沖突解決方法，以及是散列表的填裝因子（即散列表中元素個數(shù)與表長的商），填裝因子越小越好，當(dāng)填裝因子過大時發(fā)生沖突的可能性就越大，在java中，填裝因子為0.75。
散列表一般在平常的使用當(dāng)中可以用于做消息緩存，比如可以先將數(shù)據(jù)庫或服務(wù)器上常用的數(shù)據(jù)，以散列表的形式緩存到本地，這樣便可以提高程序的運行效率，散列表還可以用于一些需要快速查找的場景之中，畢竟散列表這種結(jié)構(gòu)相較其它的數(shù)據(jù)結(jié)構(gòu)來看，其查找，插入，刪除等一般操作的時間復(fù)雜度僅為O(1)，效率還是要快于其它的。
下面就是使用java代碼簡單實現(xiàn)的一個自定義的散列表。其散列函數(shù)采用了除留取余法，解決沖突的方法采用了鏈地址法。
package HashTable;
//該類作為鏈表中的元素類
public class Entry {
int key;
int value;
Entry next;
public Entry(int key, int value, Entry next){
super();
this.key = key;
this.value = value;
this.next = next;
}
@Override
public String toString() {
return "[key="+key+",value="+value+",next="+next+"]";
}
}
package HashTable;
public class HashTable {
public static void main(String[] args) {
HashTable hashtable = new HashTable();
hashtable.put(1, 1);
hashtable.put(5, 2);
hashtable.put(2, 3);
System.out.println(hashtable.hash(1));
System.out.println(table[1]);
System.out.println(hashtable.size());
System.out.println(hashtable.getLength());
System.out.println(hashtable.getUse());
}
// 默認(rèn)散列表的初始化長度
private static final int DEFAULT_INITIAL_CAPACITY = 4;
// 擴充因子，如果散列表內(nèi)元素數(shù)量占總?cè)萘康谋壤_到這個標(biāo)準(zhǔn)，那么在之后的操作中將會自動擴容
private static final float LOAD_FACTOR = 0.75f;
// 散列表中用于存儲元素的數(shù)組，使用初始化長度作為數(shù)組的初始長度。
private static Entry[] table = new Entry[DEFAULT_INITIAL_CAPACITY];
// size表示散列表中元素的個數(shù)，use表示散列表使用地址的個數(shù)
private int size = 0;
private int use = 0;
/**
* 向散列表中添加或者修改元素
* @param key 指定的key值
* @param value 指定的value值
*/
public void put(int key, int value) {
// 通過散列函數(shù)獲得索引
int index = hash(key);
// 如果當(dāng)前索引下沒有任何元素，那么向散列表數(shù)組中添加一個空元素
if (table[index] == null) {
table[index] = new Entry(-1, -1, null);
}
// 從散列表數(shù)組中獲取當(dāng)前索引的元素
Entry e = table[index];
if (e.next == null) {
// 如果e.next==null，表示當(dāng)前索引下元素并沒有指向其它的元素，那么可以直接向當(dāng)前元素追加一個新的元素。
table[index].next = new Entry(key, value, null);
// 添加完元素后，對size，use值自增，同時檢測是否需要擴容。
size++;
use++;
if (use >= table.length * LOAD_FACTOR) {
resize();
}
} else {
// 如果e.next!=null，表示當(dāng)前索引下的元素存在指向其它的元素，那么遍歷當(dāng)前索引下的鏈表，判斷是否存在元素的key值等于指定key值的元素，如果存在則修改其value值。
for (e = e.next; e != null; e = e.next) {
int k = e.key;
if (k == key) {
e.value = value;
return;
}
}
// 如果遍歷完當(dāng)前鏈表中沒有發(fā)現(xiàn)key值對應(yīng)的元素，那么新建一個元素插入到鏈表中，對應(yīng)size值自增,這里的插入是將新元素插入到當(dāng)前索引的下一個位置，新元素指向原先元素指向的元素。因為散列表中沒有使用新的地址值，所以use值無需自增。
Entry temp = table[index].next;
Entry newEntry = new Entry(key, value, temp);
table[index].next = newEntry;
size++;
}
}
/**
* 刪除指定key值的元素
* @param key
*/
public void remove(int key) {
// 通過散列函數(shù)獲取對應(yīng)的索引值
int index = hash(key);
// 獲取當(dāng)前索引下的元素
Entry e = table[index];
Entry pre = table[index];
// 判斷當(dāng)前鏈表中是否有實際元素
if (e != null && e.next != null) {
// 遍歷鏈表中所有的元素，如果存在指定key的元素，那么修改鏈表中前一個元素的指向，從而起到刪除的作用，然后size值對應(yīng)自減
for (e = e.next; e != null; pre = e, e = e.next) {
int k = e.key;
if (k == key) {
pre.next = e.next;
size--;
return;
}
}
}
}
/**
* 返回指定key值的value值
* @param key 指定的key值
* @return 一個int型值，返回的是指定key值的value值
*/
public int get(int key) {
// 通過散列函數(shù)獲取對應(yīng)的索引值
int index = hash(key);
// 通過索引獲取散列數(shù)組中對應(yīng)的元素
Entry e = table[index];
// 判斷獲取的元素是否是有效元素，如果是，則進一步遍歷鏈表，查找是否有對應(yīng)key值的元素。
if (e != null && e.next != null) {
// 遍歷鏈表，查找是否有對應(yīng)key值的元素，如果存在就返回其value值。
for (e = e.next; e != null; e = e.next) {
int k = e.key;
if (k == key) {
return e.value;
}
}
}
// 如果沒有找到對應(yīng)key值的元素，則返回-1。
return -1;
}
/**
* @return 返回散列表中元素的數(shù)量
*/
public int size() {
return size;
}
/**
* @return 返回散列表中已經(jīng)使用的地址個數(shù)
*/
public int getUse(){
return use;
}
/**
*
* @return 返回散列表數(shù)組的長度
*/
public int getLength() {
return table.length;
}
/**
* 散列函數(shù)，這里使用了比較簡單的除留取余法
* @param key 指定的key值
* @return 返回一個int值，作為hash算法的返回值
*
*/
private int hash(int key) {
return key % table.length;
}
/**
* 該方法用于擴容
*/
private void resize() {
// 定義了一個int型值用于作為新的散列表數(shù)組的長度，其為原有長度的兩倍
int newLength = table.length * 2;
// 定義了一個Entry類型數(shù)組，用于存放原有的散列數(shù)組中的元素，用于后面擴容后，將原有數(shù)據(jù)重新賦值到新的散列數(shù)組中。
Entry[] oldTable = table;
// 備份完原有數(shù)據(jù)后，將table指向新的散列數(shù)組對象，容量為原來的兩倍，此時散列數(shù)組中沒有數(shù)據(jù)，故use值重置為0.
table = new Entry[newLength];
use = 0;
// 通過循環(huán)將備份的老散列數(shù)組中的數(shù)據(jù)放入新的散列數(shù)組之中。
for (int i = 0; i < oldTable.length; i++) {
// 該判斷用于篩選出老的散列數(shù)組中存儲數(shù)據(jù)的位置
if (oldTable[i] != null && oldTable[i].next != null) {
// 新建了一個Entry元素，用于接收老的散列數(shù)組中對應(yīng)索引處的元素
Entry e = oldTable[i];
// 遍歷老的散列數(shù)組中的鏈表，將其重新通過散列函數(shù)計算，重新放置到新的散列數(shù)組中。
while (null != e.next) {
// 新建了一個Entry元素，用于存放當(dāng)前元素指向的下一個元素
Entry next = e.next;
// 通過散列函數(shù)，重新計算key值對應(yīng)的索引值
int index = hash(next.key);
// 獲取當(dāng)前索引下的元素，如果為空向其中添加第一個頭元素，同時use值自增
if (table[index] == null) {
use++;
table[index] = new Entry(-1, -1, null);
}
// 如果當(dāng)前元素不為空，那么將舊列表中的指定元素加入到新列表中指定鏈表的首部(頭元素之后)。
Entry temp = table[index].next;
Entry newEntry = new Entry(next.key, next.value, temp);
table[index].next = newEntry;
// 元素指向下一位
e = next;
}
}
}
}
}
執(zhí)行上述代碼可以在控制臺看到如下打?。?/p>
可以看到我們存入的元素成功的存儲進了我們自定義的散列表之中。
以上為本篇的全部內(nèi)容，其中有的知識點一概而過了，可能的話會在其它的篇幅中進行補充。
