集合、字典和散列表可以存储不重复的值，在集合中，感兴趣的是每个值本身，并作为主要元素。而在字典和散列表中是以键值对的形式来存储数据。

1. 字典

字典也叫映射，集合以 [值, 值] 的形式来存储数据，而字典以 [键, 值] 的形式来存储数据。ES6 中的 Map 类就是字典。

  • set(key,value)：向字典中添加新元素。
  • delete(key)：通过使用键值来从字典中移除键值对应的数据值。
  • has(key)：如果某个键值存在于这个字典中，则返回true，反之则返回false。
  • get(key)：通过键值查找特定的数值并返回。
  • clear()：将这个字典中的所有元素全部删除。
  • size()：返回字典所包含元素的数量。与数组的length属性类似。
  • keys()：将字典所包含的所有键名以数组形式返回。
  • values()：将字典所包含的所有数值以数组形式返回。
  1. /**
  2.  * 非常简单，仅仅是使用对象本身来存储字典的键值对
  3.  */
  4. function Dictionary() {
  5.   var items = {};
  7.   this.has = function (key) {
  8.     return items.hasOwnProperty(key);
  9.   };
  11.   this.set = function (key, value) {
  12.     items[key] = value;
  13.   };
  15.   this.delete = function (key) {
  16.     if (this.has(key)) {
  17.       delete items[key];
  18.       return true;
  19.     }
  20.     return false;
  21.   };
  23.   this.get = function (key) {
  24.     return this.has(key) ? items[key] : undefined;
  25.   };
  27.   this.keys = function () {
  28.     return Object.keys(items);
  29.   };
  31.   this.values = function () {
  32.     return Object.keys(items).map(key => items[key]);
  33.   };
  35.   this.clear = function () {
  36.     items = {};
  37.   };
  39.   this.size = function () {
  40.     return Object.keys(items).length;
  41.   };
  43.   // 纯粹为了验证items
  44.   this.getItems = function () {
  45.     return items;
  46.   };
  47. }

2. 散列表

散列表（散列映射），是 Dictionary 类的一种散列表实现方式，叫做 HashTable 类，也叫做 HashMap 类。散列算法的作用是尽可能快地在数据结构中找到一个值，给定一个键值，然后返回值在表中的地址。
最简单的散列算法应该就是 lose lose 散列函数，仅仅是简单地将每个键值中的每个字母的 ASCII 码相加。

image.png

2.1 创建散列表

  • put(key,value)：向散列表增加一个新的项（也能更新散列表）。
  • remove(key)：根据键值从散列表中移除值。
  • get(key)：返回根据键值检索到的特定的值。
  1. /**
  2.  * 散列表，基于 lose lose 哈希算法
  3.  * 键需要是字符串，值可以是任意类型
  4.  * @constructor
  5.  */
  7. function HashTable() {
  8.   var table = [];
  10.   /**
  11.    * 散列函数 lose lose
  12.    *
  13.    * @param {string} key
  14.    * @returns {number}
  15.    */
  16.   var loseloseHashCode = function (key) {
  17.     var hash = 0;
  18.     for (var i = 0; i < key.length; i++) {
  19.       hash += key.charCodeAt(i); // 将键值中的每个字母的ASCII值相加
  20.     }
  21.     return hash % 37; // 为了得到较小的值，和一个数取余，最后数组的存储范围是 0~36
  22.   };
  24.   this.put = function (key, value) {
  25.     var position = loseloseHashCode(key);
  26.     console.log(position + ' - ' + key);
  27.     table[position] = value;
  28.   };
  30.   this.get = function (key) {
  31.     return table[loseloseHashCode(key)];
  32.   };
  34.   this.remove = function (key) {
  35.     table[loseloseHashCode(key)] = undefined;
  36.   };
  38.   // 纯粹为了验证table
  39.   this.getTable = function () {
  40.     return table;
  41.   };
  42. }

2.2 散列表和散列集合

在一些编程语言，比如 Java 中，除了 HashMap 还有 HashSet，其实在 Java 中，HashSet 内部就是个 HashMap。散列集合就是 散列函数 + 集合，完全可以重用散列表的实现，只是不再添加键值对，而是只插入值而没有键。

2.3 处理散列表中的冲突

lose lose 散列函数虽然简单，但是冲突率比较高。事实上，再好的散列算法也可能产生哈希冲突，因此需要解决冲突，毕竟数据结构用来保存数据而不是用来丢失的。

2.3.1 分离链接

为散列表的每一个有数据的位置创建一个链表用来存储元素。手段简单，但同时也需要额外的存储空间。

image.png

  1. /**
  2.  * 解决hash冲突: 分离链接法
  3.  *
  4.  * 以下实现中是本人基于书中进行改良，推荐！
  5.  * 当发生hash碰撞时，或者重复的key时，都会向表头添加键值对，
  6.  * 即使key重复，当get时也能就近获取最近一次设置的value
  7.  *
  8.  * @constructor
  9.  */
  10. function HashTable() {
  11.   var table = [];
  13.   var loseloseHashCode = function (key) {
  14.     var hash = 0;
  15.     for (var i = 0; i < key.length; i++) {
  16.       hash += key.charCodeAt(i);
  17.     }
  18.     return hash % 37;
  19.   };
  21.   // 键值对辅助类
  22.   var ValuePair = function (key, value) {
  23.     this.key = key;
  24.     this.value = value;
  26.     this.toString = function () {
  27.       return '[' + this.key + ' - ' + this.value + ']';
  28.     };
  29.   };
  31.   this.put = function (key, value) {
  32.     var position = loseloseHashCode(key);
  34.     if (table[position] === undefined) {
  35.       table[position] = new LinkedList();
  36.     }
  37.     table[position].insert(0, new ValuePair(key, value)); // 插入到表头
  38.   };
  40.   this.get = function (key) {
  41.     var position = loseloseHashCode(key);
  43.     if (table[position] !== undefined) {
  44.       // 遍历链表寻找键值对
  45.       var current = table[position].getHead();
  46.       while (current) {
  47.         if (current.element.key === key) {
  48.           return current.element.value;
  49.         }
  50.         current = current.next;
  51.       }
  52.     }
  53.     return undefined;
  54.   };
  56.   this.remove = function (key) {
  57.     var position = loseloseHashCode(key);
  59.     if (table[position] !== undefined) {
  60.       var current = table[position].getHead();
  61.       while (current) {
  62.         if (current.element.key === key) {
  63.           table[position].remove(current.element);
  64.           if (table[position].isEmpty()) { // 不留下空链表
  65.             table[position] = undefined;
  66.           }
  67.           return true;
  68.         }
  69.         current = current.next;
  70.       }
  71.     }
  72.     return false;
  73.   };
  75.   // 纯粹为了验证table
  76.   this.getTable = function () {
  77.     return table;
  78.   };
  79. }

2.3.2 线性探查

当向散列表中某个哈希位置添加新元素时，若位置已被占用，则尝试下一个位置，以此类推。

  1. /**
  2.  * 解决hash冲突: 线性探查法
  3.  *
  4.  * 以下纯粹来自书中实现，但其实有不少问题，不推荐！
  5.  *
  6.  * @constructor
  7.  */
  9. function HashTable() {
  10.   var table = [];
  12.   /**
  13.    * 散列函数 lose lose
  14.    *
  15.    * @param key
  16.    * @returns {number}
  17.    */
  18.   var loseloseHashCode = function (key) {
  19.     var hash = 0;
  20.     for (var i = 0; i < key.length; i++) {
  21.       hash += key.charCodeAt(i);
  22.     }
  23.     return hash % 37;
  24.   };
  26.   // 键值对辅助类
  27.   var ValuePair = function (key, value) {
  28.     this.key = key;
  29.     this.value = value;
  31.     this.toString = function () {
  32.       return '[' + this.key + ' - ' + this.value + ']';
  33.     };
  34.   };
  36.   this.put = function (key, value) {
  37.     var position = loseloseHashCode(key);
  38.     console.log(position + ' - ' + key);
  40.     var pair = new ValuePair(key, value);
  42.     // 当目标位置被占用时尝试position++的位置
  43.     if (table[position] === undefined) {
  44.       table[position] = pair;
  45.     } else {
  46.       var index = ++position;
  47.       while (table[index] !== undefined) {
  48.         index++;
  49.       }
  50.       table[index] = pair;
  51.     }
  52.   };
  54.   this.get = function (key) {
  55.     var position = loseloseHashCode(key);
  57.     if (table[position] !== undefined) {
  58.       if (table[position].key === key) {
  59.         return table[position].value;
  60.       } else {
  61.         var index = ++position;
  62.         while (
  63.           table[index] === undefined ||
  64.           table[index].key !== key
  65.           ) {
  66.           index++;
  67.         }
  68.         if (table[index].key === key) {
  69.           return table[index].value;
  70.         }
  71.       }
  72.     }
  73.     return undefined;
  74.   };
  76.   this.remove = function (key) {
  77.     var position = loseloseHashCode(key);
  79.     if (table[position] !== undefined) {
  80.       if (table[position].key === key) {
  81.         table[position] = undefined;
  82.       } else {
  83.         var index = ++position;
  84.         while (
  85.           table[index] === undefined ||
  86.           table[index].key !== key
  87.           ) {
  88.           index++;
  89.         }
  90.         if (table[index].key === key) {
  91.           table[index] = undefined;
  92.         }
  93.       }
  94.     }
  95.   };
  97.   // 纯粹为了验证table
  98.   this.getTable = function () {
  99.     return table;
  100.   };
  101. }

2.4 更好的散列函数 djb2

lose lose 散列函数过于简单、冲突太多，极端情况下退化为链表，失去了散列数组快速访问元素的意义。
因此，一个良好的散列函数既要计算的快，又要冲突少。djb2 是目前最受社区推崇的散列函数之一。

  1. /**
  2.  * djb2 散列算法
  3.  *
  4.  * @param {string} key
  5.  * @returns {number}
  6.  */
  7. function djb2HashCode(key) {
  8.   var hash = 5381; // 大多数实现都使用 5381
  9.   for (var i = 0; i < key.length; i++) {
  10.     hash = hash * 33 + hash.charCodeAt(i);
  11.   }
  12.   return hash % 1013; // 控制下最终哈希值大小，假设散列表大小为1000
  13. }

2.5 ES6中的Map、WeakMap、Set、WeakSet

ES6 中的 Map 和 Set 的 values 和 keys 方法返回的都是 Iterator 迭代器，而不是直接的数组。另外 size 是属性而不是方法。
Map 和 Set 与其弱化版本 WekMap 和 WeakSet 之间的区别是：

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

  • 只能用对象作为键。