首页 » 博文 » 类别 » WEB前端 » 正文
网站地图

前端学数据结构之字典和散列表

汉王 WEB前端 2018年01月03日 收藏

前面的话

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

字典

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

【创建字典】

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

下面将要实现的类就是以ECMAScript 6中Map类的实现为基础的。它和Set类很相似（但不同于存储[值，值]对的形式，我们将要存储的是[键，值]对）

这是我们的Dictionary类的骨架： 

  1. function Dictionary() {
  2.     var items = {};
  3. }

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

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

【has】

首先来实现has(key)方法。之所以要先实现这个方法，是因为它会被set和remove等其他方法调用。这个方法的实现和之前在Set类中的实现是一样的。使用JavaScript中的in操作符来验证一个key是否是items对象的一个属性。可以通过如下代码来实现： 

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

【set】

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

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

【remove】

它和Set类中的remove方法很相似，唯一的不同点在于我们将先搜索key（而不是value），然后我们可以使用JavaScript的delete操作符来从items对象中移除key属性 

  1. this.remove = function(key) { 
  2.   if (this.has(key)) {
  3.     delete items[key];
  4.     return true;
  5.   }
  6.   return false;
  7. }

【get】

get方法首先会验证我们想要检索的值是否存在（通过查找key值），如果存在，将返回该值， 反之将返回一个undefined值 

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

【values】

首先，我们遍历items对象的所有属性值（行{1}）。为了确定值存在，我们使用has函数来验证key确实存在，然后将它的值加入values数组（行{2}）。最后，我们就能返回所有找到的值。这个方法以数组的形式返回字典中所有values实例的值： 

  1. this.values = function() { 
  2.   var values = {};
  3.   for (var k in items) { //{1} 
  4.     if (this.has(k)) {
  5.       values.push(items[k]); //{2}
  6.     }
  7.   }
  8.   return values;
  9. };

【clear】 

  1.     this.clear = function(){
  2.         items = {};
  3.     };

【size】 

  1.     this.size = function(){
  2.         return Object.keys(items).length;
  3.     };

【keys】

keys方法返回在Dictionary类中所有用于标识值的键名。要取出一个JavaScript对象中所有的键名，可以把这个对象作为参数传入Object类的keys方法，如下： 

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

【items】

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

  1. this.getItems = function() {
  2.  return items;
  3. }

【完整代码】

Dictionary类的完整代码如下所示 

  1. function Dictionary(){
  2.  
  3.     var items = {};
  4.  
  5.     this.set = function(key, value){
  6.         items[key] = value; //{1}
  7.     };
  8.  
  9.     this.delete = function(key){
  10.         if (this.has(key)){
  11.             delete items[key];
  12.             return true;
  13.         }
  14.         return false;
  15.     };
  16.  
  17.     this.has = function(key){
  18.         return items.hasOwnProperty(key);
  19.         //return value in items;
  20.     };
  21.  
  22.     this.get = function(key) {
  23.         return this.has(key) ? items[key] : undefined;
  24.     };
  25.  
  26.     this.clear = function(){
  27.         items = {};
  28.     };
  29.  
  30.     this.size = function(){
  31.         return Object.keys(items).length;
  32.     };
  33.  
  34.     this.keys = function(){
  35.         return Object.keys(items);
  36.     };
  37.  
  38.     this.values = function(){
  39.         var values = [];
  40.         for (var k in items) {
  41.             if (this.has(k)) {
  42.                 values.push(items[k]);
  43.             }
  44.         }
  45.         return values;
  46.     };
  47.  
  48.     this.each = function(fn) {
  49.         for (var k in items) {
  50.             if (this.has(k)) {
  51.                 fn(k, items[k]);
  52.             }
  53.         }
  54.     };
  55.  
  56.     this.getItems = function(){
  57.         return items;
  58.     }
  59. }

【使用Dictionary类】

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

  1. var dictionary = new Dictionary(); 
  2. dictionary.set('Gandalf', 'gandalf@email.com'); 
  3. dictionary.set('John', 'johnsnow@email.com'); 
  4. dictionary.set('Tyrion', 'tyrion@email.com');

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

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

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

  1. console.log(dictionary.size());

现在，执行下面的几行代码： 

  1. console.log(dictionary.keys()); 
  2. console.log(dictionary.values()); 
  3. console.log(dictionary.get('Tyrion'));

输出结果分别如下所示： 

  1. ["Gandalf", "John", "Tyrion"]
  2. ["gandalf@email.com", "johnsnow@email.com", "tyrion@email.com"] 
  3. tyrion@email.com

最后，再执行几行代码： 

  1. dictionary.remove('John');

再执行下面的代码： 

  1. console.log(dictionary.keys()); 
  2. console.log(dictionary.values()); 
  3. console.log(dictionary.getItems());

输出结果如下所示： 

  1. ["Gandalf", "Tyrion"] 
  2. ["gandalf@email.com", "tyrion@email.com"]
  3. Object {Gandalf: "gandalf@email.com", Tyrion: "tyrion@email.com"}

移除了一个元素后，现在的dictionary实例中只包含两个元素了

散列表

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

散列算法的作用是尽可能快地在数据结构中找到一个值。如果要在数据结构中获得一个值（使用get方法），需要遍历整个数据结构来找到它。如果使用散列函数，就知道值的具体位置，因此能够快速检索到该值。散列函数的作用是给定一个键值，然后返回值在表中的地址

举个例子，我们继续使用在前面使用的电子邮件地址簿。我们将要使用最常见的散列函数——“lose lose”散列函数，方法是简单地将每个键值中的每个字母的ASCII值相加

hashtable1

【创建散列表】

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

  1. function HashTable(){
  2.   var table = [];
  3. }

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

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

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

  1. var loseloseHashCode = function (key) {
  2.  var hash = 0; //{1}
  3.  for (var i = 0; i < key.length; i++) { //{2}
  4.      hash += key.charCodeAt(i); //{3}
  5.  }
  6.  return hash % 37; //{4}
  7. };

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

【put】

现在，有了散列函数，我们就可以实现put方法了： 

  1. this.put = function(key, value) {
  2.  var position = loseloseHashCode(key); //{5}
  3.  console.log(position + ' - ' + key); //{6}
  4.  table[position] = value; //{7}
  5. };

首先，根据给定的key和所创建的散列函数计算出它在表中的位置（行{5}）。为了便于展示信息，我们将计算出的位置输出至控制台（行{6}）。由于它不是必需的，我们也可以将这行代码移除。然后要做的，是将value参数添加到用散列函数计算出的对应的位置上（行{7}）

【get】

从HashTable实例中查找一个值也很简单。为此，将会实现一个get方法。首先，我们会使用所创建的散列函数来求出给定key所对应的位置。这个函数会返回值的位置，因此我们所要做的就是根据这个位置从数组table中获得这个值。 

  1. this.get = function (key) {
  2.  return table[loseloseHashCode(key)];
  3. };

【remove】

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

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

  1. this.remove = function(key) {
  2.  table[loseloseHashCode(key)] = undefined;
  3. };

【完整代码】

HashTable类的完整代码如下所示 

  1. function HashTable() {
  2.  
  3.     var table = [];
  4.  
  5.     var loseloseHashCode = function (key) {
  6.         var hash = 0;
  7.         for (var i = 0; i < key.length; i++) {
  8.             hash += key.charCodeAt(i);
  9.         }
  10.         return hash % 37;
  11.     };
  12.  
  13.     var djb2HashCode = function (key) {
  14.         var hash = 5381;
  15.         for (var i = 0; i < key.length; i++) {
  16.             hash = hash * 33 + key.charCodeAt(i);
  17.         }
  18.         return hash % 1013;
  19.     };
  20.  
  21.     var hashCode = function (key) {
  22.         return loseloseHashCode(key);
  23.     };
  24.  
  25.     this.put = function (key, value) {
  26.         var position = hashCode(key);
  27.         console.log(position + ' - ' + key);
  28.         table[position] = value;
  29.     };
  30.  
  31.     this.get = function (key) {
  32.         return table[hashCode(key)];
  33.     };
  34.  
  35.     this.remove = function(key){
  36.         table[hashCode(key)] = undefined;
  37.     };
  38.  
  39.     this.print = function () {
  40.         for (var i = 0; i < table.length; ++i) {
  41.             if (table[i] !== undefined) {
  42.                 console.log(i + ": " + table[i]);
  43.             }
  44.         }
  45.     };
  46. }

【使用HashTable类】

下面执行一些代码来测试HashTable类： 

  1. var hash = new HashTable();
  2. hash.put('Gandalf', 'gandalf@email.com');
  3. hash.put('John', 'johnsnow@email.com');
  4. hash.put('Tyrion', 'tyrion@email.com');

执行上述代码，会在控制台中获得如下输出： 

  1. 19 - Gandalf
  2. 29 - John
  3. 16 - Tyrion

下面的图表展现了包含这三个元素的HashTable数据结构：

hashtable2

现在来测试get方法： 

  1. console.log(hash.get('Gandalf'));
  2. console.log(hash.get('Loiane'));

获得如下的输出： 

  1. gandalf@email.com
  2. undefined

由于Gandalf是一个在散列表中存在的键，get方法将会返回它的值。而由于Loiane是一个不存在的键，当我们试图在数组中根据位置获取值的时候（一个由散列函数生成的位置），返回值将会是undefined（即不存在）

然后，我们试试从散列表中移除Gandalf： 

  1. hash.remove('Gandalf');
  2. console.log(hash.get('Gandalf'));

由于Gandalf不再存在于表中，hash.get('Gandalf')方法将会在控制台上给出undefined的输出结果

【散列集合】

在一些编程语言中，还有一种叫作散列集合的实现。散列集合由一个集合构成，但是插入、移除或获取元素时，使用的是散列函数。我们可以重用本章中实现的所有代码来实现散列集合，不同之处在于，不再添加键值对，而是只插入值而没有键。例如，可以使用散列集合来存储所有的英语单词（不包括它们的定义）。和集合相似，散列集合只存储唯一的不重复的值

处理冲突

有时候，一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候，我们称其为冲突。例如，我们看看下面的代码会得到怎样的输出结果： 

  1. var hash = new HashTable();
  2. hash.put('Gandalf', 'gandalf@email.com');
  3. hash.put('John', 'johnsnow@email.com');
  4. hash.put('Tyrion', 'tyrion@email.com');
  5. hash.put('Aaron', 'aaron@email.com');
  6. hash.put('Donnie', 'donnie@email.com');
  7. hash.put('Ana', 'ana@email.com');
  8. hash.put('Jonathan', 'jonathan@email.com');
  9. hash.put('Jamie', 'jamie@email.com');
  10. hash.put('Sue', 'sue@email.com');
  11. hash.put('Mindy', 'mindy@email.com');
  12. hash.put('Paul', 'paul@email.com');
  13. hash.put('Nathan', 'nathan@email.com');

输出结果如下： 

  1. 19 - Gandalf
  2. 29 - John
  3. 16 - Tyrion
  4. 16 - Aaron
  5. 13 - Donnie
  6. 13 - Ana
  7. 5 - Jonathan
  8. 5 - Jamie
  9. 5 - Sue
  10. 32 - Mindy
  11. 32 - Paul
  12. 10 – Nathan

Tyrion和Aaron有相同的散列值（16）。Donnie和Ana有相同的散列值（13），Jonathan、Jamie和Sue有相同的散列值（5），Mindy和Paul也有相同的散列值（32）

那HashTable实例会怎样呢？执行之前的代码后散列表中会有哪些值呢？为了获得结果，我们来实现一个叫作print的辅助方法，它会在控制台上输出HashTable中的值： 

  1. this.print = function() {
  2.  for (var i = 0; i < table.length; ++i) { //{1}
  3.  　　if (table[i] !== undefined) { //{2}
  4.  　　　　console.log(i + ": " + table[i]);//{3}
  5.  　　}
  6.  }
  7. };

首先，遍历数组中的所有元素（行{1}）。当某个位置上有值的时候（行{2}），会在控制台上输出位置和对应的值（行{3}）。现在来使用这个方法： 

  1. hash.print();

在控制台上得到如下的输出结果： 

  1. 5:sue@email.com
  2. 10:nathan@email.com
  3. 13:ana@email.com
  4. 16:aaron@email.com
  5. 19:gandalf@email.com
  6. 29:johnsnow@email.com
  7. 32:paul@email.com

Jonathan、Jamie和Sue有相同的散列值，也就是5。由于Sue是最后一个被添加的，Sue将是在HashTable实例中占据位置5的元素。首先，Jonathan会占据这个位置，然后Jamie会覆盖它，然后Sue会再次覆盖。这对于其他发生冲突的元素来说也是一样的。

使用一个数据结构来保存数据的目的显然不是去丢失这些数据，而是通过某种方法将它们全部保存起来。因此，当这种情况发生的时候就要去解决它。处理冲突有几种方法：分离链接、线性探查和双散列法

【分离链接】

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

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

hashtable3

在位置5上，将会有包含三个元素的LinkedList实例；在位置13、16和32上，将会有包含两个元素的LinkedList实例；在位置10、19和29上，将会有包含单个元素的LinkedList实例

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

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

  1. var ValuePair = function(key, value){
  2.  this.key = key;
  3.  this.value = value;
  4.  this.toString = function() {
  5.   return '[' + this.key + ' - ' + this.value + ']'; 
  6.   }
  7. };

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

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

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

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

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

  1. this.get = function(key) {
  2.  var position = loseloseHashCode(key);
  3.  if (table[position] !== undefined){ //{3}
  4.   //遍历链表来寻找键/值
  5.   var current = table[position].getHead(); //{4}
  6.     while(current.next){ //{5}
  7.     if (current.element.key === key){ //{6}
  8.       return current.element.value; //{7}
  9.     }
  10.     current = current.next; //{8}
  11.   }
  12.   //检查元素在链表第一个或最后一个节点的情况
  13.   if (current.element.key === key){ //{9}
  14.     return current.element.value;
  15.   }
  16.  }
  17.  return undefined; //{10}
  18. };

我们要做的第一个验证，是确定在特定的位置上是否有元素存在（行{3}）。如果没有，则返回一个undefined表示在HashTable实例中没有找到这个值（行{10}）。如果在这个位置上有值存在，我们知道这是一个LinkedList实例。现在要做的是遍历这个链表来寻找我们需要的元素。在遍历之前先要获取链表表头的引用（行{4}），然后就可以从链表的头部遍历到尾部（行{5}，current.next将会是null）。

Node链表包含next指针和element属性。而element属性又是ValuePair的实例，所以它又有value和key属性。可以通过current.element.next来获得Node链表的key属性，并通过比较它来确定它是否就是我们要找的键（行{6}）。（这就是要使用ValuePair这个辅助类来存储元素的原因。我们不能简单地存储值本身，这样就不能确定哪个值对应着特定的键。）如果key值相同，就返回Node的值（行{7}）；如果不相同，就继续遍历链表，访问下一个节点（行{8}）。

如果要找的元素是链表的第一个或最后一个节点，那么就不会进入while循环的内部。因此，需要在行{9}处理这种特殊的情况

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

  1. this.remove = function(key){
  2.  var position = loseloseHashCode(key);
  3.  if (table[position] !== undefined){
  4.   var current = table[position].getHead();
  5.   while(current.next){
  6.     if (current.element.key === key){ //{11}
  7.       table[position].remove(current.element); //{12}
  8.       if (table[position].isEmpty()){ //{13}
  9.         table[position] = undefined; //{14}
  10.       }
  11.       return true; //{15}
  12.     }
  13.     current = current.next;
  14.   }
  15.   // 检查是否为第一个或最后一个元素
  16.   if (current.element.key === key){ //{16}
  17.     table[position].remove(current.element);
  18.   if (table[position].isEmpty()){
  19.     table[position] = undefined;
  20.   }
  21.   return true;
  22.   }
  23.  }
  24.  return false; //{17}
  25. };

在remove方法中，我们使用和get方法一样的步骤找到要找的元素。遍历LinkedList实例时，如果链表中的current元素就是要找的元素（行{11}），使用remove方法将其从链表中移除。然后进行一步额外的验证：如果链表为空了（行{13}——链表中不再有任何元素了），就将散列表这个位置的值设为undefined（行{14}），这样搜索一个元素或打印它的内容的时候，就可以跳过这个位置了。最后，返回true表示这个元素已经被移除（行{15}）或者在最后返回false表示这个元素在散列表中不存在（行{17}）。同样，需要和get方法一样，处理元素在第一个或最后一个的情况（行{16}）

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

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

  1. function HashTableSeparateChaining(){
  2.  
  3.     var table = [];
  4.  
  5.     var ValuePair = function(key, value){
  6.         this.key = key;
  7.         this.value = value;
  8.  
  9.         this.toString = function() {
  10.             return '[' + this.key + ' - ' + this.value + ']';
  11.         }
  12.     };
  13.  
  14.     var loseloseHashCode = function (key) {
  15.         var hash = 0;
  16.         for (var i = 0; i < key.length; i++) {
  17.             hash += key.charCodeAt(i);
  18.         }
  19.         return hash % 37;
  20.     };
  21.  
  22.     var hashCode = function(key){
  23.         return loseloseHashCode(key);
  24.     };
  25.  
  26.     this.put = function(key, value){
  27.         var position = hashCode(key);
  28.         console.log(position + ' - ' + key);
  29.  
  30.         if (table[position] == undefined) {
  31.             table[position] = new LinkedList();
  32.         }
  33.         table[position].append(new ValuePair(key, value));
  34.     };
  35.  
  36.     this.get = function(key) {
  37.         var position = hashCode(key);
  38.  
  39.         if (table[position] !== undefined  && !table[position].isEmpty()){
  40.  
  41.             //iterate linked list to find key/value
  42.             var current = table[position].getHead();
  43.  
  44.             do {
  45.                 if (current.element.key === key){
  46.                     return current.element.value;
  47.                 }
  48.                 current = current.next;
  49.             } while(current);
  50.         }
  51.         return undefined;
  52.     };
  53.  
  54.     this.remove = function(key){
  55.  
  56.         var position = hashCode(key);
  57.  
  58.         if (table[position] !== undefined){
  59.  
  60.             //iterate linked list to find key/value
  61.             var current = table[position].getHead();
  62.  
  63.             do {
  64.                 if (current.element.key === key){
  65.                     table[position].remove(current.element);
  66.                     if (table[position].isEmpty()){
  67.                         table[position] = undefined;
  68.                     }
  69.                     return true;
  70.                 }
  71.                 current = current.next;
  72.             } while(current);
  73.         }
  74.  
  75.         return false;
  76.     };
  77.  
  78.     this.print = function() {
  79.         for (var i = 0; i < table.length; ++i) {
  80.             if (table[i] !== undefined) {
  81.                console.log(table[i].toString());
  82.             }
  83.         }
  84.     };
  85. }

【线性探查】

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

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

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

和之前一样，先获得由散列函数生成的位置（行{1}），然后验证这个位置是否有元素存在（如果这个位置被占据了，将会通过行{2}的验证）。如果没有元素存在，就在这个位置加入新元素（行{3}——一个ValuePair的实例）

如果这个位置已经被占据了，需要找到下一个没有被占据的位置（position的值是undefined），因此我们声明一个index变量并赋值为position+1（行{4}——在变量名前使用自增运算符++会先递增变量值然后再将其赋值给index）。然后验证这个位置是否被占据（行{5}），如果被占据了，继续将index递增（行{6}），直到找到一个没有被占据的位置。然后要做的，就是将值分配到这个位置（行{7}）

如果再次执行前面实例中插入数据的代码，下图展示使用了线性探查的散列表的最终结果：

hashtable4

让我们来模拟一下散列表中的插入操作

1、试着插入Gandalf。它的散列值是19，由于散列表刚刚被创建，位置19还是空的——可以在这里插入数据

2、试着在位置29插入John。它也是空的，所以可以插入这个姓名

3、试着在位置16插入Tyrion。它是空的，所以可以插入这个姓名

4、试着插入Aaron，它的散列值也是16。位置16已经被Tyrion占据了，所以需要检查索引值为position+1的位置（16+1）。位置17是空的，所以可以在位置17插入Aaron

5、接着，试着在位置13插入Donnie。它是空的，所以可以插入这个姓名

6、想在位置13插入Ana，但是这个位置被占据了。因此在位置14进行尝试，它是空的，所以可以在这里插入姓名

7、然后，在位置5插入Jonathan，这个位置是空的，所以可以插入这个姓名

8、试着在位置5插入Jamie，但是这个位置被占了。所以跳至位置6，这个位置是空的，因此可以在这个位置插入姓名

9、试着在位置5插入Sue，但是位置被占据了。所以跳至位置6，但也被占了。接着跳至位置7，这里是空的，所以可以在这里插入姓名。以此类推

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

  1. this.get = function(key) {
  2.  var position = loseloseHashCode(key);
  3.  if (table[position] !== undefined){ //{8}
  4.   if (table[position].key === key) { //{9}
  5.     return table[position].value; //{10}
  6.   } else {
  7.     var index = ++position;
  8.     while (table[index] === undefined  || table[index].key !== key){ //{11}
  9.       index++;
  10.     }
  11.     if (table[index].key === key) { //{12}
  12.       return table[index].value; //{13}
  13.     }
  14.   }
  15.  }
  16.  return undefined; //{14}
  17. };

要获得一个键对应的值，先要确定这个键存在（行{8}）。如果这个键不存在，说明要查找的值不在散列表中，因此可以返回undefined（行{14}）。如果这个键存在，需要检查我们要找的值是否就是这个位置上的值（行{9}）。如果是，就返回这个值（行{10}）。

如果不是，就在散列表中的下一个位置继续查找，直到找到一个键值与我们要找的键值相同的元素（行{11}）。然后，验证一下当前项就是我们要找的项（行{12}——只是为了确认一下）并且将它的值返回（行{13}）。

我们无法确定要找的元素实际上在哪个位置，这就是使用ValuePair来表示HashTable元素的原因

remove方法和get方法基本相同，不同之处在于行{10}和{13}，它们将会由下面的代码代替： 

  1. table[index]=undefined;

要移除一个元素，只需要给其赋值为undefined，来表示这个位置不再被占据并且可以在必要时接受一个新元素

线性探查的HashTable的完整代码如下所示 

  1. function HashLinearProbing(){
  2.  
  3.     var table = [];
  4.  
  5.     var ValuePair = function(key, value){
  6.         this.key = key;
  7.         this.value = value;
  8.  
  9.         this.toString = function() {
  10.             return '[' + this.key + ' - ' + this.value + ']';
  11.         }
  12.     };
  13.  
  14.     var loseloseHashCode = function (key) {
  15.         var hash = 0;
  16.         for (var i = 0; i < key.length; i++) {
  17.             hash += key.charCodeAt(i);
  18.         }
  19.         return hash % 37;
  20.     };
  21.  
  22.     var hashCode = function(key){
  23.         return loseloseHashCode(key);
  24.     };
  25.  
  26.     this.put = function(key, value){
  27.         var position = hashCode(key);
  28.         console.log(position + ' - ' + key);
  29.  
  30.         if (table[position] == undefined) {
  31.             table[position] = new ValuePair(key, value);
  32.         } else {
  33.             var index = ++position;
  34.             while (table[index] != undefined){
  35.                 index++;
  36.             }
  37.             table[index] = new ValuePair(key, value);
  38.         }
  39.     };
  40.  
  41.     this.get = function(key) {
  42.         var position = hashCode(key);
  43.  
  44.         if (table[position] !== undefined){
  45.             if (table[position].key === key) {
  46.                 return table[position].value;
  47.             } else {
  48.                 var index = ++position;
  49.                 while (table[index] !== undefined && (table[index] && table[index].key !== key)){
  50.                     index++;
  51.                 }
  52.                 if (table[index] && table[index].key === key) {
  53.                     return table[index].value;
  54.                 }
  55.             }
  56.         } else { //search for possible deleted value
  57.             var index = ++position;
  58.             while (table[index] == undefined || index == table.length ||
  59.                 (table[index] !== undefined && table[index] && table[index].key !== key)){
  60.                 index++;
  61.             }
  62.             if (table[index] && table[index].key === key) {
  63.                 return table[index].value;
  64.             }
  65.         }
  66.         return undefined;
  67.     };
  68.  
  69.     this.remove = function(key){
  70.         var position = hashCode(key);
  71.  
  72.         if (table[position] !== undefined){
  73.             if (table[position].key === key) {
  74.                 table[position] = undefined;
  75.             } else {
  76.                 var index = ++position;
  77.                 while (table[index] === undefined || table[index].key !== key){
  78.                     index++;
  79.                 }
  80.                 if (table[index].key === key) {
  81.                     table[index] = undefined;
  82.                 }
  83.             }
  84.         }
  85.     };
  86.  
  87.     this.print = function() {
  88.         for (var i = 0; i < table.length; ++i) {
  89.             if (table[i] !== undefined) {
  90.                 console.log(i + ' -> ' + table[i].toString());
  91.             }
  92.         }
  93.     };
  94. }

【更好的散列函数】

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

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

  1. var djb2HashCode = function (key) {
  2.  var hash = 5381; //{1}
  3.  for (var i = 0; i < key.length; i++) { //{2}
  4.      hash = hash * 33 + key.charCodeAt(i); //{3}
  5.  }
  6.  return hash % 1013; //{4}
  7. };

它包括初始化一个hash变量并赋值为一个质数（行{1}——大多数实现都使用5381），然后迭代参数key（行{2}），将hash与33相乘（用来当作一个魔力数），并和当前迭代到的字符的ASCII码值相加（行{3}）

最后，我们将使用相加的和与另一个随机质数（比我们认为的散列表的大小要大——在本例中，我们认为散列表的大小为1000）相除的余数。

如果再次执行前面实例中插入数据的代码，这将是使用djb2HashCode代替loseloseHashCode的最终结果： 

  1. 798-Gandalf
  2. 838-John
  3. 624-Tyrion
  4. 215-Aaron
  5. 278-Donnie
  6. 925-Ana
  7. 288-Jonathan
  8. 962-Jamie
  9. 502-Sue
  10. 804-Mindy
  11. 54-Paul
  12. 223-Nathan

没有冲突！这并不是最好的散列函数，但这是最被社区推荐的散列函数之一

ES6

ECMAScript 2015新增了Map类。我们可以基于ES6的Map类开发我们的Dictionary类

看看原生的Map类怎么用。还是用我们原来测试Dictionary类的例子： 

  1. var map = new Map();
  2. map.set('Gandalf', 'gandalf@email.com');
  3. map.set('John', 'johnsnow@email.com');
  4. map.set('Tyrion', 'tyrion@email.com');
  5. console.log(map.has('Gandalf')); //输出true
  6. console.log(map.size); //输出3
  7. console.log(map.keys()); //输出["Gandalf", "John", "Tyrion"]
  8. console.log(map.values()); //输出["gandalf@email.com",
  9. "johnsnow@email.com", "tyrion@email.com"]
  10. console.log(map.get('Tyrion')); //输出tyrion@email.com

和Dictionary类不同，ES6的Map类的values方法和keys方法都返回Iterator，而不是值或键构成的数组。另一个区别是，我们实现的size方法返回字典中存储的值的个数，而ES6的Map类则有一个size属性

删除map中的元素可以用delete方法： 

  1. map.delete('John');

clear方法会重置map数据结构，这跟我们在Dictionary类里实现的一样

除了Set和Map这两种新的数据结构，ES6还增加了它们的弱化版本，WeakSet和WeakMap。基本上，Map和Set与其弱化版本之间仅有的区别是：

1、WeakSet或WeakMap类没有entries、keys和values等方法；

2、只能用对象作为键

创建和使用这两个类主要是为了性能。WeakSet和WeakMap是弱化的（用对象作为键），没有强引用的键。这使得JavaScript的垃圾回收器可以从中清除整个入口。另一个优点是，必须用键才可以取出值。这些类没有entries、keys和values等迭代器方法，因此，除非知道键，否则没有办法取出值

使用WeakMap类的例子如下： 

  1. var map = new WeakMap();
  2. var ob1 = {name:'Gandalf'}, //{1}
  3.     ob2 = {name:'John'},
  4.     ob3 = {name:'Tyrion'};
  5. map.set(ob1, 'gandalf@email.com'); //{2}
  6. map.set(ob2, 'johnsnow@email.com');
  7. map.set(ob3, 'tyrion@email.com');
  8. console.log(map.has(ob1)); //{3} 输出true
  9. console.log(map.get(ob3)); //{4} 输出tyrion@email.com
  10. map.delete(ob2); //{5}

WeakMap类也可以用set方法，但不能使用数字、字符串、布尔值等基本数据类型，需要将名字转换为对象（行{1}和行{2}）。搜索（行{3}）、读取（行{4}）和删除值（行{5}），也要传入作为键的对象。同样的逻辑也适用于WeakSet类。

作者：https://www.cnblogs.com/xiaohuochai/p/8183020.html

推荐文章
最新文章
基于ThinkPHP5开发的后台整合系统

基于ThinkPHP5开发的后台整合系统

ThinkPHP5开发的电脑端和手机端商城购物系统（含支付）

ThinkPHP5开发的电脑端和手机端商城购物系统（含支付）

Yii2和aceAdmin 开发的后台管理系统

Yii2和aceAdmin 开发的后台管理系统

Yii2打造RBAC后台通用权限的管理系统

Yii2打造RBAC后台通用权限的管理系统

最新Yii2+AdminLTE开发经典内容管理系统

最新Yii2+AdminLTE开发经典内容管理系统

Yii2 开发的经典博客系统

Yii2 开发的经典博客系统

Yii2 打造经典CMS管理系统

Yii2 打造经典CMS管理系统

Yii1 打造网上商城购物系统

Yii1 打造网上商城购物系统