一、數(shù)據(jù)結(jié)構(gòu)之哈希表

所謂哈希表，是一種數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，我們可以通過數(shù)據(jù)的“關(guān)鍵碼值”來直接訪問表。通過散列的方法(可以理解為一種特殊的數(shù)學(xué)過程=_=)，我們可以把關(guān)鍵碼值映射到數(shù)組中的不同位置。

設(shè)計(jì)散列系統(tǒng)的目標(biāo)是對于任一個(gè)關(guān)鍵碼值Key，都能通過某散列函數(shù)的計(jì)算來得到一個(gè)數(shù)組中的存儲(chǔ)下標(biāo)，使得該位置存儲(chǔ)值Value。這樣一來就很可能出現(xiàn)不同的關(guān)鍵碼值對應(yīng)同一個(gè)數(shù)組下標(biāo)的情況，因此設(shè)計(jì)沖突解決策略也是必須的。
一種很容易想到的解決沖突的策略是，每當(dāng)要存儲(chǔ)一個(gè)關(guān)鍵值為Key的數(shù)據(jù)時(shí)，首先判斷計(jì)算出的存儲(chǔ)下標(biāo)處是否已經(jīng)存儲(chǔ)了一個(gè)數(shù)據(jù)，如果是則將下標(biāo)值進(jìn)行“+1”操作，繼續(xù)判斷，直到判斷為否時(shí)存入數(shù)據(jù)。

根據(jù)以上原理我們可以設(shè)計(jì)一個(gè)簡單的程序來模擬哈希表的實(shí)現(xiàn)（這里假設(shè)Key和Value的數(shù)據(jù)類型都是int）

public class HashDemo {

    static int size = 1000;
    static int[] hash = new int[size];
    int currsize = 0;
    int Key, Value;

    static {
        for (int i = 0; i < size; i++) {
            hash[i] = -1;
        }
    }

    // 構(gòu)造方法
    public HashDemo(int Key, int Value) {
        this.Key = Key;
        this.Value = Value;
    }

    public HashDemo() {}

    // 計(jì)算hashcode
    public int hashcode(int Key) {
        int index = Key % size;
        if (currsize == size) {
            return -1;
        } else {
            while (index >= 0 && index < size && hash[index] != -1) {
                index++;
                if (index == size - 1) {
                    index++;
                }
            }
            return index;
        }
    }


    // 往HashDemo中插入測試數(shù)據(jù)
    public boolean put(int Key, int Value) {
        int index = hashcode(Key);
        if (index == -1 || index < 0 || index >= size)
            return false;
        else {
            hash[index] = Value;
            return true;
        }
    }

    public void Tester() {
        HashDemo hd = new HashDemo();
        long starttime = System.currentTimeMillis();

        for (int i = 0; i < 100000; i++) {
            hd.put(i * i, i * i);
        }
        long endtime = System.currentTimeMillis();
        System.out.println("100000次put所用時(shí)間:" + (endtime - starttime) + "ms");
            }

}

二、java中hashmap的具體實(shí)現(xiàn)

import java.util.HashMap;

public class HashTest {

    public void Tester(){
        HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();

        long starttime=System.currentTimeMillis();

        for(int i=0;i<1000000;i++){
            Integer n=new Integer(i);
            hm.put(n*n,n*n );
        }

        long endtime=System.currentTimeMillis();
        System.out.println("100000次put所用時(shí)間:"+(endtime-starttime)+"ms");

        starttime=System.currentTimeMillis();

        for(int i=0;i<1000000;i++){
            Integer n=new Integer(i);
            Integer m=hm.get(n*n);
        }

        endtime=System.currentTimeMillis();
        System.out.println("100000次get所用時(shí)間:"+(endtime-starttime)+"ms");

        starttime=System.currentTimeMillis();

        for(int i=0;i<1000000;i++){
            Integer n=new Integer(i);
            hm.remove(n*n);
        }

        endtime=System.currentTimeMillis();
        System.out.println("100000次remove所用時(shí)間:"+(endtime-starttime)+"ms");
    }

可以看到使用java中自帶的hashmap類執(zhí)行put操作時(shí)，和上述思路所花費(fèi)的時(shí)間有較大的出入，并且可以發(fā)現(xiàn)多次put和get操作所花費(fèi)的時(shí)間也有較大的差別。

通過查看源代碼其實(shí)不難發(fā)現(xiàn)，java中的哈希表中每一個(gè)位置不會(huì)只存儲(chǔ)一個(gè)元素，如果有多個(gè)Key值計(jì)算出來的hashcode結(jié)果是相同的，則這幾個(gè)元素并不會(huì)移動(dòng)存儲(chǔ)的位置，也就是說，hashcode一旦被計(jì)算出來，就不會(huì)在改變。

那么多個(gè)數(shù)據(jù)是怎么存儲(chǔ)在數(shù)組的一個(gè)位置上呢，其實(shí)很簡單，我們可以聯(lián)想數(shù)據(jù)結(jié)構(gòu)中的“圖”，其中有一種表示方法叫做臨接表表示法，將存儲(chǔ)在同一位置的數(shù)據(jù)用鏈表的形式連接起來來進(jìn)行存儲(chǔ)，其實(shí)HashMap有一個(gè)叫做Entry的內(nèi)部類，它用來存儲(chǔ)key-value對。

```

由于put時(shí)每一次都要實(shí)例化Entry內(nèi)部類的對象，所以put方法要使用比get方法更久的時(shí)間。

三、hashcode的計(jì)算方法

由于java中有許多的數(shù)據(jù)類型，而且有時(shí)傳入的Key是一個(gè)類的對象。所以hashcode的計(jì)算并不是那么容易。在設(shè)計(jì)一個(gè)類的時(shí)候，很可能要重寫類的hashCode()方法，根據(jù)哈希表的特點(diǎn)，重寫的hashCode()方法需要遵守以下準(zhǔn)則：
            ①同一個(gè)對象調(diào)用hashCode()時(shí)，應(yīng)返回相同的值
            ②若兩個(gè)對象通過equals()方法比較返回true的時(shí)候，兩個(gè)對象的hashCode()方法應(yīng)返回相同的值
            ③對象調(diào)用equals()方法參與比較的值，都應(yīng)該拿來計(jì)算hashCode()

對象中不同的值對應(yīng)不同的計(jì)算方法：

```

將所有的數(shù)據(jù)計(jì)算出來的hashCode相加即為該對象的hashCode();為了避免重復(fù)，可以讓各個(gè)數(shù)據(jù)乘以不同的權(quán)值后再相加。