首页 > 代码库 > 使用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模拟常见数据结构(三)