JavaScript数据结构——字典和散列表的实现

  • 时间:
  • 浏览:0
  • 来源:大发时时彩官网_大发时时彩邀请码_大发时时彩娱乐平台

  在前一篇文章中,大伙介绍了何如在JavaScript中实现集合。字典和集合的主要区别就在于,集合中数据是以[值,值]的形式保存的,大伙只关心值本身;而在字典和散列表中数据是以[键,值]的形式保存的,键只有重复,大伙不仅关心键,也关心键所对应的值。

  大伙还可否只有把字典称之为映射表。可能字典和集合很同类,大伙能只有在前一篇文章中的集合类Set的基础上来实现大伙的字典类Dictionary。与Set类同类,ES6的原生Map类可能实现了字典的完全功能,稍后大伙会介绍它的用法。

  下面是大伙的Dictionary字典类的实现代码:

class Dictionary {
    constructor () {
        this.items = {};
    }

    set (key, value) { // 向字典中再加或修改元素
        this.items[key] = value;
    }

    get (key) { // 通过键值查找字典中的值
        return this.items[key];
    }

    delete (key) { // 通过使用键值来从字典中删除对应的元素
        if (this.has(key)) {
            delete this.items[key];
            return true;
        }
        return false;
    }

    has (key) { // 判断给定的键值与否处于于字典中
        return this.items.hasOwnProperty(key);
    }

    clear() { // 清空字典内容
        this.items = {};
    }

    size () { // 返回字典中所有元素的数量
        return Object.keys(this.items).length;
    }

    keys () { // 返回字典中所有的键值
        return Object.keys(this.items);
    }

    values () { // 返回字典中所有的值
        return Object.values(this.items);
    }

    getItems () { // 返回字典中的所有元素
        return this.items;
    }
}

  与Set类很同类,然后 我把其中value的累积替再加了key。大伙来看看你这一 测试用例:

let Dictionary = require('./dictionary');

let dictionary = new Dictionary();
dictionary.set('Gandalf', 'gandalf@email.com');
dictionary.set('John', 'john@email.com');
dictionary.set('Tyrion', 'tyrion@email.com');
console.log(dictionary.has('Gandalf')); // true
console.log(dictionary.size()); // 3
console.log(dictionary.keys()); // [ 'Gandalf', 'John', 'Tyrion' ]
console.log(dictionary.values()); // [ 'gandalf@email.com', 'john@email.com', 'tyrion@email.com' ]
console.log(dictionary.get('Tyrion')); // tyrion@email.com

dictionary.delete('John');
console.log(dictionary.keys()); // [ 'Gandalf', 'Tyrion' ]
console.log(dictionary.values()); // [ 'gandalf@email.com', 'tyrion@email.com' ]
console.log(dictionary.getItems()); // { Gandalf: 'gandalf@email.com', Tyrion: 'tyrion@email.com' }

  相应地,下面是使用ES6的原生Map类的测试结果:

let dictionary = new Map();
dictionary.set('Gandalf', 'gandalf@email.com');
dictionary.set('John', 'john@email.com');
dictionary.set('Tyrion', 'tyrion@email.com');
console.log(dictionary.has('Gandalf')); // true
console.log(dictionary.size); // 3
console.log(dictionary.keys()); // [Map Iterator] { 'Gandalf', 'John', 'Tyrion' }
console.log(dictionary.values()); // [Map Iterator] { 'gandalf@email.com', 'john@email.com', 'tyrion@email.com' }
console.log(dictionary.get('Tyrion')); // tyrion@email.com

dictionary.delete('John');
console.log(dictionary.keys()); // [Map Iterator] { 'Gandalf', 'Tyrion' }
console.log(dictionary.values()); // [Map Iterator] { 'gandalf@email.com', 'tyrion@email.com' }
console.log(dictionary.entries()); // [Map Iterator] { [ Gandalf: 'gandalf@email.com' ], [ Tyrion: 'tyrion@email.com' ] }

  和前面大伙自定义的Dictionary类稍微有你这一 不同,values()最好的措施和keys()最好的措施返回的都不 另两个 数组,然后 我Iterator迭代器。然后 我然后 我这里的size是另两个 属性而都不 最好的措施,有刚刚然后 我Map类没办法 getItems()最好的措施,取而代之的是entries()最好的措施,它返回的也是另两个 Iterator。有关Map类的完全完全介绍能只有查看这里。

  在ES6中,除了原生的Set和Map类外,还有它们的弱化版本,分别是WeakSet和WeakMap,大伙在《JavaScript数据社会形态——栈的实现与应用》一文中可能见过WeakMap的使用了。Map和Set与它们个人的弱化版本之间的主要区别是:

  • WeakSet或WeakMap类没办法 entries、keys和values等迭代器最好的措施,只有通过get和set最好的措施访问和设置其中的值。这也是为什大伙在《JavaScript数据社会形态——栈的实现与应用》一文中要使用WeakMap类来定义类的私有属性的由于。
  • 只有用对应作为键值,可能说其中的内容只有是对象,而只有是数字、字符串、布尔值等基本数据类型。

  弱化的Map和Set类主然后 我为了提供JavaScript代码的性能。

散列表

  散列表(可能叫哈希表),是本身改进的dictionary,它将key通过另两个 固定的算法(散列函数或哈希函数)得出另两个 数字,有刚刚将dictionary中key所对应的value存放上去你这一 数字所对应的数组下标所含高的存储空间中。在原始的dictionary中,可能要查找某个key所对应的value,大伙都要遍历整个字典。为了提高查询的带宽,大伙将key对应的value保存到数组里,有刚刚我key不变,使用相同的散列函数计算出来的数字然后 我固定的,于是就能只有减慢地在数组中找到你不会查找的value。下面是散列表的数据社会形态示意图:

  下面是大伙散列函数loseloseHashCode()的实现代码:

loseloseHashCode (key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
        hash += key.charCodeAt(i);
    }
    return hash % 37;
}

  你这一 散列函数的实现很简单,大伙将传入的key中的每另两个 字符使用charCodeAt()函数(有关该函数的完全内容能只有查看这里)将其转再加ASCII码,有刚刚将什么ASCII码相加,最后用37求余,得到另两个 数字,你这一 数字然后 我你这一 key所对应的hash值。接下来要做的然后 我将value存放上去hash值所对应的数组的存储空间内。下面是大伙的HashTable类的主要实现代码:

class HashTable {
    constructor () {
        this.table = [];
    }

    loseloseHashCode (key) { // 散列函数
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    }

    put (key, value) { // 将键值对存放上去哈希表中
        let position = this.loseloseHashCode(key);
        console.log(`${position} - ${key}`);
        this.table[position] = value;
    }

    get (key) { // 通过key查找哈希表中的值
        return this.table[this.loseloseHashCode(key)];
    }

    remove (key) { // 通过key从哈希表中删除对应的值
        this.table[this.loseloseHashCode(key)] = undefined;
    }

    isEmpty () { // 判断哈希表与否为空
        return this.size() === 0;
    }

    size () { // 返回哈希表的长度
        let count = 0;
        this.table.forEach(item => {
            if (item !== undefined) count++;
        });
        return count;
    }

    clear () { // 清空哈希表
        this.table = [];
    }
}

  测试一下上面的什么最好的措施:

let HashTable = require('./hashtable');

let hash = new HashTable();
hash.put('Gandalf', 'gandalf@email.com'); // 19 - Gandalf
hash.put('John', 'john@email.com'); // 29 - John
hash.put('Tyrion', 'tyrion@email.com'); // 16 - Tyrion

console.log(hash.isEmpty()); // false
console.log(hash.size()); // 3
console.log(hash.get('Gandalf')); // gandalf@email.com
console.log(hash.get('Loiane')); // undefined

hash.remove('Gandalf');
console.log(hash.get('Gandalf')); // undefined
hash.clear();
console.log(hash.size()); // 0
console.log(hash.isEmpty()); // true

  为了方便查看hash值和value的对应关系,大伙在put()最好的措施中加入了一行console.log(),用来打印key的hash值和value之间的对应关系。能只有看后,测试的结果和前面大伙给出的示意图是一致的。

  散列集合的实现和散列表同类,只不过在散列集合中不再使用键值对,然后 我只有值没办法 键。你这一 大伙在前面介绍集合和字典的然后可能讲过了,这里不再赘述。

  细心的同学可能可能发现了,这里大伙提供的散列函数可能过于简单,以致于大伙无法保证通过散列函数计算出来的hash值一定是唯一的。换句话说,传入不同的key值,大伙有可能会得到相同的hash值。尝试一下下面什么keys:

let hash = new HashTable();
hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'john@email.com');
hash.put('Tyrion', 'tyrion@email.com');
hash.put('Aaron', 'aaron@email.com');
hash.put('Donnie', 'donnie@email.com');
hash.put('Ana', 'ana@email.com');
hash.put('Jamie', 'jamie@email.com');
hash.put('Sue', 'sue@email.com');
hash.put('Mindy', 'mindy@email.com');
hash.put('Paul', 'paul@email.com');
hash.put('Nathan', 'nathan@email.com');

  从结果中能只有看后,尽管你这一 keys不同,有刚刚通过大伙提供的散列函数岂都不 得到了相同的hash值,这显然违背了大伙的设计原则。在哈希表中,你这一 叫做散列冲突,为了得到另两个 可靠的哈希表,大伙都要尽可能地外理散列冲突。那何如外理你这一 冲突呢?这里介绍本身外理冲突的最好的措施:分离链接和线性探查。

分离链接

   所谓分离链接,然后 我将然后 我存储在哈希表中的值改成链表,然后 我在哈希表的同另两个 位置上,就能只有存储多个不同的值。链表中的每另两个 元素,一块儿存储了key和value。示意图如下:

  然后 我,当不同的key通过散列函数计算出相同的hash值时,大伙只都要找到数组中对应的位置,有刚刚往其中的链表再加新的节点即可,从而有效地外理了散列冲突。为了实现你这一 数据社会形态,大伙都要定义另两个 新的辅助类ValuePair,它的内容如下:

let ValuePair = function (key, value) {
  this.key = key;
  this.value = value;

  this.toString = function () { // 提供toString()最好的措施以方便大伙测试
      return `[${this.key} - ${this.value}]`;
  }
};

  ValuePair类具有另两个 属性,key和value,用来保存大伙要存入到散列表中的元素的键值对。toString()最好的措施在这里都从从不的,该最好的措施是为了上面大伙方便测试。

  新的采用了分离链接的HashTableSeparateChaining类能只有继承自前面的HashTable类,完全的代码如下:

class HashTableSeparateChaining extends HashTable {
    constructor () {
        super();
    }

    put (key, value) {
        let position = this.loseloseHashCode(key);

        if (this.table[position] === undefined) {
            this.table[position] = new LinkedList(); // 单向链表,都要引入LinkedList类
        }
        this.table[position].append(new ValuePair(key, value));
    }

    get (key) {
        let position = this.loseloseHashCode(key);

        if (this.table[position] !== undefined) {
            let current = this.table[position].getHead();
            while (current) {
                if (current.element.key === key) return current.element.value;
                current = current.next;
            }
        }
        return undefined;
    }

    remove (key) {
        let position = this.loseloseHashCode(key);
        let hash = this.table[position];

        if (hash !== undefined) {
            let current = hash.getHead();
            while (current) {
                if (current.element.key === key) {
                    hash.remove(current.element);
                    if (hash.isEmpty()) this.table[position] = undefined;
                    return true;
                }
                current = current.next;
            }
        }

        return false;
    }

    size () {
        let count = 0;
        this.table.forEach(item => {
            if (item !== undefined) count += item.size();
        });
        return count;
    }

    toString() {
        let objString = "";
        for (let i = 0; i < this.table.length; i++) {
            let ci = this.table[i];
            if (ci === undefined) continue;

            objString += `${i}: `;
            let current = ci.getHead();
            while (current) {
                objString += current.element.toString();
                current = current.next;
                if (current) objString += ', ';
            }
            objString += '\r\n';
        }
        return objString;
    }
}

  其中的LinkedList类为单向链表,具体内容能只有查看《JavaScript数据社会形态——链表的实现与应用》。注意,现在hash数组中的每另两个 元素都不 另两个 单向链表,单向链表的所有操作大伙能只有借有助LinkedList类来完成。大伙重写了size()最好的措施,可能现在要计算的是数组中所有链表的长度总和。

  下面是HashTableSeparateChaining类的测试用例及结果:

let hash = new HashTableSeparateChaining();

hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'john@email.com');
hash.put('Tyrion', 'tyrion@email.com');
hash.put('Aaron', 'aaron@email.com');
hash.put('Donnie', 'donnie@email.com');
hash.put('Ana', 'ana@email.com');
hash.put('Jamie', 'jamie@email.com');
hash.put('Sue', 'sue@email.com');
hash.put('Mindy', 'mindy@email.com');
hash.put('Paul', 'paul@email.com');
hash.put('Nathan', 'nathan@email.com');

console.log(hash.toString());
console.log(`size: ${hash.size()}`);
console.log(hash.get('John'));

console.log(hash.remove('Ana'));
console.log(hash.remove('John'));
console.log(hash.toString());

  能只有看后,结果和上面示意图上给出的是一致的,size()、remove()和get()最好的措施的执行结果也符合预期。

线性探查

  外理散列冲突的另本身最好的措施是线性探查。当向哈希数组中再加某另两个 新元素时,可能该位置上可能有数据了,就继续尝试下另两个 位置,直到对应的位置上没办法 数据时,就在该位置上再加数据。大伙将上面的例子改成线性探查的最好的措施,存储结果如下图所示:

  现在大伙不都要单向链表LinkedList类了,有刚刚ValuePair类仍然是都要的。同样的,大伙的HashTableLinearProbing类继承自HashTable类,完全的代码如下:

class HashTableLinearProbing extends HashTable {
    constructor () {
        super();
    }

    put (key, value) {
        let position = this.loseloseHashCode(key);

        if (this.table[position] === undefined) {
            this.table[position] = new ValuePair(key, value);
        }
        else {
            let index = position + 1;
            while (this.table[index] !== undefined) {
                index ++;
            }
            this.table[index] = new ValuePair(key, value);
        }
    }

    get (key) {
        let position = this.loseloseHashCode(key);

        if (this.table[position] !== undefined) {
            if (this.table[position].key === key) return this.table[position].value;
            let index = position + 1;
            while (this.table[index] !== undefined && this.table[index].key === key) {
                index ++;
            }
            return this.table[index].value;
        }
        return undefined;
    }

    remove (key) {
        let position = this.loseloseHashCode(key);

        if (this.table[position] !== undefined) {
            if (this.table[position].key === key) {
                this.table[position] = undefined;
                return true;
            }
            let index = position + 1;
            while (this.table[index] !== undefined && this.table[index].key !== key) {
                index ++;
            }
            this.table[index] = undefined;
            return true;
        }
        return false;
    }

    toString() {
        let objString = "";
        for (let i = 0; i < this.table.length; i++) {
            let ci = this.table[i];
            if (ci === undefined) continue;

            objString += `${i}: ${ci}\r\n`;
        }
        return objString;
    }
}

  使用上面和HashTableSeparateChaining类相同的测试用例,大伙来看看测试结果:

  能只有和HashTableSeparateChaining类的测试结果比较一下,多出来的位置6、14、17、33,正是HashTableSeparateChaining类中每另两个 链表的剩余累积。get()和remove()最好的措施还可否正常工作,大伙不都要重写size()最好的措施,和基类HashTable中一样,hash数组中每另两个 位置只保存了另两个 元素。然后 我要注意的地方是,可能JavaScript中定义数组时不都要提前给出数组的长度,有刚刚大伙能只有很容易地利用JavaScript语言的你这一 社会形态来实现线性探查。在你这一 编程语言中,数组的定义是都要明确给出长度的,这时大伙就都要重新考虑大伙的HashLinearProbing类的实现了。

  loseloseHashCode()散列函数并都不 另两个 表现良好的散列函数,正如你所看后的,它会很轻易地产生散列冲突。另两个 表现良好的散列函数都要还可否尽可能低地减少散列冲突,并提高性能。大伙能只有在网上找你这一 不同的散列函数的实现最好的措施,下面是另两个 比loseloseHashCode()更好的散列函数djb2HashCode():

djb2HashCode (key) {
    let hash = 5381;
    for (let i = 0; i < key.length; i++) {
        hash = hash * 33 + key.charCodeAt(i);
    }
    return hash % 1013;
}

  大伙用相同的测试用例来测试dj2HashCode(),下面是测试结果:

  这次没办法 冲突!然而这并都不 最好的散列函数,但它是社区最推崇的散列函数之一。

  下一章大伙将介绍何如用JavaScript来实现树。

猜你喜欢

cnblogs客户端配置说明

1.下载地址http://openlivewriter.org/2.安装安装时设置好blog地址和账户、密码:到这里基本上就算安装完成了。因为以前的自动配置这么成功,会出显1个

2019-12-06

炉石传说术士卡组 炉石传说术士卡组该怎么搭配

术士卡组作为炉石传说中较为热门的卡组,尤其是当战士卡组被削之前 又有成为大热门的趋势,可是我我当然拥有可是我我种搭配方法 ,今天小编为我们歌词 我们歌词 介绍一下比较

2019-12-06

闹闹天宫嫦娥厉害吗 闹闹天宫嫦娥玩法介绍

斗玩网(douwan.com)报道:闹闹天宫嫦娥厉害吗?在游戏中,嫦娥定位暂且辅助就是dps,嫦娥有着非常不错的输出能力,感兴趣的男友一起去来看看闹闹天宫嫦娥玩法介绍。闹闹天宫

2019-12-06

对标三星 摩托罗拉将推1500美元折叠式手机

【环球网科技报道记者张之颖】最新消息指出,摩托罗拉将推出此人 的折叠式智能手机。一项可追溯到8月的专利显示,联想正致力于研发折叠式屏幕的技术。据了解,联想表示计划出售8万台摩

2019-12-06

魔幻三杰2 v1.14升级档+破解补丁[RELOADED]

关于大伙  |  加入大伙  |  意见反馈  |  招聘信息  |  商务合作|  游戏库列表温馨提示,适度游戏益脑,沉迷游戏伤身,合理安排时间,享受健康生活本站所有游戏均来

2019-12-06