TypeScript 基础数据结构哈希表 HashTable 教程

什么是哈希表 HashTable

在计算机科学中，哈希表（HashTable），也叫散列表，是根据关键码值(Key­value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫作哈希函数，存放记录的数组叫作哈希表。

如何实现哈希表 HashTable

哈希表的实现过程主要包括两步，哈希函数的设计和哈希冲突的解决。

哈希函数的设计

哈希函数将不同的值映射到不同的位置，因此哈希函数的设计是哈希表的重要部分。常见的哈希函数包括除数取余法、乘法取整法、数字分析法等等。

以下是一个使用除数取余法实现的简单哈希函数：

function hashFn(key: string, length: number): number {
  let total = 0
  for (let i = 0; i < key.length; i++) {
    total += key.charCodeAt(i)
  }
  return total % length
}

该函数的输入参数为一个字符串类型的键值 key 和表的长度 length，输出参数为该键值在表中的位置。该哈希函数的实现过程为求出字符串的 ASCII 码值总和并对表长取余。

哈希冲突的解决

由于哈希函数的映射过程是将多个不同的输入映射到同一个哈希值，因此可能会存在不同的输入具有相同的哈希值的情况，这种现象称为哈希冲突。常见的哈希冲突解决方法包括拉链法和线性探测法等等。

以下是一个使用拉链法实现的哈希表：

class HashTable {
  private storage: any[]
  private length: number

  constructor() {
    this.storage = []
    this.length = 0
  }

  private hashFn(key: string, length: number): number {
    let total = 0
    for (let i = 0; i < key.length; i++) {
      total += key.charCodeAt(i)
    }
    return total % length
  }

  public getItem(key: string): any {
    const index = this.hashFn(key, this.length)
    if (!this.storage[index]) {
      return null
    }
    for (let i = 0; i < this.storage[index].length; i++) {
      if (this.storage[index][i][0] === key) {
        return this.storage[index][i][1]
      }
    }
    return null
  }

  public setItem(key: string, value: any): void {
    const index = this.hashFn(key, this.length)
    if (!this.storage[index]) {
      this.storage[index] = []
    }
    for (let i = 0; i < this.storage[index].length; i++) {
      if (this.storage[index][i][0] === key) {
        this.storage[index][i][1] = value
        return
      }
    }
    this.storage[index].push([key, value])
    this.length++
  }

  public removeItem(key: string): void {
    const index = this.hashFn(key, this.length)
    if (!this.storage[index]) {
      return
    }
    for (let i = 0; i < this.storage[index].length; i++) {
      if (this.storage[index][i][0] === key) {
        this.storage[index].splice(i, 1)
        this.length--
        return
      }
    }
  }
}

该实现使用了数组来存储哈希表，并使用拉链法来解决哈希冲突。

哈希表 HashTable 的应用场景

哈希表的高效性能使其被广泛应用于各种场景中，例如：

• 缓存
• 数据库索引
• 语法分析器

示例说明

示例一

const hashTable = new HashTable()
hashTable.setItem('name', '张三')
hashTable.setItem('age', 20)

console.log(hashTable.getItem('name')) // 输出：张三
console.log(hashTable.getItem('age')) // 输出：20

hashTable.removeItem('age')
console.log(hashTable.getItem('age')) // 输出：null

以上示例创建了一个哈希表，并向其中添加了两个键值对 "name": "张三" 和 "age": 20。随后，示例中通过 getItem 和 removeItem 方法获取和移除了其中的一个键值对，并分别输出了获取结果。

示例二

const products = [
  { name: 'iPhone', price: 8000 },
  { name: 'iPad', price: 6000 },
  { name: 'MacBook', price: 20000 }
]

const hashTable = new HashTable()
products.forEach(product => hashTable.setItem(product.name, product.price))

console.log(hashTable.getItem('iPhone')) // 输出：8000
console.log(hashTable.getItem('iPad')) // 输出：6000
console.log(hashTable.getItem('MacBook')) // 输出：20000

以上示例将一个商品数组转换为一个哈希表，并通过 setItem 方法将商品名称作为键值，商品价格作为值存储在哈希表中。随后，示例中通过 getItem 方法获取了其中三个商品的价格并分别输出了获取结果。