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

1. 字典

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

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

/**
 * 非常简单，仅仅是使用对象本身来存储字典的键值对
 */
function Dictionary() {
  var items = {};

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

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

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

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

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

  this.values = function () {
    return Object.keys(items).map(key => items[key]);
  };

  this.clear = function () {
    items = {};
  };

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

  // 纯粹为了验证items
  this.getItems = function () {
    return items;
  };
}

2. 散列表

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

image.png

2.1 创建散列表

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

/**
 * 散列表，基于 lose lose 哈希算法
 * 键需要是字符串，值可以是任意类型
 * @constructor
 */

function HashTable() {
  var table = [];

  /**
   * 散列函数 lose lose
   *
   * @param {string} key
   * @returns {number}
   */
  var loseloseHashCode = function (key) {
    var hash = 0;
    for (var i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i); // 将键值中的每个字母的ASCII值相加
    }
    return hash % 37; // 为了得到较小的值，和一个数取余，最后数组的存储范围是 0~36
  };

  this.put = function (key, value) {
    var position = loseloseHashCode(key);
    console.log(position + ' - ' + key);
    table[position] = value;
  };

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

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

  // 纯粹为了验证table
  this.getTable = function () {
    return table;
  };
}

2.2 散列表和散列集合

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

2.3 处理散列表中的冲突

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

2.3.1 分离链接

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

image.png

/**
 * 解决hash冲突: 分离链接法
 *
 * 以下实现中是本人基于书中进行改良，推荐！
 * 当发生hash碰撞时，或者重复的key时，都会向表头添加键值对，
 * 即使key重复，当get时也能就近获取最近一次设置的value
 *
 * @constructor
 */
function HashTable() {
  var table = [];

  var loseloseHashCode = function (key) {
    var hash = 0;
    for (var i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % 37;
  };

  // 键值对辅助类
  var ValuePair = function (key, value) {
    this.key = key;
    this.value = value;

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

  this.put = function (key, value) {
    var position = loseloseHashCode(key);

    if (table[position] === undefined) {
      table[position] = new LinkedList();
    }
    table[position].insert(0, new ValuePair(key, value)); // 插入到表头
  };

  this.get = function (key) {
    var position = loseloseHashCode(key);

    if (table[position] !== undefined) {
      // 遍历链表寻找键值对
      var current = table[position].getHead();
      while (current) {
        if (current.element.key === key) {
          return current.element.value;
        }
        current = current.next;
      }
    }
    return undefined;
  };

  this.remove = function (key) {
    var position = loseloseHashCode(key);

    if (table[position] !== undefined) {
      var current = table[position].getHead();
      while (current) {
        if (current.element.key === key) {
          table[position].remove(current.element);
          if (table[position].isEmpty()) { // 不留下空链表
            table[position] = undefined;
          }
          return true;
        }
        current = current.next;
      }
    }
    return false;
  };

  // 纯粹为了验证table
  this.getTable = function () {
    return table;
  };
}

2.3.2 线性探查

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

/**
 * 解决hash冲突: 线性探查法
 *
 * 以下纯粹来自书中实现，但其实有不少问题，不推荐！
 *
 * @constructor
 */

function HashTable() {
  var table = [];

  /**
   * 散列函数 lose lose
   *
   * @param key
   * @returns {number}
   */
  var loseloseHashCode = function (key) {
    var hash = 0;
    for (var i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % 37;
  };

  // 键值对辅助类
  var ValuePair = function (key, value) {
    this.key = key;
    this.value = value;

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

  this.put = function (key, value) {
    var position = loseloseHashCode(key);
    console.log(position + ' - ' + key);

    var pair = new ValuePair(key, value);

    // 当目标位置被占用时尝试position++的位置
    if (table[position] === undefined) {
      table[position] = pair;
    } else {
      var index = ++position;
      while (table[index] !== undefined) {
        index++;
      }
      table[index] = pair;
    }
  };

  this.get = function (key) {
    var position = loseloseHashCode(key);

    if (table[position] !== undefined) {
      if (table[position].key === key) {
        return table[position].value;
      } else {
        var index = ++position;
        while (
          table[index] === undefined ||
          table[index].key !== key
          ) {
          index++;
        }
        if (table[index].key === key) {
          return table[index].value;
        }
      }
    }
    return undefined;
  };

  this.remove = function (key) {
    var position = loseloseHashCode(key);

    if (table[position] !== undefined) {
      if (table[position].key === key) {
        table[position] = undefined;
      } else {
        var index = ++position;
        while (
          table[index] === undefined ||
          table[index].key !== key
          ) {
          index++;
        }
        if (table[index].key === key) {
          table[index] = undefined;
        }
      }
    }
  };

  // 纯粹为了验证table
  this.getTable = function () {
    return table;
  };
}

2.4 更好的散列函数 djb2

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

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

2.5 ES6中的Map、WeakMap、Set、WeakSet

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

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

只能用对象作为键。

第7章字典和散列表 (Dictionary and HashTable)

第7章字典和散列表 (Dictionary and HashTable)

1. 字典

2. 散列表

2.1 创建散列表

2.2 散列表和散列集合

2.3 处理散列表中的冲突

2.3.1 分离链接

2.3.2 线性探查

2.4 更好的散列函数 djb2

2.5 ES6中的Map、WeakMap、Set、WeakSet

第7章 字典和散列表 (Dictionary and HashTable)

1. 字典

2. 散列表

2.1 创建散列表

2.2 散列表和散列集合

2.3 处理散列表中的冲突

2.3.1 分离链接

2.3.2 线性探查

2.4 更好的散列函数 djb2

2.5 ES6中的Map、WeakMap、Set、WeakSet

第7章字典和散列表 (Dictionary and HashTable)