詳細介紹JavaScript怎麼實現雜湊表
2022-03-03 19:01:34
相關推薦：
雜湊表通常是基於陣列進行實現的，但是相對於陣列，它有很多優勢：
- 它可以提供非常快速的插入-刪除-查詢操作
- 無論多少資料，插入和刪除需要接近常數的時間：即O(1)的時間級。實際上，只需要幾個機器指令即可完成。
- 雜湊表的速度比樹還要快，基本可以瞬間查詢到想要的元素
- 雜湊表相對於樹來說編碼要容易很多
雜湊表相對於陣列的一些不足：
- 雜湊表中的資料是沒有順序的，所以不能以一種固定的方式來遍歷其中的元素
- 通常情況下，雜湊表中的key是不允許重複的，不能放置相同的key，用於儲存不同的元素
- 空間利用率不高，底層使用的是陣列，並且某些單元格沒有被利用
雜湊表是什麼？
- 雜湊表並不好理解，不像陣列、連結串列和樹等可通過圖形的形式表示其結構和原理。
- 雜湊表的結構就是陣列，但它神奇之處在於對下標值的一種變換，這種變換我們可以稱之為雜湊函數，通過雜湊函數可以獲取HashCode。
雜湊表的一些概念
- 雜湊化：將大數位轉化成陣列範圍內下標的過程，稱之為雜湊化；
- 雜湊函數：我們通常會將單詞轉化成大數位，把大數位進行雜湊化的程式碼實現放在一個函數中，該函數就稱為雜湊函數；
- 雜湊表：對最終資料插入的陣列進行整個結構的封裝，得到的就是雜湊表。
仍然需要解決的問題：
- 雜湊化過後的下標依然可能重複，如何解決這個問題呢？這種情況稱為衝突，衝突是不可避免的，我們只能解決衝突。
解決衝突的方法
解決衝突常見的兩種方案：
- 方案一：鏈地址法（拉鍊法）；
如下圖所示，我們將每一個數位都對10進行取餘操作，則餘數的範圍0~9作為陣列的下標值。並且，陣列每一個下標值對應的位置儲存的不再是一個數位了，而是儲存由經過取餘操作後得到相同餘數的數位組成的陣列或連結串列。
總結：鏈地址法解決衝突的辦法是每個陣列單元中儲存的不再是單個資料，而是一條鏈條，這條鏈條常使用的資料結構為陣列或連結串列，兩種資料結構查詢的效率相當（因為鏈條的元素一般不會太多）。
- 方案二：開放地址法；
開放地址法的主要工作方式是尋找空白的單元格來放置衝突的資料項。
據探測空白單元格位置方式的不同，可分為三種方法：
- 線性探測
- 二次探測
- 再雜湊法
可以看到隨著裝填因子的增加，平均探測長度呈線性增長，較為平緩。在開發中使用鏈地址法較多，比如Java中的HashMap中使用的就是鏈地址法。
優秀的雜湊函數
雜湊表的優勢在於它的速度，所以雜湊函數不能採用消耗效能較高的複雜演演算法。提高速度的一個方法是在雜湊函數中儘量減少乘法和除法。
效能高的雜湊函數應具備以下兩個優點：
- 快速的計算；
- 均勻的分佈；
快速計算
霍納法則：在中國霍納法則也叫做秦九韶演演算法，具體演演算法為：
求多項式的值時，首先計算最內層括號內一次多項式的值，然後由內向外逐層計算一次多項式的值。這種演演算法把求n次多項式f(x)的值就轉化為求n個一次多項式的值。
變換之前：
- 乘法次數：n（n+1）/2次；
- 加法次數：n次；
變換之後：
- 乘法次數：n次；
- 加法次數：n次；
如果使用大O表示時間複雜度的話，直接從變換前的O(N2)降到了O(N)。
均勻分佈
為了保證資料在雜湊表中均勻分佈，當我們需要使用常數的地方，儘量使用質數；比如：雜湊表的長度、N次冪的底數等。
Java中的HashMap採用的是鏈地址法，雜湊化採用的是公式為：index = HashCode（key）&（Length-1）
即將資料化為二進位制進行與運算，而不是取餘運算。這樣計算機直接運算二進位制資料，效率更高。但是JavaScript在進行叫巨量資料的與運算時會出現問題，所以以下使用JavaScript實現雜湊化時還是採用取餘運算。
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 < str.length; i++) {
// 34 43 43 都是常用的底數
hashCode = 37 * hashCode + str.charCodeAt(i);
}
return hashCode % size;
};
// 插入和修改方法
HashTable.prototype.put = function (key, value) {
// 根據key獲取對應的index
var index = this.hashFunction(key, this.limit);
// 根據index取出對應的bucket
var bucket = this.storage[index];
if (bucket == null) {
bucket = [];
this.storage[index] = bucket;
}
// 判斷是否是修改資料
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i];
if (tuple[0] === key) {
tuple[1] == value;
return;
}
}
// 不是修改資料就新增資料
bucket.push([key, value]);
this.count++;
// 擴容
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開始刪除一個
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;
};
// 擴容
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.迴圈判斷
for (var i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
};
//獲取質數的方法
HashTable.prototype.getPrime = function (num) {
//7*2=14,+1=15,+1=16,+1=17(質數)
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]]
相關推薦：
以上就是詳細介紹JavaScript怎麼實現雜湊表的詳細內容，更多請關注TW511.COM其它相關文章！