用TypeScript写个哈希表——说白了就是“找东西利器”
哈希表这个东西呢，跟生活中找钥匙差不多。想象一下，你每次出门都乱丢钥匙，回家要用半小时才能找到它。如果有个哈希表，那你一秒就能知道钥匙放哪了。所以今天我们来用TypeScript写个哈希表，别担心，跟朋友聊天一样简单。
什么是哈希表？
哈希表就像给你的钥匙分配了个专属抽屉，你把钥匙往哈希表里一丢，它自己找个抽屉放好，等你要用的时候，你直接问它：“我的钥匙在哪呢？” 它马上告诉你在哪个抽屉里，秒找。是不是很方便？那咱现在就来动手写一个。
代码部分——慢慢来，不急
我们来一步步写哈希表，代码都标注好，解释清楚，放心不会扯得太远。
class HashTable<T> {
// 创建一个桶数组，桶就是个小抽屉，里面装着key-value对
private buckets: Array<Array<[string, T]>>;
// 哈希表的大小，也就是有多少个抽屉
private size: number;
constructor(size: number) {
this.size = size;
// 创建一个指定大小的桶数组，初始每个位置是个空数组
this.buckets = new Array(size).fill(null).map(() => []);
// 为啥要fill(null)？TypeScript不允许你直接在空数组上map，得先填充一波。
}
// 哈希函数，负责把key变成数字，这样才能找到对应的桶
private hash(key: string): number {
let hash = 0;
for (let i = 0; i < key.length; i++) {
// 计算哈希值，用ASCII码+位置的算法，最后取模，得到抽屉位置
hash = (hash + key.charCodeAt(i) * i) % this.size;
}
return hash; // 这个数字就是抽屉的索引
}
// 插入或更新键值对
set(key: string, value: T): void {
const index = this.hash(key); // 通过哈希函数找到抽屉
const bucket = this.buckets[index]; // 拿到对应的抽屉
// 先看看抽屉里有没有相同的key
for (let i = 0; i < bucket.length; i++) {
const pair = bucket[i];
if (pair[0] === key) {
// 找到了，就更新value
pair[1] = value;
return;
}
}
// 没找到？那就直接把新的key-value对扔进去
bucket.push([key, value]);
}
// 查找键值对
get(key: string): T | undefined {
const index = this.hash(key); // 先找到抽屉
const bucket = this.buckets[index]; // 拿出这个抽屉
// 遍历抽屉里的东西，看看有没有这个key
for (const pair of bucket) {
if (pair[0] === key) {
return pair[1]; // 找到了，直接返回value
}
}
return undefined; // 没找到，给你个undefined，你懂的
}
// 删除键值对
remove(key: string): boolean {
const index = this.hash(key); // 一样先找到抽屉
const bucket = this.buckets[index]; // 取出这个抽屉
// 遍历抽屉，找到要删的key
for (let i = 0; i < bucket.length; i++) {
const pair = bucket[i];
if (pair[0] === key) {
bucket.splice(i, 1); // 找到后直接删掉
return true; // 成功删除，返回true
}
}
return false; // 没找到就返回false，删除失败
}
}
说点需要注意的
- 构造函数那点事儿
为啥得先fill(null)？TypeScript不让直接在空数组上map()，所以你得先用fill(null)把它填满，再通过map()每个位置给它创建一个空的抽屉。不这样搞，TypeScript就会给你脸色看（直接报错）。 - 哈希函数到底在干嘛？
你可能好奇这hash()函数到底干啥。其实它就是把字符串变成一个数字，方便找到你想要的抽屉。这里我们用了每个字符的ASCII码乘以它在字符串里的位置，最后对哈希表的大小取模。简单、暴力、够用！但别想太复杂，咱写这个不是为了拿诺贝尔奖，能用就行。 - 冲突咋处理？
冲突是难免的，两个key哈希到同一个位置就叫冲突。这里我们用了“链地址法”来处理冲突，简单来说就是一个桶可以存多个键值对，每次冲突时就往同一个桶里塞。不过，这种方式容易导致某些桶变得过于拥挤，性能就可能下降。如果你想避免这种情况，可以试试“开放地址法”（Open Addressing）。它的原理是，如果一个桶已经有数据了，哈希表会去找下一个空的桶来放新数据。总的来说，两种方法各有优缺点，你可以根据实际需求选择。 - 时间复杂度
哈希表的优势是大多数操作都是 O(1) 时间复杂度，也就是速度快！不过当冲突多了，桶里东西多了，链地址法会退化成 O(n)，查找变得慢。所以，哈希表适合用在冲突不太多的场景，或者你可以用更复杂的数据结构，比如平衡二叉树来处理冲突，提升查找效率。
然后呢？
好了，你已经有了一个能插入、查找、删除数据的哈希表了。接下来如果你想进一步优化，我们可以聊聊其他的冲突处理方式，比如“开放地址法”——这玩意儿可以让你别再往一个抽屉里塞太多东西。另外呢，像红黑树这种高级结构，也可以用来提升性能，后面有机会我们再详细聊。