【性能优化】1.4 [内存查找] 哈希索引
1.4 哈希索引
哈希索引可以理解为序号定位的延伸。
使用某个函数将被查找键值计算成一个 1…M 之间的自然数，称为该记录的哈希值，此函数称为哈希函数。将序表 T 的记录按哈希值分组后可得到一个长度为 M 的两层序列 H（就是 SPL 的 group@n 运算，其中可能有空成员）。现在可以对 H 使用序号定位方法，计算查找值的哈希函数后，即可定位到相应的分组子集，然后在这个分组子集中再使用顺序或二分查找方式进一步找到目标值。这个事先要做的分组运算结果，称为哈希索引。
A |
|
1 |
=20000.sort(rand()).to(10000) |
2 |
=A1.new(~:id, …) |
3 |
=A2.group(id%100+1).(~.sort(id)) |
4 |
=A3(2345%100+1).select@b1(id-2345) |
在 A3 中使用取余数加 1 作为哈希函数，将 10000 条记录分成 100 个组中。在 A4 中先序号定位再二分查找，涉及数据量只有全数据集的 100 分之一，比对次数会少 log2100 次。
取余数也是针对整数类型查找键的常用哈希函数。
如果运气好，H 中成员的成员个数（H 的成员是个集合）比较平均（都接近 N/M 个），由于哈希值计算和序号定位查找的复杂度为 O(1)，则建立哈希索引后的查找复杂度将降低 M 倍，和查找长度为 N/M 的序表相当。如果运气不好，H 中成员的成员个数分布很不平均，哈希索引查找在极端情况时有可能并不会提高性能，这取决于哈希函数的设计和原数据集中被查找键值的分布情况。
不过，运气通常不会太差，哈希索引大多数情况都会获得较好的性能提升，甚至能在原数据无序时比排序后使用二分法更有优势。
哈希索引的缺点在于需要占用内存空间来保存这个索引，而想速度更快，就需要更大的索引，也就会占用更大的空间。
SPL 提供了针对主键的哈希索引，会自动使用系统内置的哈希函数。
A |
|
1 |
=20000.sort(rand()).to(10000) |
2 |
=A1.new(~:id, …).keys@i(id) |
3 |
=A2.find(12345) |
4 |
=A1.new(~:id, …).keys@i(id;100) |
5 |
=A4.find(23456) |
在设置主键时用 @i 可以同时建立索引，在 find 查找时如果有索引将会自动使用。建索引时还可以再用参数控制哈希索引的长度（即 M 值），读者可以尝试不同的哈希索引长度对性能的影响。
