爱囡囡，爱前端

0%

TypeScript数据结构与算法：散列表

发表于 分类于 ， ，

上一篇《TypeScript 数据结构与算法：字典》实现了 Typescript 中字典的数据结构与算法，本篇继续实现散列表。

散列表（Hash Map，也叫哈希表 ）是一种特殊的字典实现。在一个普通的字典中，通过键直接来获取值。但是在散列表中，可以通过哈希函数先将键映射为一个内存地址，所以存储的结构由键 -> 值 变为了 键 -> 地址 -> 值。所以在查询时，可以通过键映射后的地址快速取值，避免了耗费性能的迭代查值过程。

散列表有一些在计算机科学中应用的例子。因为它是字典的一种实现，所以可以用来对数据库进行索引。当我们在关系型数据库（如 MySQL、Microsoft SQL Server、Oracle，等等）中创建一个新的表时，同时创建一个索引可以更快地查询到记录的 key。在这种情况下，散列表可以用来保存键和对表中记录的引用。

数据结构

注意：在 JS 引擎内部已经将 Map 和 Object 优化为了散列表。所以本篇只是实现类似的优化过程，并没有实际的优化效果。

哈希函数

因为转换出来的 hashCode 是一个内存地址，所以这个哈希函数的设计最好能满足下面三个原则：

  1. 哈希值是一个相对比较短的非负整数；
  2. 相同的键计算储的哈希值必需相同；
  3. 不同的键计算出来的哈希值应该不同；

toStrFn 辅助方法

由于键有可能是各种数据类型，所以第一步首先要把键映射为统一的 String 数据类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @description: 将item转换为字符串
 */
export function defaultToString(item: any): string {
  // 对于 null undefined和字符串的处理
  if (item === null) {
    return 'NULL';
  } else if (item === undefined) {
    return 'UNDEFINED';
  } else if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  }
  // 其他情况时调用数据结构自带的 toString 方法
  return item.toString();
}

loselose 函数

先从一个简单的哈希函数 loselose 开始，其实算法就是将字符串各个位上的 UTF-16 Unicode 值加起来，然后对 37 取余即为哈希值：

1
2
3
4
5
6
7
8
9
10
11
const loseloseHashCode = (key: K): number => {
  if (typeof key === 'number') {
    return key;
  }
  const tableKey = this.toStrFn(key);
  let hash = 0;
  for (let i = 0; i < tableKey.length; i++) {
    hash += tableKey.charCodeAt(i);
  }
  return hash % 37;
};

djb2 函数

可以发现，上述的 loselose 哈希算法有一个很重大缺点，就是不同的源字符串导致出现相同哈希值的概率很高，比如 Jonathan、Jamie、Sue 和 Aethelwulf 会有相同的哈希值 5。

所以改进一下算法，将 hash 初始值设置 5381，每次迭代时将 hash 乘 33 再累加，最后对 1013 取余，使得出现重复哈希值得概率大幅度降低。

为什么是 DJB2 算法中为 5381、33、1013，而为什么 losolose 算法是 0、0、37，可以看stackOverflow上的一篇回答，简单来说，这些数都是一些幻数，为了减少重复概率而设计的。

1
2
3
4
5
6
7
8
9
10
11
const djb2HashCode = (key: K): number => {
  if (typeof key === 'number') {
    return key;
  }
  const tableKey = this.toStrFn(key);
  let hash = 5381;
  for (let i = 0; i < tableKey.length; i++) {
    hash = hash * 33 + tableKey.charCodeAt(i);
  }
  return hash % 1013;
};

散列表

有了计算哈希值的算法，接下来就可以实现散列表的数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import { defaultToString } from '../util';

export default class HashTable<K, V> {
  protected table: Map<number, V>;

  constructor(protected toStrFn: (key: K) => string = defaultToString) {
    this.table = new Map();
  }

  /**
   * @description: 哈希函数
   */
  private djb2HashCode(key: K): number {
    if (typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 5381;
    for (let i = 0; i < tableKey.length; i++) {
      hash = hash * 33 + tableKey.charCodeAt(i);
    }
    return hash % 1013;
  }

  /**
   * @description: 计算键的哈希值
   */
  hashCode(key: K): number {
    return this.djb2HashCode(key);
  }

  /**
   * @description: 更新散列表
   */
  put(key: K, value: V): boolean {
    if (key != null && value != null) {
      const position = this.hashCode(key);
      this.table.set(position, value);
      return true;
    }
    return false;
  }

  /**
   * @description: 根据键获取值
   */
  get(key: K): V {
    return this.table.get(this.hashCode(key));
  }

  /**
   * @description: 根据键移除值
   */
  remove(key: K): boolean {
    return this.table.delete(this.hashCode(key));
  }

  /**
   * @description: 返回内部table
   */
  getTable(): Map<number, V> {
    return this.table;
  }

  /**
   * @description: 返回是否为空散列表
   */
  isEmpty(): boolean {
    return this.size() === 0;
  }

  /**
   * @description: 散列表的大小
   */
  size(): number {
    return this.table.size;
  }

  /**
   * @description: 清空散列表
   */
  clear() {
    this.table.clear();
  }

  /**
   * @description: 替代默认的toString
   */
  toString(): string {
    if (this.isEmpty()) {
      return '';
    }
    let objStringList = [];
    for (const [hashCode, value] of this.table) {
      objStringList.push(`{${hashCode} => ${value}}`);
    }
    return objStringList.join(',');
  }
}

这里的散列表实现的其实并不完整，因为即使将 loselose 算法改为使用了 DJB 算法，或者说即使现在非常著名的 MD5、SHA、CRC 哈希算法，也没办法避免这用哈希冲突。原因就是由多映射到少，必然会出现冲突。导致新添加的键值对如果重复时会覆盖之前添加的值，所以这里需要对算法进行改进。

分离链接散列表

分离链接法（Separate Chaining Hash Table）是对散列表数据结构的改进，为散列表的每一个 hashcode 创建一个链表，并将键值对存储在链表中，它是解决冲突的最简单的方法。

下面是分离链接散列表的实现（不能仅存储值，需要存储整个键值对）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
import { defaultToString } from '../util';
import LinkedList from './linked-list';

export default class HashTableSeparateChaining<K, V> {
  protected table: Map<number, LinkedList<{ key: K; value: V }>>;

  constructor(protected toStrFn: (key: K) => string = defaultToString) {
    this.table = new Map();
  }

  /**
   * @description: 哈希函数
   */
  private loseloseHashCode(key: K): number {
    if (typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
  }

  /**
   * @description: 哈希函数封装
   */
  hashCode(key: K): number {
    return this.loseloseHashCode(key);
  }

  /**
   * @description: 更新散列表
   */
  put(key: K, value: V): boolean {
    if (key != null && value != null) {
      const position = this.hashCode(key);

      // 当该hashcode不存在时，先创建一个链表
      if (this.table.get(position) == null) {
        this.table.set(position, new LinkedList<{ key: K; value: V }>());
      }
      // 再给链表push值
      this.table.get(position).push({ key, value });
      return true;
    }
    return false;
  }

  /**
   * @description: 根据键获取值
   */
  get(key: K): V {
    const position = this.hashCode(key);
    const linkedList = this.table.get(position);
    if (linkedList != null && !linkedList.isEmpty()) {
      let current = linkedList.getHead();
      // 去链表中迭代查找键值对
      while (current != null) {
        if (current.element.key === key) {
          return current.element.value;
        }
        current = current.next;
      }
    }
    return undefined;
  }

  /**
   * @description: 根据键移除值
   */
  remove(key: K): boolean {
    const position = this.hashCode(key);
    const linkedList = this.table.get(position);
    if (linkedList != null && !linkedList.isEmpty()) {
      let current = linkedList.getHead();
      while (current != null) {
        if (current.element.key === key) {
          linkedList.remove(current.element);
          // 关键的一点，当链表为空以后，需要在tabel中删除掉hashcode
          if (linkedList.isEmpty()) {
            this.table.delete(position);
          }
          return true;
        }
        current = current.next;
      }
    }
    return false;
  }

  /**
   * @description: 返回是否为空散列表
   */
  isEmpty(): boolean {
    return this.size() === 0;
  }

  /**
   * @description: 散列表的大小
   */
  size(): number {
    let count = 0;
    // 迭代每个链表，累计求和
    for (const [hashCode, linkedList] of this.table) {
      count += linkedList.size();
    }
    return count;
  }

  /**
   * @description: 清空散列表
   */
  clear() {
    this.table.clear();
  }

  /**
   * @description: 返回内部table
   */
  getTable() {
    return this.table;
  }

  /**
   * @description: 替代默认的toString
   */
  toString(): string {
    if (this.isEmpty()) {
      return '';
    }

    let objStringList = [];
    for (const [hashCode, linkedList] of this.table) {
      let node = linkedList.getHead();
      while (node) {
        objStringList.push(`{${node.element.key} => ${node.element.value}}`);
        node = node.next;
      }
    }
    return objStringList.join(',');
  }
}

线性探查散列表

另一种解决冲突的方法是线性探查（Linear Probing Hash Table）。之所以称作线性，是因为它处理冲突的方法是将键值对直接存储到表中，而不是像分离链接一样存储在单独的数据结构中。

当想向表中添加一个新键值对的时候，如果索引为 hashCode 的位置已经被占据了，就尝试 hashCode + 1 的位置。如果 hashCode + 1 的位置也被占据了，就尝试 hashCode + 2 的位置，以此类推，直到在散列表中找到一个空闲的位置。

在删除的时候，需要检查是否有必要将后面的键值对向前挪动移动，避免出现空位置。下图展现了这个过程：

下面是线性探查散列表的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
import { defaultToString } from '../util';

export default class HashTableLinearProbing<K, V> {
  protected table: Map<number, { key: K; value: V }>;

  constructor(protected toStrFn: (key: K) => string = defaultToString) {
    this.table = new Map();
  }

  /**
   * @description: 哈希函数
   */
  private loseloseHashCode(key: K): number {
    if (typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
  }

  /**
   * @description: 哈希函数封装
   */
  hashCode(key: K): number {
    return this.loseloseHashCode(key);
  }

  /**
   * @description: 更新散列表
   */
  put(key: K, value: V): boolean {
    if (key != null && value != null) {
      const position = this.hashCode(key);

      if (this.table.get(position) == null) {
        // 当hashcode位置为空时，可以直接添加
        this.table.set(position, { key, value });
      } else {
        // 否则需要迭代查找最近的空位置再添加
        let index = position + 1;
        while (this.table.get(index) != null) {
          index++;
        }
        this.table.set(index, { key, value });
      }
      return true;
    }
    return false;
  }

  /**
   * @description: 根据键获取值
   */
  get(key: K): V {
    const position = this.hashCode(key);

    if (this.table.get(position) != null) {
      // 如果查到的hashcode位置就是要查的key，则直接返回
      if (this.table.get(position).key === key) {
        return this.table.get(position).value;
      }
      // 否则需要迭代着向下查找
      let index = position + 1;
      while (
        this.table.get(index) != null &&
        this.table.get(index).key !== key
      ) {
        index++;
      }
      if (this.table.get(index) != null && this.table.get(index).key === key) {
        return this.table.get(position).value;
      }
    }
    // 最后也没查到，就返回undefined
    return undefined;
  }

  /**
   * @description: 根据键移除值
   */
  remove(key: K): boolean {
    const position = this.hashCode(key);

    if (this.table.get(position) != null) {
      // 同理，如果hashcode对应位置就是要查的key，则直接删除
      if (this.table.get(position).key === key) {
        this.table.delete(position);
        // 删除后处理副作用
        this.verifyRemoveSideEffect(key, position);
        return true;
      }
      // 同理，如果hashcode对应的位置不是要查的key，就迭代查到
      let index = position + 1;
      while (
        this.table.get(index) != null &&
        this.table.get(index).key !== key
      ) {
        index++;
      }
      if (this.table.get(index) != null && this.table.get(index).key === key) {
        this.table.delete(index);
        // 同样在删除后处理副作用
        this.verifyRemoveSideEffect(key, index);
        return true;
      }
    }
    return false;
  }

  /**
   * @description: 处理移除键值对后的副作用
   */
  private verifyRemoveSideEffect(key: K, removedPosition: number) {
    const hash = this.hashCode(key);
    let index = removedPosition + 1;
    // 迭代着处理后面的每一个键值对
    while (this.table.get(index) != null) {
      const posHash = this.hashCode(this.table.get(index).key);
      // 挨个向前挪动，关键点在于，hashcode值比较小的键值对尽量先向前补位
      // 详细的说：如果当前元素的 hash 值小于或等于原始的 hash 值
      // 或者当前元素的 hash 值小于或等于 removedPosition（也就是上一个被移除 key 的 hash 值），
      // 表示我们需要将当前元素移动至 removedPosition 的位置
      if (posHash <= hash || posHash <= removedPosition) {
        this.table.set(removedPosition, this.table.get(index));
        this.table.delete(index);
        removedPosition = index;
      }
      index++;
    }
  }

  /**
   * @description: 返回是否为空散列表
   */
  isEmpty(): boolean {
    return this.size() === 0;
  }

  /**
   * @description: 散列表的大小
   */
  size(): number {
    return this.table.size;
  }

  /**
   * @description: 清空散列表
   */
  clear() {
    this.table.clear();
  }

  /**
   * @description: 返回内部table
   */
  getTable(): Map<number, { key: K; value: V }> {
    return this.table;
  }

  /**
   * @description: 替代默认的toString
   */
  toString(): string {
    if (this.isEmpty()) {
      return '';
    }

    let objStringList = [];
    for (const [hashCode, { key, value }] of this.table) {
      objStringList.push(`{${key} => ${value}}`);
    }
    return objStringList.join(',');
  }
}

下一篇来分析树。

前端记事本，不定期更新，欢迎关注！

👆 全文结束，棒槌时间到 👇