JavaScript数据结构与算法（8）字典和散列表

待我称王封你为后i 2022-01-29 10:41 259阅读 0赞

集合、字典和散列表可以存储不重复的值。在集合中，我们感兴趣的是每个值本身，并把它当作主要元素。在字典中，我们用\[键，值\]的形式来存储数据。在散列表中也是一样（也是以\[键，值\]对的形式来存储数据）。但是两种数据结构的实现方式略有不同。

**1.字典**

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

这是我们的Dictionary类的骨架：

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

与Set类类似，我们将在一个Object的实例而不是数组中存储元素。 然后，我们需要声明一些映射/字典所能使用的方法：

set(key,value)：向字典中添加新元素。  
remove(key)：通过使用键值来从字典中移除键值对应的数据值。  
has(key)：如果某个键值存在于这个字典中，则返回true，反之则返回false。  
get(key)：通过键值查找特定的数值并返回。  
clear()：将这个字典中的所有元素全部删除。  
size()：返回字典所包含元素的数量。与数组的length属性类似。  
keys()：将字典所包含的所有键名以数组形式返回。  
values()：将字典所包含的所有数值以数组形式返回。

使用Dictionary类

var dictionary = new Dictionary(); 
    dictionary.set('Gandalf', 'gandalf@email.com'); 
    dictionary.set('John', 'johnsnow@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", "johnsnow@email.com", "tyrion@email.com"] 
    console.log(dictionary.get('Tyrion')); //tyrion@email.com
    
    dictionary.remove('John');
    console.log(dictionary.keys()); 
    console.log(dictionary.values()); 
    console.log(dictionary.getItems());
    //输出结果如下所示：
    ["Gandalf", "Tyrion"] 
    ["gandalf@email.com", "tyrion@email.com"]
    Object {Gandalf: "gandalf@email.com", Tyrion: "tyrion@email.com"}

**2.散列表**

下面将详细介绍HashTable类，也叫HashMap类，是Dictionary类的一种散列表实现方式

我们将使用数组来表示我们的数据结构，从搭建类的骨架开始：

function HashTable(){
      var table = [];
    }

然后，给类添加一些方法。我们给每个类实现三个基础的方法

put(key,value)：向散列表增加一个新的项（也能更新散列表）。  
remove(key)：根据键值从散列表中移除值。  
get(key)：返回根据键值检索到的特定的值。

在实现这三个方法之前，要实现的第一个方法是散列函数，它是HashTable类中的一个私有方法：

给定一个key参数，就能根据组成key的每个字符的ASCII码值的和得到一个数字。所以，首先需要一个变量来存储这个总和（行\{1\}）。然后，遍历key（行\{2\}）并将从ASCII表中查到的每个字符对应的ASCII值加到hash变量中（可以使用JavaScript的String类中的charCodeAt方法——行\{3\}）。最后，返回hash值。为了得到比较小的数值，我们会使用hash值和一个任意数做除法的余数（mod）。

HashTable类的完整代码如下所示：

对于remove中要从HashTable实例中移除一个元素，只需要求出元素的位置（可以使用散列函数来获取）并赋值为undefined。

对于HashTable类来说，我们不需要像ArrayList类一样从table数组中将位置也移除。由于元素分布于整个数组范围内，一些位置会没有任何元素占据，并默认为undefined值。我们也不能将位置本身从数组中移除（这会改变其他元素的位置），否则，当下次需要获得或移除一个元素的时候，这个元素会不在我们用散列函数求出的位置上。

也就是说，并不移除位置，只是移除位置上元素。

**3.处理冲突**

处理冲突有几种方法：分离链接、线性探查、双散列法

分离链接

分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法，但是它在HashTable实例之外还需要额外的存储空间

例如，我们在之前的测试代码中使用分离链接的话，输出结果将会是这样：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]

对于分离链接和线性探查来说，只需要重写三个方法：put、get和remove。这三个方法在每种技术实现中都是不同的

为了实现一个使用了分离链接的HashTable实例，我们需要一个新的辅助类来表示将要加入LinkedList实例的元素。我们管它叫ValuePair类（在HashTable类内部定义）：

var ValuePair = function(key, value){
     	this.key = key;
     	this.value = value;
     	this.toString = function() {
      		return '[' + this.key + ' - ' + this.value + ']'; 
      	}
    };

这个类只会将key和value存储在一个Object实例中。我们也重写了toString方法，以便之后在浏览器控制台中输出结果

我们来实现第一个方法，put方法，代码如下：

this.put = function(key, value){
     	var position = loseloseHashCode(key);
     	if (table[position] == undefined) { //{1}
    　　 	table[position] = new LinkedList(); //考虑到前面的链表定义
    	}
    	table[position].append(new ValuePair(key, value)); //{2}
    };

在这个方法中，将验证要加入新元素的位置是否已经被占据（行\{1\}）。如果这个位置是第一次被加入元素，我们会在这个位置上初始化一个LinkedList类的实例（你已经在第5章中学习过）。然后，使用append方法向LinkedList实例中添加一个ValuePair实例（键和值）（行\{2\}）

然后，我们实现用来获取特定值的get方法：

this.get = function(key) {
     var position = loseloseHashCode(key);
     if (table[position] !== undefined){ //{3}
      //遍历链表来寻找键/值
      var current = table[position].getHead(); //{4} 在遍历之前先要获取链表表头的引用（行{4}），
        while(current.next){ //{5} 然后就可以从链表的头部遍历到尾部（行{5}，current.next将会是null）。
        if (current.element.key === key){ //{6} Node链表包含next指针和element属性。而element属性又是ValuePair的实例，所以它又有value和key属性。
          return current.element.value; //{7}
        }
        current = current.next; //{8}
      }
      //检查元素在链表第一个或最后一个节点的情况
      if (current.element.key === key){ //{9}
        return current.element.value;
      }
     }
     return undefined; //{10}
    };

使用分离链接法从HashTable实例中移除一个元素和之前在本章实现的remove方法有一些不同。现在使用的是链表，我们需要从链表中移除一个元素。来看看remove方法的实现：

this.remove = function(key){
     var position = loseloseHashCode(key);
     if (table[position] !== undefined){
      var current = table[position].getHead();
      while(current.next){
        if (current.element.key === key){ //{11}
          table[position].remove(current.element); //{12}
          if (table[position].isEmpty()){ //{13}
            table[position] = undefined; //{14}
          }
          return true; //{15}
        }
        current = current.next;
      }
      // 检查是否为第一个或最后一个元素
      if (current.element.key === key){ //{16}
        table[position].remove(current.element);
      if (table[position].isEmpty()){
        table[position] = undefined;
      }
      return true;
      }
     }
     return false; //{17}
    };

重写了这三个方法后，我们就拥有了一个使用了分离链接法来处理冲突的HashMap实例

分离链接的HashMap的完整代码如下所示

线性探查

另一种解决冲突的方法是线性探查。当想向表中某个位置加入一个新元素的时候，如果索引为index的位置已经被占据了，就尝试index+1的位置。如果index+1的位置也被占据了，就尝试index+2的位置，以此类推

继续实现需要重写的三个方法。第一个是put方法：

this.put = function(key, value){
     var position = loseloseHashCode(key); // {1}
     if (table[position] == undefined) { // {2}
       table[position] = new ValuePair(key, value); // {3}
     } else {
      var index = ++position; // {4}
      while (table[index] != undefined){ // {5}
        index++; // {6}
      }
      table[index] = new ValuePair(key, value); // {7}
     }
    };

现在插入了所有的元素，下面实现get方法来获取它们的值

this.get = function(key) {
     var position = loseloseHashCode(key);
     if (table[position] !== undefined){ //{8}
      if (table[position].key === key) { //{9}
        return table[position].value; //{10}
      } else {
        var index = ++position;
        while (table[index] === undefined  || table[index].key !== key){ //{11}
          index++;
        }
        if (table[index].key === key) { //{12}
          return table[index].value; //{13}
        }
      }
     }
     return undefined; //{14}
    };

更好的散列函数

“loselose”散列函数并不是一个表现良好的散列函数，因为它会产生太多的冲突。如果使用这个函数的话，会产生各种各样的冲突。一个表现良好的散列函数是由几个方面构成的：插入和检索元素的时间（即性能），当然也包括较低的冲突可能性

另一个可以实现的比“loselose”更好的散列函数是djb2：

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]: /images/20220129/72967e988e5c4711af7c6eb9b6412147.png