JavaScript實(shí)現(xiàn)哈希表的方法

本篇內(nèi)容主要講解“JavaScript實(shí)現(xiàn)哈希表的方法”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“JavaScript實(shí)現(xiàn)哈希表的方法”吧!

哈希表通常是基于數(shù)組進(jìn)行實(shí)現(xiàn)的，但是相對(duì)于數(shù)組，它有很多優(yōu)勢：

1. 它可以提供非?？焖俚牟迦?刪除-查找操作

2. 無論多少數(shù)據(jù)，插入和刪除需要接近常量的時(shí)間：即O(1)的時(shí)間級(jí)。實(shí)際上，只需要幾個(gè)機(jī)器指令即可完成。

3. 哈希表的速度比樹還要快，基本可以瞬間查找到想要的元素

4. 哈希表相對(duì)于樹來說編碼要容易很多

哈希表相對(duì)于數(shù)組的一些不足：

1. 哈希表中的數(shù)據(jù)是沒有順序的，所以不能以一種固定的方式來遍歷其中的元素

2. 通常情況下，哈希表中的key是不允許重復(fù)的，不能放置相同的key，用于保存不同的元素

3. 空間利用率不高，底層使用的是數(shù)組，并且某些單元格沒有被利用

哈希表是什么？

• 哈希表并不好理解，不像數(shù)組、鏈表和樹等可通過圖形的形式表示其結(jié)構(gòu)和原理。

• 哈希表的結(jié)構(gòu)就是數(shù)組，但它神奇之處在于對(duì)下標(biāo)值的一種變換，這種變換我們可以稱之為哈希函數(shù)，通過哈希函數(shù)可以獲取HashCode。

哈希表的一些概念

• 哈?；?strong>將大數(shù)字轉(zhuǎn)化成數(shù)組范圍內(nèi)下標(biāo)的過程，稱之為哈?；?/strong>；

• 哈希函數(shù)：我們通常會(huì)將單詞轉(zhuǎn)化成大數(shù)字，把大數(shù)字進(jìn)行哈?；?/strong>的代碼實(shí)現(xiàn)放在一個(gè)函數(shù)中，該函數(shù)就稱為哈希函數(shù)；

• 哈希表：對(duì)最終數(shù)據(jù)插入的數(shù)組進(jìn)行整個(gè)結(jié)構(gòu)的封裝，得到的就是哈希表。

仍然需要解決的問題：

• 哈?；^后的下標(biāo)依然可能重復(fù)，如何解決這個(gè)問題呢？這種情況稱為沖突，沖突是不可避免的，我們只能解決沖突。

解決沖突的方法

解決沖突常見的兩種方案：

• 方案一：鏈地址法（拉鏈法）；

如下圖所示，我們將每一個(gè)數(shù)字都對(duì)10進(jìn)行取余操作，則余數(shù)的范圍0~9作為數(shù)組的下標(biāo)值。并且，數(shù)組每一個(gè)下標(biāo)值對(duì)應(yīng)的位置存儲(chǔ)的不再是一個(gè)數(shù)字了，而是存儲(chǔ)由經(jīng)過取余操作后得到相同余數(shù)的數(shù)字組成的數(shù)組或鏈表。

總結(jié)：鏈地址法解決沖突的辦法是每個(gè)數(shù)組單元中存儲(chǔ)的不再是單個(gè)數(shù)據(jù)，而是一條鏈條，這條鏈條常使用的數(shù)據(jù)結(jié)構(gòu)為數(shù)組或鏈表，兩種數(shù)據(jù)結(jié)構(gòu)查找的效率相當(dāng)（因?yàn)殒湕l的元素一般不會(huì)太多）。

• 方案二：開放地址法；

開放地址法的主要工作方式是尋找空白的單元格來放置沖突的數(shù)據(jù)項(xiàng)。

據(jù)探測空白單元格位置方式的不同，可分為三種方法：

• 線性探測

• 二次探測

• 再哈希法

可以看到隨著裝填因子的增加，平均探測長度呈線性增長，較為平緩。在開發(fā)中使用鏈地址法較多，比如Java中的HashMap中使用的就是鏈地址法。

優(yōu)秀的哈希函數(shù)

哈希表的優(yōu)勢在于它的速度，所以哈希函數(shù)不能采用消耗性能較高的復(fù)雜算法。提高速度的一個(gè)方法是在哈希函數(shù)中盡量減少乘法和除法。

性能高的哈希函數(shù)應(yīng)具備以下兩個(gè)優(yōu)點(diǎn)：

• 快速的計(jì)算；

• 均勻的分布；

快速計(jì)算

霍納法則：在中國霍納法則也叫做秦九韶算法，具體算法為：

求多項(xiàng)式的值時(shí)，首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值，然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值。這種算法把求n次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值。

變換之前：

• 乘法次數(shù)：n（n+1）/2次；

• 加法次數(shù)：n次；

變換之后：

• 乘法次數(shù)：n次；

• 加法次數(shù)：n次；

如果使用大O表示時(shí)間復(fù)雜度的話，直接從變換前的O(N2)降到了O(N)。

均勻分布

為了保證數(shù)據(jù)在哈希表中均勻分布，當(dāng)我們需要使用常量的地方，盡量使用質(zhì)數(shù)；比如：哈希表的長度、N次冪的底數(shù)等。

Java中的HashMap采用的是鏈地址法，哈?；捎玫氖枪綖椋?strong>index = HashCode（key）&（Length-1）

即將數(shù)據(jù)化為二進(jìn)制進(jìn)行與運(yùn)算，而不是取余運(yùn)算。這樣計(jì)算機(jī)直接運(yùn)算二進(jìn)制數(shù)據(jù)，效率更高。但是JavaScript在進(jìn)行叫大數(shù)據(jù)的與運(yùn)算時(shí)會(huì)出現(xiàn)問題，所以以下使用JavaScript實(shí)現(xiàn)哈?；瘯r(shí)還是采用取余運(yùn)算。

                    function HashTable() {
                // 存放相關(guān)的元素
                this.storage = [];
                // 存了多少數(shù)據(jù)
                this.count = 0;
                // 用于標(biāo)記數(shù)組中一共存放了多少個(gè)元素
                this.limit = 7;
                /*
           設(shè)計(jì)哈希函數(shù)
           ①將字符串轉(zhuǎn)成比較大的數(shù)字
           ②將大的數(shù)字hashCode壓縮到數(shù)組范圍之內(nèi)
            */
                HashTable.prototype.hashFunction = function (str, size) {
                    var hashCode = 0;
                    //秦九韶算法（霍納算法）
                    // 哈希表的長度、N次冪的底數(shù)等盡量選取質(zhì)數(shù)
                    for (var i = 0; i < str.length; i++) {
                        // 34 43 43 都是常用的底數(shù)
                        hashCode = 37 * hashCode + str.charCodeAt(i);
                    }
                    return hashCode % size;
                };
                // 插入和修改方法
                HashTable.prototype.put = function (key, value) {
                    // 根據(jù)key獲取對(duì)應(yīng)的index
                    var index = this.hashFunction(key, this.limit);
                    // 根據(jù)index取出對(duì)應(yīng)的bucket
                    var bucket = this.storage[index];
                    if (bucket == null) {
                        bucket = [];
                        this.storage[index] = bucket;
                    }
                    // 判斷是否是修改數(shù)據(jù)
                    for (var i = 0; i < bucket.length; i++) {
                        var tuple = bucket[i];
                        if (tuple[0] === key) {
                            tuple[1] == value;
                            return;
                        }
                    }
                    // 不是修改數(shù)據(jù)就添加數(shù)據(jù)
                    bucket.push([key, value]);
                    this.count++;
                    // 擴(kuò)容
                    if (this.count > this.limit * 0.75) {
                        var newLimit = this.limit * 2;
                        var prime = this.getPrime(newLimit);
                        this.resize(prime);
                    }
                };
                // 獲取
                HashTable.prototype.get = function (key) {
                    var index = this.hashFunction(key, this.limit);
                    var bucket = this.storage[index];
                    if (bucket == null) return null;
                    for (var i = 0; i < bucket.length; i++) {
                        var tuple = bucket[i];
                        if (tuple[0] === key) {
                            value == tuple[1];
                            return value;
                        }
                    }
                    return null;
                };
                // 刪除
                HashTable.prototype.remove = function (key) {
                    var index = this.hashFunction(key, this.limit);
                    var bucket = this.storage[index];
                    if (bucket == null) return null;
                    for (var i = 0; i < bucket.length; i++) {
                        var tuple = bucket[i];
                        if (tuple[0] === key) {
                            // 從i開始刪除一個(gè)
                            bucket.splice(i, 1);
                            this.count--;
                            // 縮容
                            if (this.limit > 7 && this.count < this.limit * 0.25) {
                                var newLimit = Math.floor(this.limit / 2);
                                var prime = this.getPrime(newLimit);
                                this.resize(prime);
                            }
                            return tuple[1];
                        }
                    }
                    return null;
                };
                // 擴(kuò)容
                HashTable.prototype.resize = function (newLimit) {
                    var oldStorage = this.storage;
                    // 充值所有的屬性
                    this.storage = [];
                    this.count = 0;
                    this.limit = newLimit;
                    for (var i = 0; i < this.limit; i++) {
                        var bucket = oldStorage[i];
                        if (bucket == null) {
                            continue;
                        }
                        for (var j = 0; j < bucket.length; j++) {
                            var tuple = bucket[j];
                            this.put(tuple[0], tuple[1]);
                        }
                    }
                };
                // 為空？
                HashTable.prototype.isEmpty = function () {
                    return this.count > 0 ? false : true;
                };
                // size
                HashTable.prototype.size = function () {
                    return this.count;
                };
                // toString
                HashTable.prototype.toString = function () {
                    var str = '';
                    for (var i = 0; i < this.limit; i++) {
                        var arr = this.storage[i];

                        if (arr != undefined) {
                            str += '[';
                            for (var j = 0; j < arr.length; j++) {
                                var bucket = arr[j];

                                str += '[' + bucket[0] + ',' + bucket[1] + ']';
                                if (j != arr.length - 1) {
                                    str += ',';
                                }
                            }
                            str += ']';
                            if (i != this.limit - 1) {
                                str += ',';
                            }
                        } else {
                            str += '[]';
                            if (i != this.limit - 1) {
                                str += ',';
                            }
                        }
                    }

                    return str;
                };
                HashTable.prototype.isPrime = function (num) {
                    if (num <= 1) {
                        return false;
                    }
                    //1.獲取num的平方根:Math.sqrt(num)
                    //2.循環(huán)判斷
                    for (var i = 2; i <= Math.sqrt(num); i++) {
                        if (num % i == 0) {
                            return false;
                        }
                    }
                    return true;
                };

                //獲取質(zhì)數(shù)的方法
                HashTable.prototype.getPrime = function (num) {
                    //7*2=14,+1=15,+1=16,+1=17(質(zhì)數(shù))
                    while (!this.isPrime(num)) {
                        num++;
                    }
                    console.log(num);
                    return num;
                };
            }
            var hashTable = new HashTable();
            hashTable.put('q', 1);
            hashTable.put('w', 1);
            hashTable.put('e', 1);
            hashTable.put('r', 1);
            hashTable.put('t', 1);
            hashTable.put('y', 1);
            hashTable.put('z', 1);
            hashTable.put('x', 1);
            hashTable.put('c', 1);
            hashTable.put('v', 1);
            hashTable.put('b', 1);
            hashTable.put('n', 1);
            hashTable.remove('q');
            console.log(hashTable.toString());//[[w,1]],[[x,1]],[[y,1]],[[z,1]],[],[],[],[],[[n,1]],[],[],[],[[r,1]],[[b,1]],[[t,1],[c,1]],[],[[e,1],[v,1]]

到此，相信大家對(duì)“JavaScript實(shí)現(xiàn)哈希表的方法”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！