广告：宝塔服务器面板，一键全能部署及管理，送你10850元礼包，点我领取~~~

本篇文章给大家带来了关于javascript中的相关知识，其中主要介绍了关于JavaScript怎么实现哈希表的相关问题，对最终数据插入的数组进行整个结构的封装，得到的就是哈希表，希望对大家有帮助。

相关推荐：javascript学习教程

解决冲突常见的两种方案：

如下图所示，我们将每一个数字都对10进行取余操作，则余数的范围0~9作为数组的下标值。并且，数组每一个下标值对应的位置存储的不再是一个数字了，而是存储由经过取余操作后得到相同余数的数字组成的数组或链表。

总结：链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据，而是一条链条，这条链条常使用的数据结构为数组或链表，两种数据结构查找的效率相当（因为链条的元素一般不会太多）。

开放地址法的主要工作方式是寻找空白的单元格来放置冲突的数据项。

据探测空白单元格位置方式的不同，可分为三种方法：

可以看到随着装填因子的增加，平均探测长度呈线性增长，较为平缓。在开发中使用链地址法较多，比如Java中的HashMap中使用的就是链地址法。

哈希表的优势在于它的速度，所以哈希函数不能采用消耗性能较高的复杂算法。提高速度的一个方法是在哈希函数中尽量减少乘法和除法。

性能高的哈希函数应具备以下两个优点：

霍纳法则：在中国霍纳法则也叫做秦九韶算法，具体算法为：

求多项式的值时，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值。这种算法把求n次多项式f(x)的值就转化为求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学习教程

以上就是详细介绍JavaScript怎么实现哈希表的详细内容，更多请关注9543建站博客其它相关文章！