提问式算法速通--Hash

介绍一下散列表这种重要的数据结构，涵盖了其基本概念、内部机制、性能优化以及常见应用场景。

散列表是一种基于键值对存储数据的数据结构。它通过将键映射到数组索引来实现快速的数据检索。内部机制包括哈希函数用于生成索引，处理冲突的方法如开放地址法或链表法。性能优化可通过选择合适的哈希函数和解决冲突的策略，以及动态调整数组大小来实现。常见应用场景包括数据库索引、缓存系统和唯一标识符存储。

使用 JS 模拟一个散列表的使用场景

// 创建一个散列表
let hashTable = {};

// 添加数据
hashTable["name"] = "John";
hashTable["age"] = 30;
hashTable["city"] = "New York";

// 查找数据
let age = hashTable["age"];
console.log("Age:", age);  // 输出: Age: 30

// 更新数据
hashTable["age"] = 31;

// 删除数据
delete hashTable["city"];

// 检查键是否存在
let hasName = "name" in hashTable;
console.log("Has name:", hasName);  // 输出: Has name: true

散列表内部通常使用数组来存储元素，并采用散列函数将键映射到数组索引。一旦发生冲突，可以使用链表或开放地址法来解决冲突。

JS 实现

class HashTable {
  constructor() {
    this.table = new Array(10); // 使用一个长度为10的数组作为散列表
  }

  // 散列函数
  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }

  // 插入数据
  insert(key, value) {
    const index = this.hash(key);
    if (!this.table[index]) {
      this.table[index] = [];
    }
    this.table[index].push({ key, value });
  }

  // 查找数据
  search(key) {
    const index = this.hash(key);
    if (this.table[index]) {
      for (let i = 0; i < this.table[index].length; i++) {
        if (this.table[index][i].key === key) {
          return this.table[index][i].value;
        }
      }
    }
    return undefined;
  }

  // 删除数据
  delete(key) {
    const index = this.hash(key);
    if (this.table[index]) {
      this.table[index] = this.table[index].filter(item => item.key !== key);
    }
  }
}

// 使用散列表
const myHashTable = new HashTable();
myHashTable.insert("name", "John");
myHashTable.insert("age", 30);
myHashTable.insert("city", "New York");

console.log("Age:", myHashTable.search("age")); // 输出: Age: 30

myHashTable.delete("city");

console.log("City:", myHashTable.search("city")); // 输出: City: undefined