数据结构Typescript之哈希表实现详解

什么是哈希表

哈希表（Hash Table）又称为散列表，是一种根据关键字(Key)直接访问内存存储位置的数据结构。通俗的解释就是利用一个哈希函数（Hash Function）将关键字映射到哈希表中的一个位置（索引）来进行访问，从而快速、高效地查找、插入、删除元素。

哈希表的实现

本文将介绍使用Typescript实现一种基于闭散列（Closed Hashing，也称为拉链法Chaining）的简单哈希表。以下为该哈希表的基本实现思路：

1. 声明一个“链表节点”类，用于存储哈希表中的元素;
2. 声明一个哈希表类，该类包含以下方法：
3. hash(key: string): number：基于关键字计算索引值；
4. put(key: string, value: any): void：向哈希表中插入元素；
5. remove(key: string): boolean：从哈希表中删除元素；
6. get(key: string): any：在哈希表中查找指定的元素；
7. print(): void：输出哈希表的所有元素。

下面让我们详细看一下这些方法的实现。

基于链表节点实现哈希表元素

先声明一个“链表节点”类，用于存储哈希表中的元素，包含元素的关键字（key）和值（value）两个属性：

class Node {
  constructor(public key: string, public value: any) {}
}

基于闭散列实现哈希表

接下来，我们需要根据关键字计算出哈希表元素的索引位置。为了能够直接通过关键字来计算哈希表元素的索引位置，我们需要编写一个哈希函数。这里我们使用最简单的字符串哈希函数——将字符串按字符拆分，并将其所在字符位置的ASCII值相加，得出的结果再取余哈希表的长度，得到哈希表元素的索引位置：

class HashTable {
  private table: any[] = [];

  private loseloseHashCode(key: string): number {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }
}

在上述代码中，我们通过table数组来存储哈希表，loseloseHashCode函数就是我们的哈希函数。

插入元素

知道如何计算关键字的哈希值之后，我们就可以向哈希表中插入元素了。插入元素有两种情况：

1. 当哈希表中不存在该关键字时，直接将元素添加到哈希表中；
2. 当哈希表中已经存在该关键字时，更新该元素的值。

代码如下：

class HashTable {
  // ...

  public put(key: string, value: any): void {
    const position = this.loseloseHashCode(key);
    if (this.table[position] === undefined) {
      this.table[position] = new LinkedList();
    }
    this.table[position].append(new Node(key, value));
  }
}

当table数组中的某个元素为undefined时，说明该位置上未曾插入过元素。我们可以新建一个链表，并将该元素插入到链表的末尾。

当table数组中已经存在某个链表时，说明该位置上已经有元素，我们只需将新元素插入到该链表的末尾即可。

删除元素

删除元素也有两种情况：

1. 当哈希表中不存在该关键字时，直接返回false；
2. 当哈希表中存在该关键字时，删除该元素并返回true。

代码如下：

class HashTable {
  // ...

  public remove(key: string): boolean {
    const position = this.loseloseHashCode(key);
    const list = this.table[position];
    if (list !== undefined && !list.isEmpty()) {
      let current = list.getHead();
      while (current !== null) {
        if (current.element.key === key) {
          list.remove(current.element);
          if (list.isEmpty()) {
            this.table[position] = undefined;
          }
          return true;
        }
        current = current.next;
      }
    }
    return false;
  }
}

首先我们和插入操作一样找到该关键字所在的索引位置position以及对应的链表list。然后用循环遍历该链表，找到指定的元素，并将其从链表中删除。最后，我们还需要检查该链表是否为空，如果为空，需要将table数组中该元素的值设为undefined。

查找元素

查找元素也是基于关键字计算出哈希值，然后获取该关键字在哈希表中对应的链表。查找元素的方法只需要顺序遍历该链表，并返回找到的元素即可：

class HashTable {
  // ...

  public get(key: string): any {
    const position = this.loseloseHashCode(key);
    const list = this.table[position];
    if (!list.isEmpty()) {
      let current = list.getHead();
      while (current !== null) {
        if (current.element.key === key) {
          return current.element.value;
        }
        current = current.next;
      }
    }
  }
}

输出哈希表元素

输出哈希表的所有元素非常简单，只需要遍历每个链表并输出其节点元素的key和value属性即可：

class HashTable {
  // ...

  public print(): void {
    for (let i = 0; i < this.table.length; i++) {
      const list = this.table[i];
      if (list !== undefined && !list.isEmpty()) {
        let current = list.getHead();
        while (current !== null) {
          console.log(`${current.element.key} -> ${current.element.value}`);
          current = current.next;
        }
      }
    }
  }
}

示例说明

我们可以尝试向哈希表中插入以下元素：

const hashTable = new HashTable();
hashTable.put("Tom", "programmer");
hashTable.put("Jerry", "designer");
hashTable.put("Mary", "teacher");
hashTable.put("Peter", "student");
hashTable.put("John", "doctor");

然后，我们可以查找哈希表中的某个元素：

hashTable.get("Mary"); // "teacher"

或者从哈希表中删除某个元素：

hashTable.remove("Peter"); // true
hashTable.get("Peter"); // undefined

最后输出整个哈希表中的元素：

hashTable.print();

输出结果如下：

Tom -> programmer
Jerry -> designer
Mary -> teacher
John -> doctor

结论

借助于Typescript强大的类型检查功能，我们可以在代码编写的过程中更加自信和高效地开发出高质量的数据结构。虽然这种实现方式可能不是最高效的，但它值得我们学习和掌握，并为我们日常工作中的需求提供了不同的思路和实现方式。