散列表（Hash table）——將條目的關(guān)鍵碼視作其在映射結(jié)構(gòu)中的存放位置

散列表由兩個(gè)要素構(gòu)成：桶數(shù)組與散列函數(shù)

桶數(shù)組

散列表使用的桶數(shù)組（Bucket array ）幽歼，其實(shí)就是一個(gè)容量為 N 的普通數(shù)組 A[0..N-1]，只不過在這里唠粥，我們將其中的每個(gè)單元都想象為一個(gè)“桶”（Bucket）吠式，每個(gè)桶單元里都可以存放一個(gè)條目蠢古。

另外我們還需要某一函數(shù)，將任意關(guān)鍵碼轉(zhuǎn)換為介于 0 與 N-1 之間的整數(shù)??這個(gè)函數(shù)就是所謂的散列函數(shù)（Hash function）。

散列函數(shù)

為了將散列技術(shù)推廣至一般類型的關(guān)鍵碼珍坊，我們需要借助散列函數(shù) h侵状，將關(guān)鍵碼 key映射為一個(gè)整數(shù) h(key) ∈ [0..N-1]赞弥，并將對(duì)應(yīng)的條目存放至第 h(key)號(hào)桶內(nèi)，其中 N 為桶數(shù)組的容量趣兄。

如果將桶數(shù)組記作 A[ ]绽左，這一技術(shù)就可以總結(jié)為“將條目 e = (key, value)存放至 A [ h ( key ) ] 中”。

反過來(lái)诽俯，為了查找關(guān)鍵碼為 key 的條目妇菱，只需取出桶單元 A[h(key)]中存放的對(duì)象。因此暴区，h(key)也被稱作 e 的散列地址闯团。

不過，若要兌現(xiàn)上述構(gòu)思仙粱，還需要滿足另一個(gè)條件—— h( )是一個(gè)單射房交，即不同的關(guān)鍵碼key1 ≠ key2 必然對(duì)應(yīng)于不同的散列地址h(key1) ≠ h(key2)。不幸的是伐割，在絕大多數(shù)應(yīng)用問題中候味，這一條件都很難滿足。如果不同關(guān)鍵碼的散列地址相同隔心，我們就說該散列發(fā)生了沖（Collision）白群。

一個(gè)好的散列函數(shù) h()必須兼顧以下兩條基本要求：

• h( )應(yīng)該盡可能接近單射；
• 對(duì)于任何關(guān)鍵碼 key硬霍，h(key)的計(jì)算必須能夠在 O(1)時(shí)間內(nèi)完成帜慢。

關(guān)于散列函數(shù)的計(jì)算，Java有其特有的習(xí)慣唯卖。Java將h(key)的計(jì)算劃分為兩步：

• （1）將一般性的關(guān)鍵碼key轉(zhuǎn)換為一個(gè)稱作“散列碼”的整數(shù)粱玲；
• （2）然后再通過所謂的“壓縮函數(shù)”將該整數(shù)映射至區(qū)間[0..N-1]內(nèi)。

散列碼

Java 可以幫助我們將任意類型的關(guān)鍵碼 key 轉(zhuǎn)換為一個(gè)整數(shù)拜轨，稱作 key 的散列碼（Hash code）抽减。請(qǐng)注意，散列碼距離我們最終所需的散列地址還有很大距離??它不見得落在區(qū)間[0..N-1]內(nèi)橄碾，甚至不見得是正的整數(shù)卵沉。

不過這并不要緊颠锉，在這一階段我們最關(guān)心的是：各關(guān)鍵碼的散列碼之間，應(yīng)盡可能地減少?zèng)_突偎箫。顯然木柬，要是在這一階段就發(fā)生沖突，后面的沖突就無(wú)法避免淹办。

此外眉枕，從判等器的判等效果來(lái)看，散列碼必須與關(guān)鍵碼對(duì)象相互一致：被判等器 EqualityTester 判定為相等的兩個(gè)關(guān)鍵碼怜森，對(duì)應(yīng)的散列碼也應(yīng)該相等速挑。

Java 的通用類 Object 提供了一個(gè)默認(rèn)的散列碼轉(zhuǎn)換方法 hashCode()，利用它可以將任意對(duì)象實(shí)例映射為“代表”該對(duì)象的某個(gè)整數(shù)副硅。具體來(lái)說姥宝，hashCode()方法的返回值是一個(gè) 32 位 int 型整數(shù)（實(shí)際上，這一默認(rèn) hashCode()方法所返回的不過就是對(duì)象在內(nèi)存中的存儲(chǔ)地址）恐疲。

遺憾的是腊满，這一看似再自然不過的方法，實(shí)際上存在著嚴(yán)重的缺
陷培己，因此我們?cè)谑褂脮r(shí)需格外小心碳蛋。

比如，這種散列碼的轉(zhuǎn)換辦法對(duì)字符串型關(guān)鍵碼就極不適用省咨。若兩個(gè)字符串對(duì)象完全相等肃弟，本應(yīng)該將它們轉(zhuǎn)換為同一散列碼，但由于它們的內(nèi)存地址不同零蓉，由 hashCode()得到的散列碼將絕對(duì)不會(huì)一樣笤受。
實(shí)際上，在實(shí)現(xiàn) String 類時(shí)敌蜂，Java 已經(jīng)將 Object 類的 hashCode()方法改寫為一種更加適宜于字符串關(guān)鍵碼的方法箩兽。

壓縮函數(shù)

（1）模余法

最簡(jiǎn)單的壓縮辦法，就是取 N 為素?cái)?shù)章喉，并將散列碼 i 映射為：

** | i | mod N **

之所以將 N 選取為素?cái)?shù)比肄，是為了最大程度地將散列碼均勻地映射至[0..N-1]區(qū)間內(nèi)。
比如囊陡，對(duì)于散列碼集合{200, 205, 210, 215, …, 690, 695, 700}，若選取 N = 100掀亥，則其中的每個(gè)散列碼都會(huì)與另外的至少四個(gè)關(guān)鍵碼相沖突撞反；而若改用 N = 101，則不會(huì)有任何沖突搪花。

（2）MAD 法

采用一種將乘法（Mutiply）遏片、加法（Add）和除法（Divide）結(jié)合起來(lái)的方法嘹害，該方法也因此得名。具體來(lái)說吮便，對(duì)于散列碼 i笔呀，MAD 法會(huì)將 i 映射為：

** | a×i + b | mod N **

其中 N 仍為素?cái)?shù)，a>0髓需，b>0许师，a mod N ≠ 0，它們都是在確定壓縮函數(shù)時(shí)隨機(jī)選取的常數(shù)僚匆。

基于散列表實(shí)現(xiàn)映射類

我們給出基于散列表實(shí)現(xiàn)的映射結(jié)構(gòu)：

package dsa.Map;

import dsa.Iterator.Iterator;
import dsa.Iterator.IteratorElement;
import dsa.List.List;
import dsa.List.List_DLNode;
import dsa.PriorityQueue.Entry;

public class Map_HashTable implements Map {

    /*
     * 基于散列表實(shí)現(xiàn)的映射結(jié)構(gòu) 采用分離鏈策略解決沖突
     */

    private Map[] A;// 桶數(shù)組微渠，每個(gè)桶本身也是一個(gè)（基于列表實(shí)現(xiàn)的）映射結(jié)構(gòu)
    private int N;// 散列表長(zhǎng)
    private final double maxLemda = 0.75;// 裝填因子上限
    private int size;// 映射結(jié)構(gòu)的規(guī)模
    private EqualityTester T;// 判等器
    // 默認(rèn)構(gòu)造方法

    public Map_HashTable() {
        this(0, new EqualityTesterDefault());
    }

    // 構(gòu)造方法
    public Map_HashTable(int n, EqualityTester t) {
        T = t;
        N = p(n);// 桶數(shù)組容量取為不小于n的最小素?cái)?shù)
        A = new Map[N];
        for (int i = 0; i < N; i++)
            A[i] = new Map_DLNode(T);
        size = 0;
    }

    /***************************** 輔助方法 *****************************/
    // 散列定址函數(shù)（采用模余法）
    private int h(Object key) {
        return key.hashCode() % N;
    }

    // 判斷n是否為素?cái)?shù)
    private static boolean prime(int n) {
        for (int i = 3; i < 1 + Math.sqrt(n); i++)
            if (n / i * i == n)
                return false;
        return true;
    }

    // 取不小于n的最小素?cái)?shù)
    private static int p(int n) {
        if (3 > n)
            n = 3;
        n = n | 1;// 奇數(shù)化
        while (!prime(n))
            n += 2;
        return n;
    }

    /***************************** ADT方法 *****************************/
    // 查詢映射結(jié)構(gòu)當(dāng)前的規(guī)模
    public int getSize() {
        return size;
    }

    // 判斷映射結(jié)構(gòu)是否為空
    public boolean isEmpty() {
        return 0 == size;
    }

    // 若M中存在以key為關(guān)鍵碼的條目，則返回該條目的數(shù)據(jù)對(duì)象咧擂；否則逞盆，返回null
    public Object get(Object key) {
        return A[h(key)].get(key);
    }

    // 若M中不存在以key為關(guān)鍵碼的條目，則將條目(key, value)加入到M中并返回null
    // 否則松申，將已有條目的數(shù)據(jù)對(duì)象替換為value云芦，并返回原先的數(shù)據(jù)對(duì)象
    public Object put(Object key, Object value) {
        Object oldValue = A[h(key)].put(key, value);
        if (null == oldValue) {// 若插入的條目未出現(xiàn)于原散列表中，則
            size++;// 更新規(guī)模記錄
            if (size > N * maxLemda)
                rehash();// 若裝填因子過大贸桶，則重散列
        }
        return oldValue;
    }

    // 若M中存在以key為關(guān)鍵碼的條目舅逸，則刪除之并返回其數(shù)據(jù)對(duì)象；否則刨啸，返回null
    public Object remove(Object key) {
        Object oldValue = A[h(key)].remove(key);
        if (null != oldValue)
            size--;
        return oldValue;
    }

    // 返回M中所有條目的一個(gè)迭代器
    // 將各桶對(duì)應(yīng)的映射結(jié)構(gòu)的迭代器串接起來(lái)堡赔，構(gòu)成整體的迭代器
    public Iterator entries() {
        List L = new List_DLNode();
        for (int i = 0; i < N; i++) {
            Iterator it = A[i].entries();
            while (it.hasNext())
                L.insertLast(it.getNext());
        }
        return new IteratorElement(L);
    }

    // 重散列
    private void rehash() {
        Iterator it = this.entries();
        N = p(N << 1);
        A = new Map[N];// 桶數(shù)組容量至少加倍
        for (int i = 0; i < N; i++)
            A[i] = new Map_DLNode(T);// 為每個(gè)桶分配一個(gè)子映射
        while (it.hasNext()) {// 將其對(duì)應(yīng)的映射結(jié)構(gòu)中的
            Entry e = (Entry) it.getNext();// 各條目逐一取出，將其
            Object k = e.getKey();// 關(guān)鍵碼和
            Object v = e.getValue();// 數(shù)據(jù)對(duì)象
            A[h(k)].put(k, v);// 整合為新的條目设联，插入對(duì)應(yīng)的子映射中
        }
    }
}

裝填因子

對(duì)于散列表的性能而言善已，裝填因子λ = n/N是最重要的影響因素。

如果λ > 1离例，則沖突在所難免换团。

實(shí)際上，關(guān)于散列表平均復(fù)雜度的分析結(jié)果指出：

• 采取分離鏈策略時(shí)應(yīng)該保持λ < 0.9宫蛆，
• 采取開放定址策略時(shí)則應(yīng)該保持λ < 0.5

這些都得到了實(shí)驗(yàn)統(tǒng)計(jì)的證明艘包。

若采用分離鏈策略，則在發(fā)生沖突的桶中耀盗，對(duì)條目的查找將退化為對(duì)鏈表的查找想虎。因此，隨著λ不斷接近于 1叛拷，發(fā)生沖突的概率也將不斷接近于 100%舌厨，從而導(dǎo)致更多的時(shí)間消耗于對(duì)鏈表的查找，使得各種操作的效率下降忿薇。

當(dāng)采用開放定址策略時(shí)裙椭，隨著λ超過 0.5 并不斷提高躏哩，條目在桶數(shù)組中聚集的程度將急速加劇，于是揉燃，需要經(jīng)過越來(lái)越多次的探測(cè)才能完成一次查找扫尺。

重散列

通常都采用重散列的方法??將所有條目全部取出，將桶數(shù)組的規(guī)模
加倍炊汤，然后將各條目重新插入其中正驻。

例如，Java 內(nèi)建的 java.util.HashMap 類實(shí)現(xiàn)了映射結(jié)構(gòu)的 ADT婿崭，在創(chuàng)建該類的對(duì)象時(shí)拨拓，程序員可以指定裝填因子的上限（默認(rèn)設(shè)置為 0.75）。一旦裝填因子超出這一范圍氓栈，java.util.HashMap會(huì)自動(dòng)進(jìn)行重散列（Rehashing）渣磷。