1
class HashTable {
2
  constructor(size = 53) {
3
    this.keyMap = new Array(size);
4
  }
5

6
  // 哈希函数
7
  _hash(key) {
8
    let total = 0;
9
    const PRIME = 31;
10
    const MAX_LENGTH = 100;
11

12
    for (let i = 0; i < Math.min(key.length, MAX_LENGTH); i++) {
13
      const char = key[i];
14
      const value = char.charCodeAt(0) - 96; // a=1, b=2...
15
      total = (total * PRIME + value) % this.keyMap.length;
16
    }
17
    return total;
18
  }
19

20
  // 插入键值对
21
  set(key, value) {
22
    const index = this._hash(key);
23

24
    if (!this.keyMap[index]) {
25
      this.keyMap[index] = [];
26
    }
27

28
    // 检查键是否已存在，存在则更新
29
    for (let i = 0; i < this.keyMap[index].length; i++) {
30
      if (this.keyMap[index][i][0] === key) {
31
        this.keyMap[index][i][1] = value;
32
        return;
33
      }
34
    }
35

36
    this.keyMap[index].push([key, value]);
37
  }
38

39
  // 获取值
40
  get(key) {
41
    const index = this._hash(key);
42

43
    if (this.keyMap[index]) {
44
      for (let i = 0; i < this.keyMap[index].length; i++) {
45
        if (this.keyMap[index][i][0] === key) {
46
          return this.keyMap[index][i][1];
47
        }
48
      }
49
    }
50
    return undefined;
51
  }
52

53
  // 删除键值对
54
  delete(key) {
55
    const index = this._hash(key);
56

57
    if (!this.keyMap[index]) return false;
58

59
    for (let i = 0; i < this.keyMap[index].length; i++) {
60
      if (this.keyMap[index][i][0] === key) {
61
        this.keyMap[index].splice(i, 1);
62
        if (this.keyMap[index].length === 0) {
63
          delete this.keyMap[index];
64
        }
65
        return true;
66
      }
67
    }
68
    return false;
69
  }
70

71
  // 获取所有键
72
  keys() {
73
    const keysArr = [];
74
    for (let i = 0; i < this.keyMap.length; i++) {
75
      if (this.keyMap[i]) {
76
        for (let j = 0; j < this.keyMap[i].length; j++) {
77
          if (!keysArr.includes(this.keyMap[i][j][0])) {
78
            keysArr.push(this.keyMap[i][j][0]);
79
          }
80
        }
81
      }
82
    }
83
    return keysArr;
84
  }
85

86
  // 获取所有值
87
  values() {
88
    const valuesArr = [];
89
    for (let i = 0; i < this.keyMap.length; i++) {
90
      if (this.keyMap[i]) {
91
        for (let j = 0; j < this.keyMap[i].length; j++) {
92
          if (!valuesArr.includes(this.keyMap[i][j][1])) {
93
            valuesArr.push(this.keyMap[i][j][1]);
94
          }
95
        }
96
      }
97
    }
98
    return valuesArr;
99
  }
100
}

1
// ES6 Map 是更好的哈希表实现
2
const map = new Map();
3

4
// 设置键值对
5
map.set("name", "Alice");
6
map.set(42, "The Answer");
7
map.set({ id: 1 }, "Object Key");
8

9
// 获取
10
console.log(map.get("name")); // Alice
11

12
// 检查是否存在
13
console.log(map.has(42)); // true
14

15
// 删除
16
map.delete(42);
17

18
// 大小
19
console.log(map.size);
20

21
// 遍历
22
map.forEach((value, key) => {
23
  console.log(key, value);
24
});
25

26
// 清空
27
map.clear();

1
class OptimizedHashTable {
2
  constructor(size = 53) {
3
    this.table = new Array(size);
4
    this.deleted = Symbol("deleted"); // 特殊标记删除
5
  }
6

7
  // 二次探测
8
  _probe(index, i, tableSize) {
9
    return (index + i * i) % tableSize;
10
  }
11

12
  // 双重哈希
13
  _doubleHash(index, i, tableSize, key) {
14
    const hash2 = 1 + (this._hash2(key) % (tableSize - 1));
15
    return (index + i * hash2) % tableSize;
16
  }
17
}

1
class LRUCache {
2
  constructor(capacity) {
3
    this.capacity = capacity;
4
    this.cache = new Map(); // 哈希表 + 维护顺序
5
  }
6

7
  get(key) {
8
    if (!this.cache.has(key)) return -1;
9

10
    const value = this.cache.get(key);
11
    this.cache.delete(key);
12
    this.cache.set(key, value); // 更新为最近使用
13

14
    return value;
15
  }
16

17
  put(key, value) {
18
    if (this.cache.has(key)) {
19
      this.cache.delete(key);
20
    } else if (this.cache.size >= this.capacity) {
21
      // 删除最久未使用的
22
      const oldestKey = this.cache.keys().next().value;
23
      this.cache.delete(oldestKey);
24
    }
25

26
    this.cache.set(key, value);
27
  }
28
}

1
function groupBy(array, keyFn) {
2
  const groups = new Map();
3

4
  for (const item of array) {
5
    const key = typeof keyFn === "function" ? keyFn(item) : item[keyFn];
6

7
    if (!groups.has(key)) {
8
      groups.set(key, []);
9
    }
10

11
    groups.get(key).push(item);
12
  }
13

14
  return groups;
15
}
16

17
// 使用
18
const people = [
19
  { name: "Alice", age: 25 },
20
  { name: "Bob", age: 30 },
21
  { name: "Charlie", age: 25 },
22
];
23

24
const groupedByAge = groupBy(people, "age");
25
console.log(groupedByAge.get(25));
26
// [{ name: 'Alice', age: 25 }, { name: 'Charlie', age: 25 }]