（最近剛來到簡(jiǎn)書平臺(tái)衷戈，以前在CSDN上寫的一些東西狭吼，也在逐漸的移到這兒來，有些篇幅是很早的時(shí)候?qū)懴碌耐讯瑁虼丝赡軙?huì)看到一些內(nèi)容雜亂的文章搏嗡，對(duì)此深感抱歉，以下為正文）

引子

眾所周知，數(shù)據(jù)結(jié)構(gòu)和算法對(duì)于一個(gè)開發(fā)人員是多么的重要采盒，一個(gè)好的數(shù)據(jù)結(jié)構(gòu)和算法旧乞，可以讓你在實(shí)現(xiàn)同一個(gè)功能的時(shí)候，提升非常多的效率磅氨。筆者作為一個(gè)初入IT業(yè)的菜鳥尺栖，覺得也很有必要在這方面下一番功夫，所以特開此篇作為學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的開篇烦租，后面會(huì)繼續(xù)記錄分享我的學(xué)習(xí)經(jīng)歷延赌。

因?yàn)楣P者主要做Java這塊兒的工作，所以前期寫的東西大多都是以Java作為基礎(chǔ)語(yǔ)言來進(jìn)行描述的叉橱，不過數(shù)據(jù)結(jié)構(gòu)和算法這種東西挫以，其實(shí)跟語(yǔ)言的關(guān)聯(lián)性不是特別大。想學(xué)習(xí)算法窃祝，那么必須對(duì)數(shù)據(jù)結(jié)構(gòu)有一定的了解掐松，一些好的算法難免要結(jié)合一些數(shù)據(jù)結(jié)構(gòu)的知識(shí)來實(shí)現(xiàn)。本篇講述的是最基礎(chǔ)最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)(數(shù)組粪小，集合和散列表)大磺，盡管它們很基礎(chǔ)，但我們?nèi)孕枰煤玫娜チ私馑鼈儭?/p>

正文

數(shù)組

數(shù)組是數(shù)據(jù)結(jié)構(gòu)中最為基礎(chǔ)的一個(gè)結(jié)構(gòu)探膊，是我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的基石杠愧，事實(shí)上大部分的數(shù)據(jù)結(jié)構(gòu)都可以用數(shù)組來進(jìn)行實(shí)現(xiàn)。就像在前面Java IO筆記的篇幅中逞壁，我們可以經(jīng)常在源碼中看到數(shù)組的存在流济，靈活的運(yùn)用它們可以為我們解決很多事情。

那么數(shù)組是什么呢猾担，在我看來數(shù)組就是有限個(gè)數(shù)的同類型數(shù)據(jù)袭灯，按照順序排列，組合在一起的一個(gè)有序集合绑嘹。當(dāng)然在一些弱語(yǔ)言中稽荧，數(shù)組對(duì)內(nèi)部元素的數(shù)據(jù)類型沒有強(qiáng)制要求，如JavaScript中我們可以使用var來聲明變量而不用指定數(shù)據(jù)類的類型工腋，但在Java中姨丈，數(shù)組要求數(shù)據(jù)元素必須是同一種類型。數(shù)組可以分為一維數(shù)組和多維數(shù)組擅腰，事實(shí)上多維數(shù)組就是一維數(shù)組的擴(kuò)展蟋恬，就是一維數(shù)組中的元素還是數(shù)組，如是而已趁冈。

數(shù)組有一個(gè)最為明顯的特征歼争，那就是它是定長(zhǎng)的拜马，在使用前我們需要先行明確它需要在內(nèi)存中開辟出多大的空間，如果開辟的空間過小沐绒，那么我們無法將所需要的數(shù)據(jù)完整的存儲(chǔ)到數(shù)組之中俩莽，如果我們開辟的過大，那么除了裝載我們所需的數(shù)據(jù)之外乔遮，其它的空間將會(huì)被浪費(fèi)掉扮超。所以我們?cè)谑褂脭?shù)組的過程中必須要結(jié)合使用的場(chǎng)景謹(jǐn)慎使用，合理初始化蹋肮。下面將結(jié)合一些Java的代碼以及圖示來簡(jiǎn)單地描述數(shù)組的使用出刷。

在Java中，數(shù)組（一維）的創(chuàng)建方式如下坯辩，筆者為了方便馁龟，之后的實(shí)例中都將以int類型數(shù)組作為描述對(duì)象：

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);

        // 該種方法在聲明的同時(shí)就為其賦值
        int[] array2 = new int[] { 1, 2, 3, 4, 5 };
        System.out.print("聲明同時(shí)直接賦值：");
        printArray(array2);
    }

    private void printArray(int[] arrays) {
        for (int temp : arrays) {
            System.out.print(temp + "  ");
        }
        System.out.println();
    }
}

執(zhí)行上述代碼后可以在控制臺(tái)看到如下打颖舴：

控制臺(tái)輸出

上面展示的示例代碼演示了在Java中創(chuàng)建數(shù)組的過程屁柏。第一種是先聲明再賦值啦膜，執(zhí)行時(shí)有送，會(huì)先在內(nèi)存中開辟出指定的空間，此時(shí)數(shù)組中沒有賦值僧家，JVM會(huì)自動(dòng)為其在內(nèi)存中賦上默認(rèn)初始值雀摘，初始值根據(jù)數(shù)組類型來分配，在Java中八拱，引用型數(shù)據(jù)類型默認(rèn)初始為null阵赠，基本數(shù)據(jù)類型的默認(rèn)初始值如下圖所示：

數(shù)值初始化

之后再將需要存儲(chǔ)的值放入開辟好的空間之中，下面筆者將通過畫圖的方式更形象地來描述這個(gè)過程肌稻。

內(nèi)存描述

如上圖所示清蚀，我截取了initArray方法中的一部分代碼并畫圖分析。程序運(yùn)行爹谭，首先JVM會(huì)將Test.class文件加載到方法區(qū)中枷邪，本例中，首先被壓入棧內(nèi)存的是initArray方法诺凡，方法中定義了一個(gè)局部變量array1东揣，該變量是個(gè)int類型數(shù)組，初始化時(shí)腹泌，采用了先開辟空間后賦值的方式嘶卧，因此當(dāng)執(zhí)行完第一條語(yǔ)句后，JVM會(huì)在堆空間中開辟出一個(gè)可以容納5個(gè)int型數(shù)據(jù)的空間凉袱，此時(shí)數(shù)組空間中因?yàn)闆]有指定初始化值芥吟，JVM會(huì)自動(dòng)向內(nèi)填充初始值侦铜，賦值規(guī)則在上面已經(jīng)提到過，不同類型數(shù)據(jù)的默認(rèn)初始值是不同的钟鸵，本例中泵额，因?yàn)槭褂玫氖莍nt型數(shù)組，所以默認(rèn)的初始值為0携添，然后array1變量便指向了這片內(nèi)存嫁盲。之后通過一個(gè)for循環(huán)為數(shù)組重新賦值，堆空間中使用新的值替換掉之前的默認(rèn)值烈掠，接著執(zhí)行printArray方法羞秤，該方法進(jìn)棧，因?yàn)槲覀兪菍rray1變量作為參數(shù)傳入了該方法左敌，所以該方法中的arrays參數(shù)也是指向著array1所在的這片內(nèi)存瘾蛋，然后方法內(nèi)通過一個(gè)循環(huán)遍歷了該數(shù)組中的元素，并將它們打印了出來矫限。

采用第二種方式其實(shí)在本質(zhì)上跟第一種方式?jīng)]有區(qū)別哺哼，都會(huì)經(jīng)歷默認(rèn)初始化值這一步，只是給人的感官上是省略了默認(rèn)初始化這一步叼风。通過上面的描述取董，對(duì)數(shù)組有了初步的認(rèn)識(shí)，我們知道了數(shù)組擁有著定長(zhǎng)的特性无宿，除了定長(zhǎng)的特性茵汰，數(shù)組還有著順序訪問的特性，盡管在編程中我們可以使用索引來獲取數(shù)組中指定位置的值孽鸡，但計(jì)算機(jī)在執(zhí)行時(shí)蹂午，其實(shí)還是一個(gè)一個(gè)的按順序訪問的，直到訪問到指定索引的位置彬碱。

因?yàn)閿?shù)組的特性豆胸，所以數(shù)組的適用場(chǎng)景主要是那些業(yè)務(wù)不會(huì)出現(xiàn)變化的場(chǎng)景。筆者曾經(jīng)寫過一個(gè)小的象棋游戲巷疼，當(dāng)時(shí)的棋盤就是用二維數(shù)組來表示的晚胡，因?yàn)槠灞P上可以落子的位置個(gè)數(shù)是固定的，正好符合數(shù)組的特性皮迟。盡管數(shù)組的作用很強(qiáng)大搬泥，但也有這其劣勢(shì)，因?yàn)槎ㄩL(zhǎng)的特性伏尼，導(dǎo)致如果業(yè)務(wù)出現(xiàn)變化時(shí)忿檩，需要重新改變程序，所以下面就來說說數(shù)組的延伸運(yùn)用爆阶。

動(dòng)態(tài)數(shù)組

正如前面所說燥透，數(shù)組雖然比較高效沙咏，但是因?yàn)槠涠ㄩL(zhǎng)的特性導(dǎo)致了其應(yīng)用場(chǎng)景的局限性。神說要有光班套，于是便有了光肢藐，因?yàn)橛兄枨螅杂辛藙?chuàng)新吱韭。為了解決數(shù)組定長(zhǎng)的問題吆豹，集合這類數(shù)據(jù)結(jié)構(gòu)誕生了，因?yàn)榧系母拍畋容^寬泛理盆，所以暫且將其理解為一個(gè)用于存儲(chǔ)元素的容器痘煤，并且其是變長(zhǎng)的。

集合的出現(xiàn)猿规，解決了數(shù)組因?yàn)槎ㄩL(zhǎng)特性而不能解決的應(yīng)用場(chǎng)景衷快。集合跟數(shù)組一樣也有著其一些屬于自己的特性：

• 集合的容量是非固定的。當(dāng)集合的當(dāng)前容量不足以裝載新的元素時(shí)姨俩，它會(huì)自動(dòng)擴(kuò)展容量以裝納新的元素蘸拔。這點(diǎn)是跟數(shù)組最明顯的區(qū)別。
• 集合中存放的為引用性數(shù)據(jù)類型环葵，因?yàn)樽詣?dòng)裝箱拆箱的原因调窍，也可以存放基本數(shù)據(jù)類型，但本質(zhì)上在存儲(chǔ)時(shí)基本數(shù)據(jù)類型已經(jīng)自動(dòng)裝箱為其對(duì)應(yīng)的引用型數(shù)據(jù)類型進(jìn)行存儲(chǔ)积担。
• 集合在不適用泛型約束的時(shí)候陨晶，一個(gè)集合中是可以存放多種類型的數(shù)據(jù)的。數(shù)組只能存放單一類型數(shù)據(jù)帝璧。

集合是一種比較寬泛的定義，為了解決各種不同的需求湿刽，它可以細(xì)化成很多獨(dú)有的數(shù)據(jù)結(jié)構(gòu)：

• 列表：列表是集合的一種的烁，它是一種順序結(jié)構(gòu)，常見的有鏈表诈闺、隊(duì)列渴庆、棧等。
• 集：集也是集合的一種雅镊，它是一種無序的結(jié)構(gòu)襟雷，并且其中的存儲(chǔ)的元素是不能重復(fù)的。
• 多重集：多重集也是集合的一種仁烹，一般來說它也是無序的耸弄，但相較集而言，它是可以存儲(chǔ)重復(fù)的值的卓缰。
• 關(guān)聯(lián)數(shù)組：關(guān)聯(lián)數(shù)組同樣也是集合的一種计呈，它也是無需的砰诵，但它多了一種鍵-值的概念，通過鍵可以獲得值捌显。
• 樹茁彭、圖等等。

在Java中扶歪，其已經(jīng)為我們內(nèi)置了很多常用的集合結(jié)構(gòu)理肺，它們都位于java.util包下，在之后的學(xué)習(xí)中將會(huì)對(duì)其進(jìn)行進(jìn)一步的了解善镰。

本節(jié)的標(biāo)題是動(dòng)態(tài)數(shù)組也可以叫其動(dòng)態(tài)列表哲嘲。其實(shí)集合這類結(jié)構(gòu)大多數(shù)都可以通過數(shù)組來實(shí)現(xiàn)的，如果讀者有過c語(yǔ)言的基礎(chǔ)媳禁，對(duì)此看法肯定會(huì)表示一定的贊同眠副。下面將展示如何基于數(shù)組去建立一個(gè)動(dòng)態(tài)數(shù)組。

在開始動(dòng)手之前竣稽，我們可以進(jìn)行簡(jiǎn)單的分析囱怕。我們之所以想構(gòu)建動(dòng)態(tài)數(shù)組的原因僅僅只是因?yàn)閿?shù)組定長(zhǎng)的特性。那么如何解決這個(gè)問題呢毫别，好比正常生活中我們現(xiàn)在使用著一部?jī)?nèi)存16g的手機(jī)娃弓，隨著我們使用時(shí)間的增長(zhǎng)，發(fā)現(xiàn)手機(jī)內(nèi)存不足以滿足我們的需求岛宦，這時(shí)你會(huì)怎么做呢台丛？刪掉一些東西繼續(xù)使用？這個(gè)方法只是臨時(shí)的緩解當(dāng)前的困境砾肺，隨著時(shí)間的增長(zhǎng)挽霉，仍然會(huì)發(fā)生一樣的問題。大部分的人應(yīng)該會(huì)直接購(gòu)買一個(gè)內(nèi)存容量更大的手機(jī)变汪，當(dāng)然你還會(huì)把原來手機(jī)上重要的數(shù)據(jù)拷貝到新手機(jī)之上侠坎。

說到這里，我們是不是也找到了問題的解決辦法了呢裙盾。因?yàn)閿?shù)組定長(zhǎng)的特性实胸，當(dāng)我們遇到所要裝載數(shù)據(jù)量大于其數(shù)組空間的時(shí)候，我們完全可以創(chuàng)建一個(gè)容量足夠大的數(shù)組用以裝載數(shù)據(jù)番官，同時(shí)將原數(shù)組的數(shù)據(jù)拷貝過來就行了庐完。動(dòng)態(tài)數(shù)組便是基于這個(gè)原理實(shí)現(xiàn)的。下面可以通過一副簡(jiǎn)單的流程圖來描述動(dòng)態(tài)數(shù)組的工作流程徘熔。

動(dòng)態(tài)數(shù)組工作流程

了解了工作原理之后门躯，接下來就是動(dòng)手開始擼碼了，我們對(duì)于該變長(zhǎng)數(shù)組的實(shí)現(xiàn)近顷，可以參考Java中為我們提功的ArrayList類生音，該類是Java為我們封裝好的集合類之一宁否。下面貼上利用數(shù)組簡(jiǎn)單實(shí)現(xiàn)動(dòng)態(tài)列表的代碼：

package Arraylist;

import java.util.Arrays;

public class MyArrayList{
    //定義了一個(gè)常量值，表示內(nèi)置數(shù)組的初始長(zhǎng)度為10
    private static final int INITIAL_SIZE = 10;

    //該變量用于表示內(nèi)置數(shù)組中實(shí)際使用的數(shù)量
    private int size = 0;

    //定義了一個(gè)Object類型數(shù)組缀遍，用于存儲(chǔ)元素
    private Object[] data;

    /**
     * 一個(gè)無參構(gòu)造函數(shù)慕匠，為內(nèi)置數(shù)組進(jìn)行初始化，初始化容量為默認(rèn)的初始值10
     */
    public MyArrayList(){
        data = new Object[INITIAL_SIZE];
    }

    /**
     * 一個(gè)帶一個(gè)參數(shù)的構(gòu)造函數(shù)
     * @param initial 默認(rèn)的列表初始化容量
     */
    public MyArrayList(int initial){
        if(initial <= 0){
            throw new IllegalArgumentException("輸入的容量初始值必須大于0");
        }
        data = new Object[initial];
    }

    /**
     * 該方法用于向動(dòng)態(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ù)組自動(dòng)擴(kuò)容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ù)組的最大長(zhǎng)度");
        }
        return data[index];
    }

    /**
     * 設(shè)置指定位置的元素值
     * @param index
     * @param obj
     */
    public void set(int index,Object obj){
        data[index] = obj;
    }

    /**
     * 獲得當(dāng)前動(dòng)態(tài)列表中存入數(shù)據(jù)的長(zhǎng)度
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 獲得當(dāng)前動(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("初始化時(shí)動(dòng)態(tài)列表中存儲(chǔ)的元素為"+list.size());
        System.out.println("初始化時(shí)動(dòng)態(tài)列表中的容量大小為"+list.length());
        for(int i = 0; i < 11; i++){
            list.add(i);
        }
        System.out.println("賦值后動(dòng)態(tài)列表中存儲(chǔ)的元素為"+list.size());
        System.out.println("賦值后動(dòng)態(tài)列表中的容量大小為"+list.length());
        System.out.print("列表中的元素為：");
        for(int i = 0; i < list.size(); i++){
            System.out.print(list.get(i)+"\t");
        }
    }
}

執(zhí)行上述代碼域醇，可以在控制臺(tái)看到如下打犹ㄒ辍：

控制臺(tái)輸出

從控制臺(tái)的打印中可以看出，我們創(chuàng)建的動(dòng)態(tài)列表成功的將數(shù)據(jù)存儲(chǔ)了起來譬挚，并且當(dāng)自身空間不夠使用的時(shí)候锅铅，自動(dòng)進(jìn)行了擴(kuò)容的操作。盡管這個(gè)動(dòng)態(tài)列表是基于數(shù)組創(chuàng)建的减宣，內(nèi)置的數(shù)組仍然保有定長(zhǎng)的特性盐须，但在外部使用時(shí)，完全感受不到其定長(zhǎng)的特性漆腌，擴(kuò)容的操作已經(jīng)在內(nèi)部便消化了贼邓。

在上面的代碼中，最關(guān)鍵的擴(kuò)容步驟中闷尿，筆者使用了一個(gè)工具類方法Arrays.copyOf方法塑径，該方法的內(nèi)部其實(shí)是調(diào)用了System.arraycopy方法，該方法是一個(gè)native方法填具，執(zhí)行效率非常高统舀，遠(yuǎn)比我們使用循環(huán)賦值的方式來拷貝舊數(shù)據(jù)要效率的多。

因?yàn)榇藙?dòng)態(tài)數(shù)組的實(shí)現(xiàn)是基于數(shù)組的劳景，所以它的執(zhí)行效率相對(duì)數(shù)組而言也沒有什么提升誉简，只是解決了定長(zhǎng)的問題。并且在擴(kuò)容和拷貝舊數(shù)據(jù)的時(shí)候甚至還會(huì)增加系統(tǒng)的開銷枢泰，所以在使用時(shí)也要根據(jù)實(shí)際場(chǎng)景來判斷如何使用描融，定義一個(gè)合理的初始化容量，以及一個(gè)合理的擴(kuò)容倍數(shù)都可以提升該結(jié)構(gòu)在實(shí)際場(chǎng)景中應(yīng)用的效率衡蚂。

散列表

前面提到了集合，并且建立了一個(gè)動(dòng)態(tài)數(shù)組來擺脫數(shù)組定長(zhǎng)的約束骏庸，但它在使用時(shí)毛甲，仍然有一些限制。因?yàn)閯?dòng)態(tài)數(shù)組其本身仍然是順序存儲(chǔ)的具被，所以當(dāng)我們要查詢其中的某個(gè)元素時(shí)玻募，我們需要順序地遍歷其中的每個(gè)元素，直到找到了要指定的元素一姿。當(dāng)動(dòng)態(tài)數(shù)組中元素總量很大七咧，并且我們所要查找的元素在動(dòng)態(tài)數(shù)組中的位置相對(duì)靠后時(shí)跃惫，此時(shí)的查詢效率是比較慢的。所以散列表就這么應(yīng)運(yùn)而生了艾栋，散列表同樣是集合中的一種爆存，它是一種使用空間去置換時(shí)間的存儲(chǔ)結(jié)構(gòu)。正所謂魚和熊證二者不可兼得蝗砾，在我們使用的過程中先较，我們要根據(jù)實(shí)際的情況去選用合適的數(shù)據(jù)結(jié)構(gòu)，如果只是因?yàn)榭吹缴⒘斜淼男时容^高并且其又能解決數(shù)組定長(zhǎng)的問題就一昧的去使用它悼粮，那么你會(huì)發(fā)現(xiàn)占用過多的存儲(chǔ)空間也是一件令人頭疼的事情闲勺。
上面描述了這么多，并沒能描述出散列表到底是什么扣猫，實(shí)在是罪過罪過菜循，小生在這兒給各位大俠賠禮了。

舉個(gè)生活中的小例子來描述一樣吧申尤。查字典癌幕，這個(gè)經(jīng)典的動(dòng)作就可以很好地對(duì)其進(jìn)行詮釋。當(dāng)我們查字典時(shí)瀑凝，如果使用動(dòng)態(tài)數(shù)組的方式去查詢的話序芦，那么意味著我們需要從第一頁(yè)一頁(yè)一頁(yè)的不停往后翻，直到我們查到了想要查找到的字粤咪⊙柚校可以想象一下，如果我們所要查詢的字在字典的最后一頁(yè)上寥枝，那意味著我們需要將整本字典都翻上一遍宪塔。如果我們使用散列表，那么我們的操作流程如下囊拜，我們會(huì)先通過字典的索引表上找到我們要查找的字所在的頁(yè)數(shù)某筐，然后通過查詢到的頁(yè)數(shù)，便可以直接翻至我們所要查找的字所在的頁(yè)冠跷，事實(shí)上南誊，我們?cè)谏钪幸泊_實(shí)是使用這種方式來查詢字典的。

通過上面的描述蜜托，此時(shí)對(duì)散列表也就有了一些初步的了解抄囚。散列表也叫做哈希表，它能通過給定的關(guān)鍵字直接訪問到具體的值 橄务，即可以把關(guān)鍵字映射到某一個(gè)表中位置上來直接訪問記錄幔托。這樣的操作方式大大加快了訪問的速度。

一般上述的關(guān)鍵字我們稱其key，將其對(duì)應(yīng)的值稱為value重挑。我們可以通過key值通過映射表直接訪問到對(duì)應(yīng)的value值嗓化。這里的映射表一般稱作散列函數(shù)或者哈希函數(shù)。而存儲(chǔ)數(shù)據(jù)的數(shù)組稱其散列表谬哀。

使用散列表時(shí)刺覆，我們通過一個(gè)key值，必定能訪問到一個(gè)唯一的value地址玻粪，理想狀態(tài)下隅津，key值和value地址值是一一對(duì)應(yīng)的，但實(shí)際情況下劲室，不同的key值經(jīng)散列函數(shù)計(jì)算之后可能會(huì)指向同一個(gè)value地址伦仍，這便發(fā)生了碰撞，在下面的篇幅中很洋，會(huì)講述一些解決碰撞問題的方法充蓝。

散列函數(shù)在散列表中起到了至關(guān)重要的作用，一個(gè)好的散列函數(shù)喉磁，可以極大程度的提高散列表的效率谓苟。下面就來介紹一些簡(jiǎn)單的散列函數(shù)：

• 直接尋址法
  直接尋址法是直接取關(guān)鍵字或者關(guān)鍵字的某個(gè)線性函數(shù)作為散列地址。即address = key 或者 address = a*key+b协怒。
• 數(shù)字分析法
  數(shù)字分析法是指通過對(duì)數(shù)據(jù)進(jìn)行分析涝焙，找出數(shù)據(jù)中沖突比較少的部分作為散列地址，即取關(guān)鍵字中的部分位作為散列地址孕暇，該種方法一般是在散列表中的關(guān)鍵字事先知道的情況下可以選擇的一種方式仑撞。比如學(xué)校中學(xué)生的學(xué)號(hào)，學(xué)生的學(xué)號(hào)一般包含入學(xué)年份妖滔，所修系的編號(hào)隧哮，所修專業(yè)的編號(hào)，班級(jí)號(hào)座舍，班級(jí)中的編號(hào)等沮翔，我們可以剔除入學(xué)年份，系編號(hào)這種存在大可能性雷同的數(shù)據(jù)字段曲秉，采用后面剩余的字段來作為散列地址采蚀。
• 平方取中法
  平方取中法是指當(dāng)我們無法確定關(guān)鍵字中哪幾位的分布相對(duì)比較均勻時(shí)，可以先求出關(guān)鍵字的平方值承二，然后取平方值的中間幾位作為散列地址搏存。因?yàn)橛?jì)算平方之后的中間幾位基本和關(guān)鍵字中的每一位值都息息相關(guān)，這樣可以使得散列地址的分配是隨機(jī)的矢洲，至于是取中間幾位作為散列地址，這個(gè)主要看表的長(zhǎng)度來決定的缩焦。
• 取隨機(jī)數(shù)法
  使用隨機(jī)數(shù)算法為關(guān)鍵字分配散列地址读虏。
• 除留取余法
  除留取余法是指取關(guān)鍵字被某個(gè)不大于散列表表長(zhǎng)m的數(shù)n除后所得的余數(shù)p來作為散列地址责静。該種方法可以再使用了上述其它方法后再次使用。該種方式對(duì)數(shù)n的要求比較高盖桥，一般取素?cái)?shù)或者直接使用表長(zhǎng)m灾螃，若選擇不好，則很容易產(chǎn)生碰撞揩徊。

上述的5種散列函數(shù)是比較基礎(chǔ)易懂的腰鬼。事實(shí)上你完全可以自己設(shè)計(jì)出屬于自己的散列函數(shù)，當(dāng)然你得參考一些關(guān)鍵因素：關(guān)鍵字的長(zhǎng)度塑荒，哈希表的大小熄赡，關(guān)鍵字的分布狀況，記錄的查找頻率等等齿税。

前面有提到過彼硫，當(dāng)我們向散列表中裝載數(shù)據(jù)時(shí)，同一個(gè)關(guān)鍵字key值經(jīng)過散列函數(shù)的計(jì)算過后凌箕，可能會(huì)分配至同一個(gè)地址空間拧篮，從而產(chǎn)生了碰撞，在這種情況下牵舱，我們就可能會(huì)覆蓋掉原有的數(shù)據(jù)串绩，從而造成了數(shù)據(jù)丟失，這是萬萬無法接受的芜壁。既然發(fā)現(xiàn)了問題礁凡，那我們自然要去解決問題。下面就簡(jiǎn)單介紹幾種常見的解決沖突的方法：

• 開放尋址法
  開放尋址法就是當(dāng)關(guān)鍵字經(jīng)過散列函數(shù)計(jì)算獲取到一個(gè)地址后沿盅，首先會(huì)判斷當(dāng)前地址是否已經(jīng)被使用了把篓，如果當(dāng)前地址沒有被使用，那么便將需要存儲(chǔ)的數(shù)據(jù)放入該地址下腰涧，如果發(fā)現(xiàn)當(dāng)前地址已經(jīng)被使用了韧掩，那么需要對(duì)該地址進(jìn)行探索再哈希。比如向后移動(dòng)一個(gè)地址窖铡，直到找到未被占用的地址疗锐，然后將要存儲(chǔ)的數(shù)據(jù)放入其中。其中探索再哈希這個(gè)過程可以通過一些算法來增加我們的效率费彼，該方面有機(jī)會(huì)的話再其它的篇幅中描述滑臊。開放尋址法與后面的鏈地址法是相對(duì)應(yīng)的，開放尋址法是將所有的元素都存放在散列表中箍铲，而不像鏈地址法通過加入鏈表結(jié)構(gòu)來解決沖突雇卷。
• 鏈地址法
  鏈地址法就是當(dāng)產(chǎn)生沖突時(shí)，同一個(gè)地址放置需要裝載多個(gè)數(shù)據(jù)的時(shí)候，多個(gè)數(shù)據(jù)采用鏈表的形式裝載進(jìn)指定的地址之中关划，該種方法在很多高級(jí)語(yǔ)言中均有實(shí)現(xiàn)小染，之后代碼演示的自定義的散列表中解決沖突的方式便是采用這種方式的。
• 創(chuàng)建一個(gè)公共溢出區(qū)
  該種方式就是單獨(dú)創(chuàng)建一個(gè)公共溢出區(qū)贮折，當(dāng)?shù)刂反嬖跊_突后裤翩，將新的地址放到公共溢出區(qū)里。

理想狀態(tài)下调榄，散列表的搜索時(shí)間復(fù)雜度為O(1)踊赠，影響該時(shí)間復(fù)雜度的主要原因就是是否產(chǎn)生沖突。因此影響散列表效率的主要因素就是是否有一個(gè)好的散列函數(shù)每庆，是否一個(gè)好的沖突解決方法筐带，以及是散列表的填裝因子（即散列表中元素個(gè)數(shù)與表長(zhǎng)的商），填裝因子越小越好扣孟，當(dāng)填裝因子過大時(shí)發(fā)生沖突的可能性就越大烫堤，在java中，填裝因子為0.75凤价。

散列表一般在平常的使用當(dāng)中可以用于做消息緩存鸽斟，比如可以先將數(shù)據(jù)庫(kù)或服務(wù)器上常用的數(shù)據(jù)，以散列表的形式緩存到本地利诺，這樣便可以提高程序的運(yùn)行效率富蓄，散列表還可以用于一些需要快速查找的場(chǎng)景之中，畢竟散列表這種結(jié)構(gòu)相較其它的數(shù)據(jù)結(jié)構(gòu)來看慢逾，其查找立倍，插入，刪除等一般操作的時(shí)間復(fù)雜度僅為O(1)侣滩，效率還是要快于其它的。
下面就是使用java代碼簡(jiǎn)單實(shí)現(xiàn)的一個(gè)自定義的散列表寝志。其散列函數(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)散列表的初始化長(zhǎng)度
    private static final int DEFAULT_INITIAL_CAPACITY = 4;

    // 擴(kuò)充因子唯竹，如果散列表內(nèi)元素?cái)?shù)量占總?cè)萘康谋壤_(dá)到這個(gè)標(biāo)準(zhǔn)，那么在之后的操作中將會(huì)自動(dòng)擴(kuò)容
    private static final float LOAD_FACTOR = 0.75f;

    // 散列表中用于存儲(chǔ)元素的數(shù)組浸颓，使用初始化長(zhǎng)度作為數(shù)組的初始長(zhǎng)度物臂。
    private static Entry[] table = new Entry[DEFAULT_INITIAL_CAPACITY];
    // size表示散列表中元素的個(gè)數(shù)旺拉，use表示散列表使用地址的個(gè)數(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ù)組中添加一個(gè)空元素
        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)前元素追加一個(gè)新的元素规丽。
            table[index].next = new Entry(key, value, null);
            // 添加完元素后撇贺，對(duì)size，use值自增艘狭，同時(shí)檢測(cè)是否需要擴(kuò)容翠订。
            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值對(duì)應(yīng)的元素菠净，那么新建一個(gè)元素插入到鏈表中，對(duì)應(yīng)size值自增,這里的插入是將新元素插入到當(dāng)前索引的下一個(gè)位置屈梁，新元素指向原先元素指向的元素在讶。因?yàn)樯⒘斜碇袥]有使用新的地址值，所以u(píng)se值無需自增革答。
            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ù)獲取對(duì)應(yīng)的索引值
        int index = hash(key);
        // 獲取當(dāng)前索引下的元素
        Entry e = table[index];
        Entry pre = table[index];
        // 判斷當(dāng)前鏈表中是否有實(shí)際元素
        if (e != null && e.next != null) {
            // 遍歷鏈表中所有的元素，如果存在指定key的元素途茫，那么修改鏈表中前一個(gè)元素的指向溪食，從而起到刪除的作用错沃，然后size值對(duì)應(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 一個(gè)int型值，返回的是指定key值的value值
     */
    public int get(int key) {
        // 通過散列函數(shù)獲取對(duì)應(yīng)的索引值
        int index = hash(key);
        // 通過索引獲取散列數(shù)組中對(duì)應(yīng)的元素
        Entry e = table[index];
        // 判斷獲取的元素是否是有效元素玉掸，如果是司浪，則進(jìn)一步遍歷鏈表把沼，查找是否有對(duì)應(yīng)key值的元素智政。
        if (e != null && e.next != null) {
            // 遍歷鏈表，查找是否有對(duì)應(yīng)key值的元素垦垂，如果存在就返回其value值牙瓢。
            for (e = e.next; e != null; e = e.next) {
                int k = e.key;
                if (k == key) {
                    return e.value;
                }
            }
        }
        // 如果沒有找到對(duì)應(yīng)key值的元素，則返回-1页慷。
        return -1;
    }

    /**
     * @return 返回散列表中元素的數(shù)量
     */
    public int size() {
        return size;
    }

    /**
     * @return 返回散列表中已經(jīng)使用的地址個(gè)數(shù)
     */
    public int getUse(){
        return use;
    }

    /**
     * 
     * @return 返回散列表數(shù)組的長(zhǎng)度
     */
    public int getLength() {
        return table.length;
    }

    /**
     * 散列函數(shù)酒繁，這里使用了比較簡(jiǎn)單的除留取余法
     * @param key 指定的key值
     * @return 返回一個(gè)int值艳汽，作為hash算法的返回值
     * 
     */
    private int hash(int key) {
        return key % table.length;
    }


    /**
     * 該方法用于擴(kuò)容
     */
    private void resize() {
        // 定義了一個(gè)int型值用于作為新的散列表數(shù)組的長(zhǎng)度弓候，其為原有長(zhǎng)度的兩倍
        int newLength = table.length * 2;
        // 定義了一個(gè)Entry類型數(shù)組他匪，用于存放原有的散列數(shù)組中的元素邦蜜，用于后面擴(kuò)容后亥至，將原有數(shù)據(jù)重新賦值到新的散列數(shù)組中。
        Entry[] oldTable = table;
        // 備份完原有數(shù)據(jù)后井辆，將table指向新的散列數(shù)組對(duì)象，容量為原來的兩倍蒸播，此時(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ù)組中存儲(chǔ)數(shù)據(jù)的位置
            if (oldTable[i] != null && oldTable[i].next != null) {
                // 新建了一個(gè)Entry元素宿崭，用于接收老的散列數(shù)組中對(duì)應(yīng)索引處的元素
                Entry e = oldTable[i];
                // 遍歷老的散列數(shù)組中的鏈表葡兑，將其重新通過散列函數(shù)計(jì)算赞草，重新放置到新的散列數(shù)組中厨疙。
                while (null != e.next) {
                    // 新建了一個(gè)Entry元素，用于存放當(dāng)前元素指向的下一個(gè)元素
                    Entry next = e.next;
                    // 通過散列函數(shù)梗醇，重新計(jì)算key值對(duì)應(yīng)的索引值
                    int index = hash(next.key);
                    // 獲取當(dāng)前索引下的元素撒蟀，如果為空向其中添加第一個(gè)頭元素牙肝，同時(shí)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í)行上述代碼可以在控制臺(tái)看到如下打雍饫恪：

控制臺(tái)輸出

可以看到我們存入的元素成功的存儲(chǔ)進(jìn)了我們自定義的散列表之中瘾境。

以上為本篇的全部?jī)?nèi)容，其中有的知識(shí)點(diǎn)一概而過了犬绒，可能的話會(huì)在其它的篇幅中進(jìn)行補(bǔ)充凯力。