首页 » 学习JavaScript数据结构与算法(第2版) » 学习JavaScript数据结构与算法(第2版)全文在线阅读

《学习JavaScript数据结构与算法(第2版)》7.1 字典

关灯直达底部

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

在本章中,我们会介绍几个在现实问题上使用字典数据结构的例子:一个实际的字典(单词和它们的释义)以及一个地址簿。

7.1.1 创建字典

Set类相似,ECMAScript 6同样包含了一个Map类的实现,即我们所说的字典。

我们在本章中将要实现的类就是以ECMAScript 6中Map类的实现为基础的。你会发现它和Set类很相似(但不同于存储[值,值]对的形式,我们将要存储的是[键,值]对)。

这是我们的Dictionary类的骨架:

function Dictionary {  var items = {};}  

Set类类似,我们将在一个Object的实例而不是数组中存储元素。

然后,我们需要声明一些映射/字典所能使用的方法。

  • set(key,value):向字典中添加新元素。

  • delete(key):通过使用键值来从字典中移除键值对应的数据值。

  • has(key):如果某个键值存在于这个字典中,则返回true,反之则返回false

  • get(key):通过键值查找特定的数值并返回。

  • clear:将这个字典中的所有元素全部删除。

  • size:返回字典所包含元素的数量。与数组的length属性类似。

  • keys:将字典所包含的所有键名以数组形式返回。

  • values:将字典所包含的所有数值以数组形式返回。

  • hasset方法

    我们首先来实现has(key)方法。之所以要先实现这个方法,是因为它会被setremove等其他方法调用。我们可以通过如下代码来实现:

    this.has = function(key) {  return key in items;};  

    这个方法的实现和我们之前在Set类中的实现是一样的。我们使用JavaScript中的in操作符来验证一个key是否是items对象的一个属性。

    然后是set方法的实现:

    this.set = function(key, value) {  items[key] = value; //{1}};  

    该方法接受一个key和一个value作为参数。我们直接将value设为items对象的key属性的值。它可以用来给字典添加一个新的值,或者用来更新一个已有的值。

  • delete方法

    接下来,我们实现delete方法。它和Set类中的delete方法很相似,唯一的不同点在于我们将先搜索key(而不是value):

    this.delete= function(key) {  if (this.has(key)) {    delete items[key];    return true;  }  return false;};  

    然后我们可以使用JavaScript的remove操作符来从items对象中移除key属性。

  • getvalues方法

    如果我们想在字典中查找一个特定的项,并检索它的值,可以使用下面的方法:

    this.get = function(key) {  return this.has(key) ? items[key] : undefined;};  

    get方法首先会验证我们想要检索的值是否存在(通过查找key值),如果存在,将返回该值,反之将返回一个undefined值(请记住undefined值和null值是不一样的,第1章中提到过这个概念)。

    下一个是values方法。这个方法以数组的形式返回字典中所有values实例的值:

    this.values = function {  var values = ;  for (var k in items) { //{1}    if (this.has(k)) {      values.push(items[k]); //{2}    }  }  return values;};  

    首先,我们遍历items对象的所有属性值(行{1})。为了确定值存在,我们使用has函数来验证key确实存在,然后将它的值加入values数组(行{2})。最后,我们就能返回所有找到的值。

     我们不能仅仅使用 for-in语句来遍历items对象的所有属性,还需要使用hasOwnProperty方法(验证items对象是否包含某个属性),因为对象的原型也会包含对象的其他属性(JavaScript基本的Object类中的属性将会被继承,并存在于当前对象中,而对于这个数据结构来说,我们并不需要它们)。

  • clearsizekeysgetItems方法

    clearsize方法与第6章Set类中对应的方法是完全一样的,因此我们就不在本章讨论了。

    keys方法返回在Dictionary类中所有用于标识值的键名。要取出一个JavaScript对象中所有的键名,可以把这个对象作为参数传入Object类的keys方法(到目前为止,书中创建的类,包括Dictionary在内,都是JavaScript对象),如下:

    this.keys = function {  return Object.keys(items);};  

    最后,我们来验证items属性的输出值。我们可以实现一个返回items变量的方法,叫作getItems

    this.getItems = function {  return items;}  

7.1.2 使用Dictionary

首先,我们来创建一个Dictionary类的实例,然后给它添加三条电子邮件地址。我们将会使用这个dictionary实例来实现一个电子邮件地址簿。

使用我们创建的类来执行如下代码:

var dictionary = new Dictionary;dictionary.set(/'Gandalf/', /'[email protected]/');dictionary.set(/'John/', /'[email protected]/');dictionary.set(/'Tyrion/', /'[email protected]/');  

如果执行了如下代码,输出结果将会是true

console.log(dictionary.has(/'Gandalf/'));  

下面的代码将会输出3,因为我们向字典实例中添加了三个元素:

console.log(dictionary.size);  

现在,执行下面的几行代码:

console.log(dictionary.keys);console.log(dictionary.values);console.log(dictionary.get(/'Tyrion/'));  

输出结果分别如下所示:

    [/"Gandalf/", /"John/", /"Tyrion/"]    [/"[email protected]/", /"[email protected]/", /"[email protected]/"]    [email protected]  

最后,再执行几行代码:

dictionary.delete(/'John/');  

再执行下面的代码:

console.log(dictionary.keys);console.log(dictionary.values);console.log(dictionary.getItems);  

输出结果如下所示:

[/"Gandalf/", /"Tyrion/"][/"[email protected]/", /"[email protected]/"]Object {Gandalf: /"[email protected]/", Tyrion:/"[email protected]/"}  

移除了一个元素后,现在的dictionary实例中只包含两个元素了。加粗的一行表现了items对象的内部结构。