散列(二)

上一章 散列(一) 主要介紹了散列的基本概念以及沖突解決方法--分離鏈表法。這一章主要介紹解決沖突的另一種方法---開放定址法。

開放定址法:嘗試另外一些單元,直到找出空的單元為止钓简。
  • 線性探測法:當產生沖突時,它將尋找下一個空閑地址放入汹想。
  • 平方探測法:使用 f(i) = i 2 的方法來解決沖突外邓,并且保證如果表有一半為空,并且表的大小為素數古掏,那么我們保證總能夠插入一個新的元素损话。
  • 雙散列:使用如下探測方法:


    double_hashing.png
線性探測法:

在線性探測法中,函數f是i的線性函數槽唾,典型的情形為f(i) = i 丧枪。 這相當于探測逐個單元(必要時可以回繞)以查找出一個空單元。

線性探測.png

如上圖庞萍,我們逐個插入關鍵字{89拧烦,18,49钝计,58恋博,69}。第一個沖突發(fā)生在插入49關鍵字私恬,它和89產生了沖突(因為49%10=9且89%10=9)债沮,因此,49被推入下一個空閑位置本鸣,即位置0 (注意這里是可以回繞的) ,緊接著插入58疫衩,58和18沖突了,則找下一個空閑位置永高,找到位置1.對于69的沖突也是一樣的隧土。

我們發(fā)現即使表相對較空提针,還是會發(fā)生一些占據的單元集中在一些塊區(qū),這種現象我們成為一次聚集曹傀。
也就是說辐脖,散列在區(qū)塊中的任何關鍵字都需要多次試選單元才能解決沖突,然后將關鍵字添加進去皆愉。

實驗證明嗜价,當裝填因子(散列表中元素個數與該表大小的比)在0 ~ 0.5之間所需探測的次數時較小的,考慮到探測次數和rehash的消耗幕庐,我們一般采用0.5作為裝填因子會達到比較好的效果久锥。

線性探測.png
平方探測法
  • 平方探測法是消除線性探測中一次聚集問題的解決沖突的方法。平方探測就是沖突函數為二次的探測方法异剥。
  • 對于線性探測瑟由,讓散列表中填滿元素并不是一個好主意,因為此時表的性能在下降冤寿。而對于平方探測方法情況甚至更糟:一旦表被填充了一半歹苦,當表的大小不是素數時甚至在表被填充一半之前,就不能保證一次找到空的單元了督怜。這是因為最多有表的一半作為解決沖突的備選位置殴瘦。
  • 定理:** 如果使用平方探測,且表的大小是素數号杠,那么當表至少有一半是空的時候蚪腋,總能夠插入一個新的元素**。
  • 在探測散列表中的刪除操作姨蟋,我們不能直接執(zhí)行屉凯,因為相應的單元可能已經引起過沖突,被轉移到其他地方了眼溶。

a. 定義一個類用來標記每個位置的值以及其是否處于活動狀態(tài)(即是否存在值)

    /**
     * 定義一個類用來標記每個位置的情況
     * @param <AnyType>
     */
    private static class HashEntry<AnyType>{
        //當前位置的元素值
        public AnyType element;
        //當前位置是否為活動狀態(tài)神得,默認為活動狀態(tài),但若刪除后偷仿,會設置其為非活動狀態(tài)
        public boolean isActive;

        public HashEntry(AnyType e){
            this(e, true);
        }

        public HashEntry(AnyType e, boolean b){
            element = e;
            isActive = b;
        }
    }

b. 定義所需變量:

    //默認表的大小
    private static final int DEFAULT_TABLE_SIZE = 11;
    //存儲表
    private HashEntry<AnyType> [] array;
    //當前表的大小
    private int currentSize;

c. 進行初始化操作:

    //無參數構造函數
    public QuadraticProbingHashTable(){
        this(DEFAULT_TABLE_SIZE);
    }
    //有參數構造函數
    public QuadraticProbingHashTable(int size){
        allocateArray(size);
        makeEmpty();
    }
    //清空表
    public void makeEmpty(){
        currentSize = 0;
        for (int i = 0; i < array.length; i ++){
            array[i] = null;
        }
    }
    //初始化表
    private void allocateArray(int size){
        array = new HashEntry[nextPrime(size)];
    }

c. 解決沖突位置:

    /**
     * 尋找空閑位置,以解決沖突
     * @param x
     * @return
     */
    private int findPos(AnyType x){
        //定義偏移量
        int offset = 1;
        //獲取到hash位置
        int currentPos = myHash(x);
        //若hash位置中存在元素,并且當前元素不等于傳入的元素
        while (array[currentPos] != null && !array[currentPos].element.equals(x)){
            //進行偏移
            currentPos += offset;
            //改變偏移量
            offset += 2;
            //考慮到溢出情況
            if (currentPos >= array.length){
                currentPos -= array.length;
            }
        }
        return currentPos;
    }

d. 插入操作:

    //插入元素
    public void insert(AnyType x){
        //獲取到空閑位置
        int currentPos = findPos(x);
        //若該位置為活動狀態(tài)宵蕉,則返回酝静,表示該位置已經存在元素
        //這種情況,實際上表示該位置上已經存在了該元素羡玛,那么不必重復插入
        if (isActive(currentPos)){
            return;
        }
        //否則别智,插入該元素
        array[currentPos] = new HashEntry<AnyType>(x);
        //判斷表的大小,超過一半稼稿,則進行rehash
        if (++ currentSize > array.length / 2){
            rehash();
        }
    }
    //判斷當前位置是否為活動狀態(tài)
    private boolean isActive(int currentPos){
        return array[currentPos] != null && array[currentPos].isActive;
    }

e. 刪除操作:

public void remove(AnyType x){
        //找到位置
        int currentPos = findPos(x);
        //若該位置為活動狀態(tài)薄榛,則進行刪除操作
        if (isActive(currentPos)){
            //令該位置為非活動狀態(tài)即可
            array[currentPos].isActive = false;
            currentSize --;
        }
    }

f. 查詢操作:

public boolean contains(AnyType x){
        int currentPos = findPos(x);
        //返回該位置是否為活動狀態(tài)
        return isActive(currentPos);
 }

g. rehash操作:

private void rehash(){
        HashEntry<AnyType> [] oldArray = array;
        //擴充表的大小
        allocateArray(nextPrime(2 * oldArray.length));
        currentSize = 0;
        //將舊表的數據添加到新表中
        for (int i = 0; i < oldArray.length; i ++){
            if (oldArray[i] != null && oldArray[i].isActive){
                insert(oldArray[i].element);
            }
        }
    }
完整代碼:
public class QuadraticProbingHashTable<AnyType> {
    //無參數構造函數
    public QuadraticProbingHashTable(){
        this(DEFAULT_TABLE_SIZE);
    }
    //有參數構造函數
    public QuadraticProbingHashTable(int size){
        allocateArray(size);
        makeEmpty();
    }
    //清空表
    public void makeEmpty(){
        currentSize = 0;
        for (int i = 0; i < array.length; i ++){
            array[i] = null;
        }
    }

    public boolean contains(AnyType x){
        int currentPos = findPos(x);
        //返回該位置是否為活動狀態(tài)
        return isActive(currentPos);
    }

    //插入元素
    public void insert(AnyType x){
        //獲取到空閑位置
        int currentPos = findPos(x);
        //若該位置為活動狀態(tài)讳窟,則返回,表示該位置已經存在元素
        //這種情況敞恋,實際上表示該位置上已經存在了該元素丽啡,那么不必重復插入
        if (isActive(currentPos)){
            return;
        }
        //否則,插入該元素
        array[currentPos] = new HashEntry<AnyType>(x);
        //判斷表的大小硬猫,超過一半补箍,則進行rehash
        if (++ currentSize > array.length / 2){
            rehash();
        }
    }

    public void remove(AnyType x){
        //找到位置
        int currentPos = findPos(x);
        //若該位置為活動狀態(tài),則進行刪除操作
        if (isActive(currentPos)){
            //令該位置為非活動狀態(tài)即可
            array[currentPos].isActive = false;
            currentSize --;
        }
    }

    /**
     * 定義一個類用來標記每個位置的情況
     * @param <AnyType>
     */
    private static class HashEntry<AnyType>{
        //當前位置的元素值
        public AnyType element;
        //當前位置是否為活動狀態(tài)啸蜜,默認為活動狀態(tài)坑雅,但若刪除后,會設置其為非活動狀態(tài)
        public boolean isActive;

        public HashEntry(AnyType e){
            this(e, true);
        }

        public HashEntry(AnyType e, boolean b){
            element = e;
            isActive = b;
        }
    }

    //默認表的大小
    private static final int DEFAULT_TABLE_SIZE = 11;
    //存儲表
    private HashEntry<AnyType> [] array;
    //當前表的大小
    private int currentSize;

    //初始化表
    private void allocateArray(int size){
        array = new HashEntry[nextPrime(size)];
    }

    //判斷當前位置是否為活動狀態(tài)
    private boolean isActive(int currentPos){
        return array[currentPos] != null && array[currentPos].isActive;
    }

    /**
     * 尋找空閑位置衬横,以解決沖突
     * @param x
     * @return
     */
    private int findPos(AnyType x){
        //定義偏移量
        int offset = 1;
        //獲取到hash位置
        int currentPos = myHash(x);
        //若hash位置中存在元素,并且當前元素不等于傳入的元素
        while (array[currentPos] != null && !array[currentPos].element.equals(x)){
            //進行偏移
            currentPos += offset;
            //改變偏移量
            offset += 2;
            //考慮到溢出情況
            if (currentPos >= array.length){
                currentPos -= array.length;
            }
        }
        return currentPos;
    }


    private void rehash(){
        HashEntry<AnyType> [] oldArray = array;
        //擴充表的大小
        allocateArray(nextPrime(2 * oldArray.length));
        currentSize = 0;
        //將舊表的數據添加到新表中
        for (int i = 0; i < oldArray.length; i ++){
            if (oldArray[i] != null && oldArray[i].isActive){
                insert(oldArray[i].element);
            }
        }
    }


    //根據值獲取到其對應的hash位置
    private int myHash(AnyType x){
        int hashVal = x.hashCode();
        hashVal %= array.length;
        if (hashVal < 0){
            hashVal += array.length;
        }
        return hashVal;
    }

    //返回下一個素數
    private static int nextPrime(int n){
        while (!isPrime(n)){
            n ++;
        }
        return n;
    }
    //判斷是否為素數
    private static boolean isPrime(int n){
        for (int i = 2; i <= Math.sqrt(n); i ++){
            if (n % i == 0 && n != 2){
                return false;
            }
        }
        return true;
    }

}
最后編輯于
?著作權歸作者所有,轉載或內容合作請聯系作者
  • 序言:七十年代末裹粤,一起剝皮案震驚了整個濱河市,隨后出現的幾起案子蜂林,更是在濱河造成了極大的恐慌遥诉,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件悉尾,死亡現場離奇詭異突那,居然都是意外死亡,警方通過查閱死者的電腦和手機构眯,發(fā)現死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進店門愕难,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人惫霸,你說我怎么就攤上這事猫缭。” “怎么了壹店?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵猜丹,是天一觀的道長。 經常有香客問我硅卢,道長射窒,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任将塑,我火速辦了婚禮脉顿,結果婚禮上,老公的妹妹穿的比我還像新娘点寥。我一直安慰自己艾疟,他們只是感情好,可當我...
    茶點故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著蔽莱,像睡著了一般弟疆。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上盗冷,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天怠苔,我揣著相機與錄音,去河邊找鬼正塌。 笑死嘀略,一個胖子當著我的面吹牛,可吹牛的內容都是我干的乓诽。 我是一名探鬼主播帜羊,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼鸠天!你這毒婦竟也來了讼育?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤稠集,失蹤者是張志新(化名)和其女友劉穎奶段,沒想到半個月后,有當地人在樹林里發(fā)現了一具尸體剥纷,經...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡痹籍,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現自己被綠了晦鞋。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片蹲缠。...
    茶點故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖悠垛,靈堂內的尸體忽然破棺而出线定,到底是詐尸還是另有隱情,我是刑警寧澤确买,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布斤讥,位于F島的核電站,受9級特大地震影響湾趾,放射性物質發(fā)生泄漏芭商。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一搀缠、第九天 我趴在偏房一處隱蔽的房頂上張望蓉坎。 院中可真熱鬧,春花似錦胡嘿、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽勿侯。三九已至,卻和暖如春缴罗,著一層夾襖步出監(jiān)牢的瞬間助琐,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工面氓, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留兵钮,地道東北人。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓舌界,卻偏偏與公主長得像掘譬,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子呻拌,可洞房花燭夜當晚...
    茶點故事閱讀 45,876評論 2 361

推薦閱讀更多精彩內容

  • Map 是一種很常見的數據結構藐握,用于存儲一些無序的鍵值對靴拱。在主流的編程語言中,默認就自帶它的實現猾普。C袜炕、C++ 中的...
    一縷殤流化隱半邊冰霜閱讀 9,286評論 23 67
  • 9.3.3 快速排序 ??快速排序將原數組劃分為兩個子數組,第一個子數組中元素小于等于某個邊界值初家,第二個子數組中的...
    RichardJieChen閱讀 1,847評論 0 3
  • 概念 散列表的實現常常叫做散列(hashing)偎窘。散列是一種用于以常數平均時間執(zhí)行插入、刪除和查找的技術笤成。散列函數...
    NoFacePeace閱讀 332評論 0 0
  • 沖突的普遍性 ? ? 生日悖論 我們可以考慮這樣一個實際問題:某課堂上的所有學生中评架,是否由某兩位在同一天過生日(稱...
    峰峰小閱讀 861評論 0 1
  • 冷靜漂泊 微光還在頻閃 我為你創(chuàng)造了所有燈紅和酒綠 步步為營助長那些理想的花兒 千山越過邊境 雨中 白玫瑰綴滿了我...
    瑾闊徐行閱讀 117評論 0 0