js教程_详细介绍JavaScript怎么实现哈希表

相关推荐：javascript学习教程

哈希表通常是基于数组进行实现的，但是相对于数组，它有很多优势：

1. 它可以提供非常快速的插入-删除-查找操作
2. 无论多少数据，插入和删除需要接近常量的时间：即O(1)的时间级。实际上，只需要几个机器指令即可完成。
3. 哈希表的速度比树还要快，基本可以瞬间查找到想要的元素
4. 哈希表相对于树来说编码要容易很多

哈希表相对于数组的一些不足：

1. 哈希表中的数据是没有顺序的，所以不能以一种固定的方式来遍历其中的元素
2. 通常情况下，哈希表中的key是不允许重复的，不能放置相同的key，用于保存不同的元素
3. 空间利用率不高，底层使用的是数组，并且某些单元格没有被利用

哈希表是什么？

• 哈希表并不好理解，不像数组、链表和树等可通过图形的形式表示其结构和原理。
• 哈希表的结构就是数组，但它神奇之处在于对下标值的一种变换，这种变换我们可以称之为哈希函数，通过哈希函数可以获取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学习教程

以上就是详细介绍JavaScript怎么实现哈希表的详细内容，更多请关注zzsucai.com其它相关文章！