链式地址实现哈希表

字符串的哈希函数如何计算？

• 逐字符累积: hash = hash * 31 + charCodeAt(i);
• 溢出友好: 每步只依赖上一步结果与当前字符编码;
• 取模定桶: 最后对容量取模得到桶下标;
• 冲突: 不同 key 可能得到同一下标, 由桶内链表承接, 见 哈希冲突;

hash(key: string): number {
  let hash = 0;
  for (let index = 0; index < key.length; index++) {
    hash = hash * 31 + key.charCodeAt(index);
  }
  return hash % this.capacity;
}

如何实现写入与覆盖？

• 定位: 按 key 算出桶下标;
• 覆盖: 桶内已存在同 key 节点时改写其 value;
• 新增: 不存在时新建键值对节点并插入该桶的链表;

set(key: string, value: unknown): void {
  const bucket = this.bucket[this.hash(key)];
  const node = bucket.find((item: HashTableItem) => item.key === key);
  if (node) node.value = { key, value };
  else bucket.insert(new DoublyLinkedListNode({ key, value }), bucket.head);
}

如何实现查找与删除？

• 查找: 定位桶后按 key 在链表中匹配, 命中返回 value, 否则返回 null;
• 删除: 命中后把节点从链表摘除, 并返回被删除的键值对;
• 存在性: has 与查找同路, 只返回布尔值;

get(key: string): unknown {
  const bucket = this.bucket[this.hash(key)];
  const node = bucket.find((item: HashTableItem) => item.key === key);
  return node ? node.value.value : null;
}

delete(key: string): unknown {
  const bucket = this.bucket[this.hash(key)];
  const node = bucket.find((item: HashTableItem) => item.key === key);
  if (!node) return null;
  bucket.delete(node);
  return node.value;
}

如何遍历哈希表的所有键值对？

• 方式: 逐桶遍历桶内链表, 依次收集节点数据;
• 三个视图: keys() 收集 key, values() 收集 value, entries() 收集 [key, value];
• 顺序: 遍历顺序由桶下标与链表顺序决定, 不保证插入顺序;