哈希表

在计算中, 一个 哈希表(hash table 或hash map) 是一种实现 关联数组(associative array) 的抽象数据类型, 该结构可以将 键映射到值。

哈希表使用 哈希函数/散列函数 来计算一个值在数组或桶(buckets)中或槽(slots)中对应的索引,可使用该索引找到所需的值。

理想情况下,散列函数将为每个键分配给一个唯一的桶(bucket),但是大多数哈希表设计采用不完美的散列函数,这可能会导致"哈希冲突(hash collisions)",也就是散列函数为多个键(key)生成了相同的索引,这种碰撞必须 以某种方式进行处理。

Hash Table

通过单独的链接解决哈希冲突

Hash Collision

class HashTable {
  constructor() {
    this.table = {};
  }

  // 哈希函数
  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % 37; // 选择一个适当的哈希表大小，如质数
  }

  // 向哈希表中插入键值对
  put(key, value) {
    const index = this.hash(key);
    if (!this.table[index]) {
      this.table[index] = {};
    }
    this.table[index][key] = value;
  }

  // 从哈希表中获取指定键的值
  get(key) {
    const index = this.hash(key);
    if (this.table[index] && this.table[index][key]) {
      return this.table[index][key];
    }
    return undefined;
  }

  // 从哈希表中移除指定键值对
  remove(key) {
    const index = this.hash(key);
    if (this.table[index] && this.table[index][key]) {
      delete this.table[index][key];
      if (Object.keys(this.table[index]).length === 0) {
        delete this.table[index];
      }
      return true;
    }
    return false;
  }

  // 检查哈希表中是否存在指定键
  contains(key) {
    const index = this.hash(key);
    return !!(this.table[index] && this.table[index][key]);
  }

  // 返回哈希表中的所有键
  keys() {
    const keys = [];
    for (const index in this.table) {
      for (const key in this.table[index]) {
        keys.push(key);
      }
    }
    return keys;
  }

  // 返回哈希表中的所有值
  values() {
    const values = [];
    for (const index in this.table) {
      for (const key in this.table[index]) {
        values.push(this.table[index][key]);
      }
    }
    return values;
  }
}

const hashTable = new HashTable();
hashTable.put("apple", 10);
hashTable.put("banana", 20);
console.log(hashTable.get("apple")); // 输出: 10
console.log(hashTable.contains("banana")); // 输出: true
console.log(hashTable.remove("banana")); // 输出: true
console.log(hashTable.contains("banana")); // 输出: false
console.log(hashTable.keys()); // 输出: ["apple"]
console.log(hashTable.values()); // 输出: [10]

参考

• Wikipedia
• YouTube