本篇文章為大家帶來了關於javascript中的相關知識，其中主要介紹了關於JavaScript怎麼實現哈希表的相關問題，對最終資料插入的數組進行整個結構的封裝，得到的就是哈希表，希望對大家有幫助。
相關推薦：javascript學習教學
解決衝突常見的兩個方案：
如下圖所示，我們將每一個數字都對10進行取餘運算，則餘數的範圍0~9作為數組的下標值。並且，數組每一個下標值對應的位置存儲的不再是一個數字了，而是存儲由經過取餘操作後得到相同餘數的數字組成的數組或鍊錶。
總結：鏈結位址法解決衝突的方法是每個陣列單元中儲存的不再是單一資料，而是一條鏈條，這條鏈條常使用的資料結構為陣列或鍊錶，兩種資料結構查找的效率相當（因為鏈條的元素一般不會太多）。
#開放位址法的主要運作方式是尋找空白的儲存格來放置衝突的資料項。
依據探測空白單元格位置方式的不同，可分為三種方法：
鏈結位址法。
優秀的雜湊函數雜湊表的優點在於它的速度，所以雜湊函數不能採用消耗效能較高的複雜演算法。提高速度的一個方法是在雜湊函數中盡量減少乘法和除法。
效能高的雜湊函數應具備以下兩個優點：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:
After transformation:
If big O is used to represent the time complexity, it will directly drop from O(N2) before transformation to O(N).
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中文網其他相關文章！
