詳細介紹JavaScript怎麼實作哈希表

本篇文章為大家帶來了關於javascript中的相關知識，其中主要介紹了關於JavaScript怎麼實現哈希表的相關問題，對最終資料插入的數組進行整個結構的封裝，得到的就是哈希表，希望對大家有幫助。

相關推薦：javascript學習教學

#哈希表通常是基於陣列進行實現的，但是相對於數組，它有很多優點：

1. 它可以提供非常快速的插入-刪除-查找操作
2. 無論多少數據，插入和刪除需要接近常數的時間：即O(1)的時間級。實際上，只需要幾個機器指令即可完成。
3. 哈希表的速度比樹還要快，基本上可以瞬間查找到想要的元素
4. 哈希表相對於樹來說編碼要容易很多

哈希表相對於數組的一些不足：

1. 哈希表中的資料是沒有順序的，所以不能以固定的方式來遍歷其中的元素
2. 通常情況下，哈希表中的key是不允許重複的，不能放置相同的key，用於保存不同的元素
3. 空間利用率不高，底層使用的是數組，並且某些單元格沒有被利用

哈希表是什麼？

• 雜湊表並不好理解，不像陣列、鍊錶和樹等可透過圖形的形式表示其結構和原理。
• 雜湊表的結構就是陣列，但它神奇之處在於對下標值的一種變換，這種變換我們可以稱之為雜湊函數，透過雜湊函數可以取得HashCode。

哈希表的一些概念

• #哈希化：將大數字轉化成數組範圍內下標的過程，稱為哈希化;
• 雜湊函數：我們通常會將單字轉換成大數字，把大數字進行哈希化的程式碼實作放在一個函數中，該函數就稱為雜湊函數;
• 雜湊表：對最終資料插入的陣列進行整個結構的封裝，得到的就是哈希表。

仍然需要解決的問題：

• 哈希化過後的下標仍然可能重複，如何解決這個問題呢？這種情況稱為衝突，衝突是不可避免的，我們只能解決衝突。

解決衝突的方法

解決衝突常見的兩個方案：

• 方案一：連結位址法（拉鍊法）；

如下圖所示，我們將每一個數字都對10進行取餘運算，則餘數的範圍0~9作為數組的下標值。並且，數組每一個下標值對應的位置存儲的不再是一個數字了，而是存儲由經過取餘操作後得到相同餘數的數字組成的數組或鍊錶。

總結：鏈結位址法解決衝突的方法是每個陣列單元中儲存的不再是單一資料，而是一條鏈條，這條鏈條常使用的資料結構為陣列或鍊錶，兩種資料結構查找的效率相當（因為鏈條的元素一般不會太多）。

• 方案二：開放位址法；

#開放位址法的主要運作方式是尋找空白的儲存格來放置衝突的資料項。

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

• ##線性探測
• #二次探測
• 再雜湊法

#可以看到隨著裝置因子的增加，平均探測長度呈線性成長，較為平緩。在開發中使用鏈結位址法較多，例如Java中的HashMap中使用的就是

鏈結位址法。

優秀的雜湊函數

雜湊表的優點在於它的速度，所以雜湊函數不能採用消耗效能較高的複雜演算法。提高速度的一個方法是在雜湊函數中

盡量減少乘法和除法。

效能高的雜湊函數應具備以下兩個優點：

• Fast calculation;
• Uniform distribution;

Quick calculation

Horner's Law: In China, Horner's Law is also called Qin Jiushao's Algorithm. The specific algorithm is:

When finding the value of a polynomial, First, calculate the value of the linear polynomial in the innermost bracket, and then calculate the value of the linear polynomial layer by layer from the inside out. This algorithm converts the value of n degree polynomial f(x) into the value of n degree polynomials.

Before transformation:

• Number of multiplications: n(n 1)/2 times;
• Number of additions: n times;

After transformation:

• Number of multiplications: n times;
• Number of additions: n times;

If big O is used to represent the time complexity, it will directly drop from O(N2) before transformation to O(N).

Uniform distribution

In order to ensure that the data is evenly distributed in the hash table, when we need touse constants, try to use Prime numbers; For example: the length of the hash table, the base of Nth power, etc.

HashMap in Java uses the chain address method, and the hashing method uses the formula: index = HashCode (key) & (Length-1)

That is to say, the data is converted into binary for and operations instead of remainder operation. In this way, the computer directly operates on binary data, which is more efficient. However, JavaScript will have problems when performing and operations called big data, so the remainder operation will still be used when using JavaScript to implement hashing.

                    function HashTable() {
                // 存放相关的元素
                this.storage = [];
                // 存了多少数据
                this.count = 0;
                // 用于标记数组中一共存放了多少个元素
                this.limit = 7;
                /*
           设计哈希函数
           ①将字符串转成比较大的数字
           ②将大的数字hashCode压缩到数组范围之内
            */
                HashTable.prototype.hashFunction = function (str, size) {
                    var hashCode = 0;
                    //秦九韶算法（霍纳算法）
                    // 哈希表的长度、N次幂的底数等尽量选取质数
                    for (var i = 0; i  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  7 && 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 <p></p><p>Related recommendations: <a href="https://www.php.cn/course/list/17.html" target="_blank">javascript learning tutorial</a><br></p>

以上是詳細介紹JavaScript怎麼實作哈希表的詳細內容。更多資訊請關注PHP中文網其他相關文章！