數據結構-散列

lei___ 發布于2019-08-23 12:15 / 2348人閱讀

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

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

散列概覽

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

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

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

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

HashTable類

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

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

    }
    showDistro() {

    }
    put() {
        
    }
}

選擇一個散列函數

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

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

乍一看, 將字符串中的每個字符的ASCII碼值相加似乎是一個不錯的散列函數. 這樣散列值就是ASCII碼值的和除以數組長度的余數. 該散列的方法_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(), 一個用來將數據存入散列表, 一個用來顯示散列表中的數據, 這樣就初步實現了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()函數通過使用JS的charCodeAt()函數, 返回每個字符的ASCII碼值, 然后再將它們相加得到散列值. put()方法通過調用_simpleHash()函數得到數組的索引, 然后將數據存儲到該索引對應的位置上. 你會發現, 數據并不是均勻分布的, 人名想數組的兩端集中.

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

一個更好的散列函數

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

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

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

散裂化整型鍵

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

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()函數時, 可以指定隨機數的最大值和最小值. 拿學生成績來說, 最低分50, 最高分100.

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

執行程序:

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

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

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()的散列效果都更勝一籌.

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

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

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

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

碰撞處理

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

開鏈法

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

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

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

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

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

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

線性探測法

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

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

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

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

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()方法先搜索鍵在散列表中的位置, 如果找到, 則返回數組_values中對應位置上的數據; 如果沒有找到, 則循環搜索, 知道找到對應的鍵或者數組中的單元為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云服務器云服務器散列存儲結構散列散列函數散列類型

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

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

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

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

shevy 2019-08-16 15:48 評論0 收藏0
Python--Redis實戰：第三章：Redis命令：第四節：散列

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

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

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

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