首页 > 代码库 > 使用javascript模拟常见数据结构(三)

使用javascript模拟常见数据结构(三)

六、字典和散列表   

  我们已经知道,集合表示一组互不相同的元素(不重复元素)。在字典中,存储的是键值对,其中键值是用来查询特定的元素的。字典和集合是很相似的,集合采用[值,值]的方式存储,而字典则是以[键,值]的方式来进行存储的。字典也称作映射。

  首先,我们还是用函数来创建一个字典,在es6中新增了map类,其表示的就是字典这种数据结构。

  

function Dictionary(){
     var items = {};      
}

嗯,然后其实还是老规矩,有一些方法来操作这个字典,包括set,remove,has,get,clear等等。

this.has = function(key){
     return key in items;
}
this.set = function(key,value){
    items[key] = value      
}
this.remove = function(key){
    if(this.has(key)){
        delete items[key];
        return true
    }
    return null    
}
this.get = function(){
    return this.has[key]?item[key]:undefined;
}

  嗯,主要就是上述这些方法,其实简单来说就是个对象。。。。

  下面主要来说一下散列表,叫做HashTable或者HashMap,散列表可以明显提高字典的查找速度,简而言之就是它不需要去遍历键。对于没哟个键名,它使用了一种算法来进行编码,编码的值记录了值的地址,嗯,像下面这张图一样。

  技术分享

  嗯,上面这张图是根据键名每个字母的ASCⅡ码的和来进行的,实际情况其实要比这复杂的多。

  然后我们可以根据loselose算法来进行键名和散列值的对应:

  

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

  嗯,这样就变成了下图这个样子了。

  技术分享

  嗯,这样需要的数组的长度就比上面小的多了,并且,如果我们需要查找一个key,那么就可以很容易的通过上面的算法直接找到其对应的值,而不用遍历整个字典了。

  另外,在散列表中大家也可以很容易的想到,如果键名生成了同样的散列值怎么样,比如Tyrion 和Aaron会生成同样的散列值16,这样后输入的键值就会覆盖前面的键值,为了解决这个问题,我们可以使用分离链表来解决。如下图:

  技术分享

  技术分享

  这样在一个散列表的每一个值的位置我们都存储一个链表,就不会发生上面说的那种情况了,这种方法叫做分离链表。

使用javascript模拟常见数据结构(三)