简介

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。
也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。
这个映射函数称做散列函数，存放记录的数组称做散列表。

const table = []; // 记录的数组，即散列表
// 散列函数
const computeHashCode = function(key) {
  // 通过某种算法，算出数值 code
  // 算法可以是 md5、SHA-1 等
  // JS 中有 charCodeAt 方法可以获取字符的 unicode 编码，也可以作为一种算法。
  // ...
  return code; // 将数值返回
}
// 设置值
const set = (key, value) => {
  const position = computeHashCode(key); 
  table[position] = value;
}

补充一下，散列表其实也可以是对象，只要算出的 hashCode 是字符串就可以。在下文，我们以数组和 JS 的 charCodeAt 来模拟散列表。

散列函数的特点

确定性
- 输出不同，输入肯定不同
散列碰撞（散列冲突）
- 输入输出不一定一一对应，多个输入可以对应一个输出
不可逆性
- 输出内容无法反推输入内容
混淆特性
- 输入即使变化很小，输出的变化会很大

JS 实现散列表

普通散列表

class HashTable {
  table = [];
  // 散列函数
  static computeHashCode(key) {
    let code = 0;
    for (let i = 0; i < key.length; i++) {
      code += key.charCodeAt(i)
    }
    // 这里对 37 取余，只是为了配合下面举例，讲解散列碰撞
    // 换成其他的也行
    return code % 37;
  }
  // 设置值
  set(key, value) {
    const position = HashTable.computeHashCode(key);
    this.table[position] = value;
  }
  get(key) {
    const position = HashTable.computeHashCode(key);
    return this.table[position]
  }
  remove(key) {
    const position = HashTable.computeHashCode(key);
     delete this.table[position]
  }
}
const hashTable = new HashTable()
// 添加值并打印输出的话可能会得到相同的hash值
hashTable.set('Tyrion', 'aaa@qq.com') // position = 16
hashTable.set('Aaron', 'bbb@qq.com') // position = 16

解决散列碰撞

链表法

使用链表来辅助存储。对于普通的散列表，本身在某个位置存储的是一个值。
而我们知道链表是有序的元素的集合，拥有存储元素本身的值和指向下一个值的引用，那么我们将某个位置本来要存储的值换成链表的形式，这就意味着我们在这个位置可以存放多个值了。

class Node {
  constructor(value, next) {
    this.value = value;
    this.next = next;
  }
}
class NodeList {
  constructor() {
    this.head = new Node(); // 哑节点
    this.tail = this.head
  }
  append(value, next) {
    const node = new Node(value, next);
    this.tail.next = node;
    this.tail = node;
  }
  getList() {
    return this.head;
  }
}
module.exports = NodeList;

const NodeList = require('./NodeList')
class HashTable {
  table = [];
  // 散列函数
  static computeHashCode(key) {
    let code = 0;
    for (let i = 0; i < key.length; i++) {
      code += key.charCodeAt(i)
    }
    // 这里对 37 取余，只是为了配合下面举例，讲解散列碰撞
    // 换成其他的也行
    return code % 37;
  }
  // 设置值
  set(key, value) {
    const position = HashTable.computeHashCode(key);
    if (!this.table[position]) this.table[position] = new NodeList();
    this.table[position].append({ key, value });
  }
  get(key) {
    const position = HashTable.computeHashCode(key);
    let head = this.table[position].getList().next;
    while (head) {
      if (head.value.key === key) return head.value.value;
      head = head.next
    }
  }
  remove(key) {
    const position = HashTable.computeHashCode(key);
    let pre = this.table[position].getList();
    let p = pre.next
    while (p) {
      if (p.value.key === key) {
        pre.next = p.next
      }
      pre = p;
      p = p.next
    }
  }
}
const hashTable = new HashTable()
// 添加值并打印输出的话可能会得到相同的hash值
hashTable.set('Tyrion', 'aaa@qq.com') // position = 16
hashTable.set('Aaron', 'bbb@qq.com') // position = 16
hashTable.get('Tyrion') // aaa@qq.com
hashTable.get('Aaron')  // bbb@qq.com

参考资料

《数据结构之散列表》