數(shù)據(jù)結構-散列

lei___ 發(fā)布于2019-08-23 12:15 / 2340人閱讀

摘要：散列是一種常用的數(shù)據(jù)存儲技術散列后的數(shù)據(jù)可以快速的插入或取用散列使用的數(shù)據(jù)結構叫做散列表在散列表上插入刪除和取用的數(shù)據(jù)都非常快但是對于查找操作來說卻效率低下比如查找一組數(shù)據(jù)中最大值和最小值這些操作得求助于其它數(shù)據(jù)結構二叉查找樹就是一個很好的

散列是一種常用的數(shù)據(jù)存儲技術, 散列后的數(shù)據(jù)可以快速的插入或取用. 散列使用的數(shù)據(jù)結構叫做 散列表 . 在散列表上插入、刪除和取用的數(shù)據(jù)都非常快, 但是對于查找操作來說卻效率低下, 比如查找一組數(shù)據(jù)中最大值和最小值. 這些操作得求助于其它數(shù)據(jù)結構, 二叉查找樹就是一個很好的選擇. 本章介紹如何實現(xiàn)散列, 以及了解什么時候應用散列存取數(shù)據(jù).

散列概覽

我們的散列表示基于數(shù)組進行設計的. 數(shù)組的長度是預先設定的, 如有需要, 可以隨時增加. 所有元素根據(jù)和該元素對應的鍵, 保存在數(shù)組的特定位置, 該鍵和我們前面講到的字典中的鍵是類似的概念. 使用散列表存儲數(shù)據(jù)時, 通過一個散列函數(shù)將鍵映射為一個數(shù)字, 這個數(shù)字的范圍是0到散列表的長度.

理想情況下, 散列函數(shù)會將每個鍵映射為一個唯一的函數(shù)索引. 然鵝, 鍵的數(shù)量是無限的, 數(shù)組的長度是有限的(理論上, 在js中是這樣的). 一個更現(xiàn)實的目標是讓散列函數(shù)盡量將鍵均勻地映射到數(shù)組中.

即使使用一個搞笑的散列函數(shù), 仍然存在將兩個鍵映射成同一個值的可能, 這樣現(xiàn)象稱為 碰撞(collision) , 當碰撞發(fā)生時, 我們需要有方法去解決. 本章稍后將詳細討論如何解決 _碰撞_.

要確定的最后一個問題是: 散列表中的數(shù)組究竟應該有多大? 這是編寫散列函數(shù)時必須要考慮的. 對數(shù)組大小常見的限制是: 數(shù)組長度應該是一個質數(shù). 在實現(xiàn)各種散列函數(shù)時, 我們將討論為什么要求數(shù)組長度為質數(shù). 之后, 會有多種確定數(shù)組大小的策略, 所有的策略都基于處理碰撞的技術, 因此, 我們將討論如何處理碰撞時對它們進行討論.

HashTable類

我們使用一個類來表示散列表, 該類包含計算散列值的方法、向散列中插入數(shù)據(jù)的方法、從散列表中讀取數(shù)據(jù)的方法、顯示散列表中數(shù)據(jù)分布的方法, 以及其它一些可能會用到的工具方法.

class HashTable {
    constructor() {
        this._table = new Array(137);
    }
    _simpleHash() {

    }
    showDistro() {

    }
    put() {
        
    }
}

選擇一個散列函數(shù)

散列函數(shù)的選擇依賴于鍵值的數(shù)據(jù)類型. 如何鍵是整型, 最簡單的散列函數(shù)就是以數(shù)組的長度對鍵取余. 在一些情況下, 比如數(shù)組的長度是10, 而鍵值都是10的倍數(shù)時, 就不推薦使用這種方式了. 這也是數(shù)據(jù)長度為什么要是質數(shù)的原因之一, 就像我們在上個構造函數(shù)中, 設定數(shù)組長度為137一樣. 如何鍵是隨機的整數(shù), 則散列函數(shù)應該更均勻地分布這些鍵. 這種散列方式稱為: 除留余數(shù)法 .

在很多應用中, 鍵是字符串類型. 事實證明, 選擇針對字符串類型的散列函數(shù)是很難的, 選擇時必須加倍小心.

乍一看, 將字符串中的每個字符的ASCII碼值相加似乎是一個不錯的散列函數(shù). 這樣散列值就是ASCII碼值的和除以數(shù)組長度的余數(shù). 該散列的方法_simpleHash():

...
_simpleHash(data) {
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };

        return total % this._table.length;
    }
...

再給HashTable加兩個方法: put()和_showDistro(), 一個用來將數(shù)據(jù)存入散列表, 一個用來顯示散列表中的數(shù)據(jù), 這樣就初步實現(xiàn)了HashTable類.

...
showDistro() {
    this._table.forEach((i, index) => {
        if(i != undefined) {
            log(`${index}: ${i}`)
        }
    })
}
put(data) {
    const pos = this._simpleHash(data);
    this._table[pos] = data;
}
...

做一個簡單散列:

window.log = console.log.bind(console)

class HashTable {
    constructor() {
        this._table = new Array(137);
    }
    _simpleHash(data) {
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };

        return total % this._table.length;
    }
    showDistro() {
        this._table.forEach((i, index) => {
            if(i != undefined) {
                log(`${index}: ${i}`)
            }
        })
    }
    put(data) {
        const pos = this._simpleHash(data);
        this._table[pos] = data;
    }
};

const someNames = [ "David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan" ];
const h = new HashTable();
someNames.forEach(i => {
    h.put(i);
});
h.showDistro();

輸出如下:

35: Cynthia
45: Clayton
57: Donnie
77: David
95: Danny
116: Mike
132: Jennifer
134: Jonathan

_simpleHash()函數(shù)通過使用JS的charCodeAt()函數(shù), 返回每個字符的ASCII碼值, 然后再將它們相加得到散列值. put()方法通過調用_simpleHash()函數(shù)得到數(shù)組的索引, 然后將數(shù)據(jù)存儲到該索引對應的位置上. 你會發(fā)現(xiàn), 數(shù)據(jù)并不是均勻分布的, 人名想數(shù)組的兩端集中.

比起這種不均勻的分布, 還有一個更嚴重的問題. 如果你仔細觀察輸出, 會發(fā)現(xiàn)初始的數(shù)組中的人名并沒有全部顯示. 給_simpleHash()函數(shù)加入一條console.log()輸出,
log("Hash value:" + data + "->" + total);
運行程序你就會發(fā)現(xiàn)有兩個字符串"Clayton"和"Raymond"的散列值是一樣的. 一樣的散列值引發(fā)了碰撞, 因為碰撞, 只有"Clayton"存入了散列表. 可以通過改善散列函數(shù)來避免碰撞.

一個更好的散列函數(shù)

為了避免碰撞, 首先要確保散列表中用來存儲數(shù)據(jù)的數(shù)組其大小是個 質數(shù). 這一點很關鍵, 這和計算散列值時使用的取余運算有關. 數(shù)組的長度應該在100以上, 這是為了讓數(shù)據(jù)在散列表中分布得更加均勻. 通過試驗我們發(fā)現(xiàn), 比100大且不會讓數(shù)據(jù)產生碰撞的第一個質數(shù)是137. 使用其它更接近100的質數(shù), 在該數(shù)據(jù)集上依然會產生碰撞.

為了避免碰撞, 在給散列表一個合適的大小后, 接下來要有一個計算散列值的更好方法.
霍納算法 很好的解決了這個問題. 本書不會過深入該算法的數(shù)學細節(jié), 在此算法中, 新的散列函數(shù)仍然先計算字符串中各字符的ASCII碼值, 不過求和時每次要乘以一個質數(shù). 大多數(shù)算法書建議使用一個較小的質數(shù), 比如31, 但是對于我們的數(shù)據(jù)集, 31不起作用, 我們使用37, 這樣剛好不會產生碰撞.

_betterHash(data) {
    const H = 37;
    let total = 0;
    for(let i = 0; i < data.length; i++) {
        total += H * total + data.charCodeAt(i);
    };
    total = total % this._table.length;
    if(total < 0) {
        total += this._table.length - 1;
    };
    
    return parseInt(total);
}

window.log = console.log.bind(console)

class HashTable {
    constructor() {
        this._table = new Array(137);
    }
    _simpleHash(data) {
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };

        return total % this._table.length;
    }
    _betterHash(data) {
        const H = 37;
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += H * total + data.charCodeAt(i);
        };
        total = total % this._table.length;
        if(total < 0) {
            total += this._table.length - 1;
        };
        
        return parseInt(total);
    }
    showDistro() {
        this._table.forEach((i, index) => {
            if(i != undefined) {
                log(`${index}: ${i}`)
            }
        })
    }
    put(data) {
        const pos = this._betterHash(data);
        this._table[pos] = data;
    }
};

const someNames = [ "David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan" ];
const h = new HashTable();
someNames.forEach(i => {
    h.put(i);
});
h.showDistro();

程序輸出:

12: Jennifer
22: Raymond
55: Donnie
58: Clayton
80: Jonathan
82: Mike
103: Cynthia
110: Danny

這次所有的人名都顯示出來了, 而且沒有碰撞.

散裂化整型鍵

上面展示了如何散列化字符串類型的鍵, 接下來介紹如何使用散列化整型鍵, 使用的數(shù)據(jù)集是學生的成績. 我們將隨機產生一個9位數(shù)的鍵, 用以識別學生身份和一門成績. 下面是產生學生數(shù)據(jù)(包含ID和成績)的函數(shù):

function getRandomInt(min, max) {
    return Math.floor(Math.random() * (max - min + 1) + min);
};

function genStuData(arr) {
    for(let i = 0; i < arr.length; i++) {
        let num = "";
        for(let j = 1; j <= 9; j++) {
            num += Math.floor(Math.random() * 10)
        };
        num += getRandomInt(50, 100);
        arr[i] = num;
    };
};

使用getRandomInt()函數(shù)時, 可以指定隨機數(shù)的最大值和最小值. 拿學生成績來說, 最低分50, 最高分100.

genStuData()函數(shù)生成學生的數(shù)據(jù). 里層的循環(huán)用來生成學生的ID, 緊跟在循環(huán)后面的代碼生成一個隨機的成績, 并把成績綴在ID的后面. 主程序會把ID和成績分離. 散列函數(shù)將學生ID里的數(shù)字相加, 使用_simpleHash()函數(shù)計算出散列值.

執(zhí)行程序:

const students = new Array(10);
genStuData(students);
students.forEach(i => {
    log(i.substring(0, 8) + "  " + i.substring(9))
});

const h = new HashTable();
students.forEach(i => {
    h.put(i)
});
h.showDistro();

程序輸出:

83700897  87
25732026  56
60875817  85
49919842  77
09796486  57
67922868  58
57820350  58
70903358  54
46307166  100
09033369  99
23: 57820350058
25: 70903358154
27: 25732026956
38: 09033369799
41: 49919842177
46: 09796486557
49: 67922868858
62: 463071660100

散列函數(shù)再一次發(fā)生碰撞, 數(shù)組中沒有包含所有的數(shù)據(jù). 事實上, 如果將程序多跑幾次, 有時會出現(xiàn)正常的情況, 但是結果太不一致了. 可以通過修改數(shù)組的大小, 或者在調用put()方法時使用更好的_betterHash()函數(shù), 來試試能不能解決碰撞.
使用_betterHash()散列函數(shù)得到的輸出:

88200007  99
22314764  82
25636690  64
88623060  53
17940629  70
59142776  58
14774034  70
90261540  66
02406002  75
95463920  65
8: 59142776758
27: 22314764782
46: 95463920165
57: 25636690564
78: 90261540066
80: 88623060453
98: 17940629670
108: 14774034770
112: 02406002475
114: 88200007799

很明顯: 無論是字符串還是整型, _betterHash()的散列效果都更勝一籌.

對散列表排序、從散列表中取值

前面講的是散列函數(shù), 現(xiàn)在學以致用, 看看如何使用散列表來存儲數(shù)據(jù). 為此, 需要修改put()方法, 使得該方法同時接受鍵和數(shù)據(jù)作為參數(shù), 對鍵值散列后, 將數(shù)據(jù)存儲到散列表中.

然后定義get()方法, 用以讀取存儲在散列表中的數(shù)據(jù). 該方法同樣需要對鍵值進行散列化, 然后才能知道數(shù)據(jù)到底存儲在數(shù)組的什么位置.

window.log = console.log.bind(console)

class HashTable {
    constructor() {
        this._table = new Array(137);
    }
    _simpleHash(data) {
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };

        return total % this._table.length;
    }
    _betterHash(data) {
        const H = 37;
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += H * total + data.charCodeAt(i);
        };
        total = total % this._table.length;
        if(total < 0) {
            total += this._table.length - 1;
        };
        
        return parseInt(total);
    }
    showDistro() {
        this._table.forEach((i, index) => {
            if(i != undefined) {
                log(`${index}: ${i}`)
            }
        })
    }
    put(key, data) {
        const pos = this._betterHash(key);
        this._table[pos] = data;
    }
    get(key) {
        return this._table[this._betterHash(key)];
    }
};

const h = new HashTable();
h.put("張三", 110);
h.put("李四", 112);
h.put("王五", 119);

log(h.get("王五")); // 輸出 119

碰撞處理

當散列函數(shù)對于多個輸入產生同樣的輸出時, 就產生了碰撞. 散列算法的第二部分就是介紹如何解決碰撞, 是所有鍵都得以存儲在散列表中. 下面介紹兩種解決辦法: 開鏈法 和 線性探測法 .

開鏈法

當碰撞發(fā)生時, 我們仍希望將鍵存儲到通過散列算法產生的索引位置上, 但實際上, 不可能將多份數(shù)據(jù)存儲到一個數(shù)組單元中. 開鏈法是指實現(xiàn)散列列表的底層數(shù)組中, 每個數(shù)組元素又是一個新的數(shù)據(jù)結構, 比如另一個數(shù)組, 這樣就能存儲多個鍵了.
使用這種技術. 即使兩個鍵散列后的值相同, 依然被保存在同樣的位置, 只不過它們在第二個數(shù)組中的位置不一樣罷了.

實現(xiàn)開鏈法的方法時: 在創(chuàng)建存儲散列過的鍵值的數(shù)組時, 通過調用一個函數(shù)創(chuàng)建一個新的空數(shù)組, 然后將該數(shù)組賦給散列表里的每個數(shù)組元素. 這樣就創(chuàng)建了一個二維數(shù)組. 我們定義了一個函數(shù)buildChains()函數(shù)用來創(chuàng)建第二組數(shù)組, 我們也稱這個數(shù)組為鏈 .
完整代碼:

window.log = console.log.bind(console)

class HashTable {
    constructor() {
        this._table = new Array(137);
    }
    _simpleHash(data) {
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };

        return total % this._table.length;
    }
    _betterHash(data) {
        const H = 37;
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += H * total + data.charCodeAt(i);
        };
        total = total % this._table.length;
        if(total < 0) {
            total += this._table.length - 1;
        };
        
        return parseInt(total);
    }
    showDistro() {
        this._table.forEach((i, index) => {
            if(i[0] != undefined) {
                log(`${index}: ${i}`)
            }
        });
    }
    buildChains() {
        for(let i = 0; i < this._table.length; i++) {
            this._table[i] = new Array();
        };
    }
    put(key, data) {
        const pos = this._betterHash(key);

        let index = 0;
        if(this._table[pos][index] == undefined) {
            this._table[pos][index] = data;
        } else {
            while(this._table[pos][index] != undefined) {
                ++index
            };
            this._table[pos][index] = data;
        }
    }
    get(key) {
        let index = 0;
        const pos = this._betterHash(key);
        
        while ((this._table[pos][index] != undefined) && (this._table[pos][index] != key)) {
            index += 1;
        };
        if(this._table[pos][index] == key) {
            return this._table[pos][index];
        } else {
            return undefined;
        }
    }
};

const someNames = [ "David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan" ];
const h = new HashTable();
h.buildChains();
someNames.forEach(i => {
    h.put(i, i);
});
h.showDistro();

log(h.get("David"))
log(h.get("Jonathan"))

考慮到散列表現(xiàn)在使用多維數(shù)組存儲數(shù)據(jù), 為了更好地顯示使用了開鏈法后鍵值的分布, 修改了showDistor()方法.

重新定義了put(), 將鍵值散列, 散列后的的值對應數(shù)組中的一個位置, 先嘗試將數(shù)據(jù)放在該位置上的數(shù)組中的第一個單元格, 如果該單元格已經有數(shù)據(jù)了, put()方法會搜索下一個位置, 知道找到能放置數(shù)據(jù)的單元格, 并把數(shù)據(jù)存儲進去. 這里實際上可以用this._table[pos].push(data)來代替, 因為通過buildChains()方法已經將散列表中的元素修改為二維數(shù)組(鏈).

get()方法先對鍵值散列, 根據(jù)散列后的值找到散列表中相應的位置, 然后搜索該位置上的鏈, 知道找到鍵值. 如果找到, 就將緊跟在鍵值后面的數(shù)據(jù)返回; 如果沒有, 就返回undefined.

線性探測法

第二種處理碰撞的方法是 線性探測法 . 線性探測法隸屬于一種更一般化的散列技術: _開放尋址散列_. 當發(fā)生碰撞時, 線性探測法檢查散列表中的下一個位置是否為空. 如果為空, 就將數(shù)據(jù)存入該位置; 如果不為空, 則繼續(xù)查找下一個位置, 知道找到一個空的為止. 該技術是基于這樣一個事實: 每個散列表都會有很多空的單元格, 可以使用他們來存儲數(shù)據(jù).

當存儲數(shù)據(jù)使用的數(shù)組特別大時, 選擇線性探測法要比開鏈法好. 這里有個公式, 常常可以幫助我們選擇使用哪種碰撞解決辦法: 如果數(shù)組的大小事帶存儲數(shù)據(jù)個數(shù)的1.5倍, 那么使用開鏈法; 如果數(shù)組的大小是待存儲數(shù)據(jù)的兩倍及兩倍以上時, 那么使用線性探測法.

為了說明線性探測法的工作原理, 可以重寫put()和get()方法. 為了實現(xiàn)一個真實的數(shù)據(jù)存取系統(tǒng), 需要為HashTable類增加一個新的數(shù)組, 用來存儲數(shù)據(jù). 數(shù)組_table和_values并行工作, 當將一個鍵值保存到數(shù)組_table中同時將數(shù)據(jù)存入數(shù)組_values中相應的位置上.

在HashTable的構造函數(shù)中加入下面一行代碼:

this._values = [];

在put()方法中使用線性探測技術:

...
put(key, data) {
    let pos = this._betterHash(key);
    
    if(this._table[pos] == undefined) {
        this._table[pos] = key;
        this._values[pos] = data;
    } else {
        while(this._table[pos] != undefined) {
            pos++
        };
        this._table[pos] = key;
        this._values[pos] = data;
    }
}
...

get()方法先搜索鍵在散列表中的位置, 如果找到, 則返回數(shù)組_values中對應位置上的數(shù)據(jù); 如果沒有找到, 則循環(huán)搜索, 知道找到對應的鍵或者數(shù)組中的單元為undefined時, 后者表示該鍵沒有被存入散列表中.

...
get(key) {
    let hash = -1;
    hash = this._betterHash(key);

    if(hash > -1) {
        for(let i = hash; this._table[hash] != undefined; i++) {

            if(this._table[i] === key) {
                return this._values[i];
            };
        }
    };

    return undefined;
}
...

GPU云服務器云服務器散列存儲結構散列散列函數(shù) 散列類型

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/98183.html

程序員修仙之路--把用戶訪問記錄優(yōu)化到極致

摘要：散列表用的是數(shù)組支持按照下標隨機訪問數(shù)據(jù)的特性，所以散列表其實就是數(shù)組的一種擴展，由數(shù)組演化而來。我們可以把它定義成，其中表示元素的鍵值，的值表示經過散列函數(shù)計算得到的散列值。 showImg(https://segmentfault.com/img/remote/1460000018521371?w=833&h=1096); 祝愿大家不要像菜菜這般苦逼，年中獎大大滴在沒有年終獎的日子...

shevy 2019-08-16 15:48 評論0 收藏0
Python--Redis實戰(zhàn)：第三章：Redis命令：第四節(jié)：散列

摘要：實例導入包包與本地進行鏈接，地址為，端口號為和字符串一樣，對散列中一個尚未存在的鍵執(zhí)行自增操作時，會將鍵的值當作來處理。上一篇文章：Python--Redis實戰(zhàn)：第三章：Redis命令：第三節(jié)：集合下一篇文章：Python--Redis實戰(zhàn)：第三章：Redis命令：第五節(jié)：有序集合第一章提到過，Redis的散列可以讓用戶將多個鍵值對存儲到一個Redis里面。從功能上來說，Red...

waterc 2019-07-31 11:15 評論0 收藏0
js數(shù)據(jù)結構和算法（五）字典和散列（hash）

摘要：哈希表也是種數(shù)據(jù)結構，它可以提供快速的插入操作和查找操作。一個更好的散列函數(shù)為了避免碰撞，首先要確保散列表中用來存儲數(shù)據(jù)的數(shù)組其大小是個質數(shù)，這和計算散列值時使用的取余運算有關。散列函數(shù)將學生里的數(shù)字相加，使用函數(shù)計算出散列值。什么是字典結構？字典是以鍵值對形式存儲數(shù)據(jù)的數(shù)據(jù)結構，就像電話號碼薄里的名字和電話號碼那樣的一一對應的關系。 javascript的Object類就是以...

Hegel_Gu 2019-08-21 10:23 評論0 收藏0