JavaScript -- 散列表（Hash table，也叫哈希表）的JavaScript的描述

╰半夏微凉° 2022-04-17 01:40 235阅读 0赞

散列是一种常用的数据存储技术，散列后的数据可以快速地插入或取用。散列使用的数据结构叫做散列表。

我们的散列表是基于数组进行设计的。数组的长度是预先设定的，如有需要，可以随时增加。所有元素根据和该元素对应的键，保存在数组的特定位置，该键和我们前面讲到的字典中的键是类似的概念。使用散列表存储数据时，通过一个散列函数将键映射为一个数字，这个数字的范围是 0 到散列表的长度。

**对数组大小常见的限制是：数组长度应该是一个质数。（为了减少冲突，碰撞）**

简单的说，就是我们通过一个函数keyHash(x),来计算下标index,将数据存入table\[index\]里面。

this.keyHash = function (data) {//存入的数据，假设为对象
            let sum = 0;
            for (let x of data.keys) {//将keys属性（默认为字符串）的每一个字符的ascii码加起来
                sum += x.charCodeAt();
            }
            return sum%this.table.length;//模table的长度（不能放到外面去） 这就是index(下标)
        };

你有没有发现这里存在一些问题，如果俩个数据的index相同咋办？（取长度为质数的原因就是为了减少这种碰撞，但是不能避免）

重新设计keyHash函数，直到没有冲突？的确这是一个方法，但是数据量大的时候，很难设计出这样的散列函数。

有俩种比较好的方法

1：开链法

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70][]

对于这种方法，我们的table是一个参差不齐数组，每一个位置又是一个数组，可以保存多个数据，很简单。

2：线性探测法

简单的说，就是根据某种规则来寻找下一个空的位置。规则你可以自己选择，我选取最简单，挨个查询下一个位置是否为空。

根据代码，我来介绍第二种方法(你可以自己试试第一种方法）

增数据：

this.put = function (data) {
            let key = this.keyHash(data);//算出index（下标）
            for (let i = 0 ; i<this.table.length ; i++) {//挨个寻找空闲的位置
                if (this.table[(i+key)%this.table.length] == undefined) {
                    this.table[(i+key)%this.table.length] = data;//找到了，就存入
                    break;
                }
            }
        };

取数据：

this.get = function (key) {//key值就是你要寻找数据的keys
            key = key.toString();
            let index = this.keyHash({ "keys": key }); //封装成对象
            for (let i = 0 ; i<this.table.length ; i++) {
                if ( typeof this.table[(i+index)%this.table.length] == 'object' &&
                this.table[(i+index)%this.table.length].keys == key ) {//根据你的规则，寻找数据
                    return this.table[(i+index)%this.table.length];
                }
            }
            return null;
        }

HashTable:

我们来测一下代码吧

![20181111121228496.png][]

很简单吧！你还可以给HashTable添加其他方法

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70]: /images/20220417/a25e7a82bd1d4376b2bfe7f4ac1f1485.png
[20181111121228496.png]: /images/20220417/70e45fc386a74a05bc4aef750d139d04.png