大规模最小完美哈希函数：快速且可扩展
27 浏览量
更新于2024-07-14
收藏 759KB PDF 举报
“Fast and Scalable Minimal Perfect Hashing for Massive Key Sets”是一篇2017年的计算机科学研究论文，由Antoine Limasset、Guillaume Rizk、Rayan Chikhi和Pierre Peterlongo共同撰写。该研究关注的是在大规模键集上实现快速且可扩展的最小完美哈希函数。
最小完美哈希函数是一种空间效率高且无碰撞的哈希技术，适用于静态集合。现有的算法和实现方法在处理大量输入元素时存在实际限制，主要是因为构建时间长、内存使用量大或外部存储需求高。论文作者重新审视了一种简单的算法，并证明了它在构建时间和内存使用方面与当前最先进的技术相比具有竞争力。
作者提供了名为BBhash的并行C++实现。这个工具可以在不到7分钟内（使用8个线程和5GB内存）为10^10个元素构建一个最小完美哈希函数，而生成的函数每个元素仅占用3.7位。据作者所知，这还是首个成功处理10^12个元素输入的实现。源代码可以在论文提供的链接中获取。
最小完美哈希函数的关键点在于：
1. **空间效率**：这种哈希函数能够确保没有哈希冲突，同时尽可能地减少存储空间的使用。在本研究中，每个元素平均只用了3.7位，极大地优化了内存利用率。
2. **快速构建**：传统方法在处理大规模数据集时构建时间较长，而BBhash通过并行化处理显著提高了构建速度，使得处理亿级元素成为可能。
3. **可扩展性**：BBhash设计考虑到了处理大规模数据的能力，能够在多线程环境下运行，适应大数据环境的需求。
4. **并行化**：并行C++实现是解决大规模问题的关键，通过多线程并行计算，有效地分摊了计算负载，减少了处理时间。
5. **实用性**：BBhash不仅在理论上有优秀表现，还经过了实际测试，证明了其在处理海量数据时的稳定性和效率。
6. **应用场景**：最小完美哈希函数广泛应用于数据库索引、缓存系统、文本分析以及任何需要高效存储和检索静态集合元素的场景。
这篇论文对理解和改进大规模数据集上的哈希算法有着重要的贡献，BBhash的实现为处理海量键值对提供了一个高效且实用的解决方案。
XX:4 Fast and scalable minimal perfect hashing for massive key sets
F
d
have the same value
i
given by hash function
h
d
. Finally, if
C
d
[
i
] = 1, then
A
d
[
i
] = 0.
Formally:
C
d
[i] = 1 ⇒ A
d
[i] = 0;
(h
d
[x] = i and A
d
[i] = 0 and C
d
[i] = 0) ⇒ A
d
[i] = 1 (and C
d
[i] = 0) ;
(h
d
[x] = i and A
d
[i] = 1 and C
d
[i] = 0) ⇒ A
d
[i] = 0 and C
d
[i] = 1.
2.2.2 Queries
A query of a key
x
is performed by finding the smallest
d
such that
A
d
[
h
d
(
x
)] = 1. The (non
minimal) hash value of x is then (
P
i<d
|F
i
|) + h
d
(x).
2.2.3 Minimality
To ensure that the image range of the function is [1
, |F
0
|
], we compute the cumulative rank
of each ’1’ in the bit arrays
A
i
. Suppose, that
d
is the smallest value such that
A
d
[
h
d
(
x
)] = 1.
The minimal perfect hash value is given by
P
i<d
(
weight
(
A
i
) +
rank
(
A
d
[
h
d
(
x
)]), where
weight
(
A
i
) is the number of bits set to ’1’ in the
A
i
array, and
rank
(
A
d
[
y
]) is the number of
bits set to 1 in
A
d
within the interval [0
, y
], thus
rank
(
A
d
[
y
]) =
P
j<y
A
d
[j]
. This is a classic
method also used in other MPHFs [3].
2.2.4 Faster query and construction times (parameter γ)
The running time of the construction depends on the number of collisions on the
A
d
arrays,
at each level
d
. One way to reduce the number of collisions, hence to place more keys at each
level, is to use bit arrays (
A
d
and
C
d
) larger than
|F
d
|
. We introduce a parameter
γ ∈ R
,
γ ≥
1, such that
|C
d
|
=
|A
d
|
=
γ|F
d
|
. With
γ
= 1, the size of
A
is minimal. With
γ ≥
2,
the number of collisions is significantly decreased and thus construction and query times are
reduced, at the cost of a larger
MPHF
structure size. The influence of
γ
is discussed in more
details in the following analyses and results.
2.3 Analysis
Proofs of the following observations and lemma are given in the Appendix.
2.3.1 Size of the MPHF
The expected size of the structure can be determined using a simple argument, previously
made in [
6
]. When
γ
= 1, the expected number of keys which do not collide at level
d
is
|A
d
|e
−1
, thus
|A
d
|
=
|A
d−1
|
(1
− e
−1
) =
|A
0
|
(1
− e
−1
)
d
. In total, the expected number of
bits required by the hashing scheme is
P
d≥0
|A
d
|
=
N
P
d≥0
(1
− e
−1
)
d
=
eN
, with
N
being
the total number of input keys (
N
=
|F
0
|
). Note that consequently the image of the hash
function is also in [1
, eN
], before minimization using the rank technique. When
γ ≥
1, the
expected proportion of keys without collisions each level
d
is
|A
d
|e
−
1
γ
. Since each
A
d
no
longer uses one bit per key but
γ
bits per key, the expected total number of bits required by
the MPHF is γe
1
γ
N.
2.3.2 Space usage during construction
We analyze the disk space during construction. Recall that during construction of level
d
, a
bit array
C
d
of size
|A
d
|
is used to record collisions. Note that the
C
d
array is only needed
剩余15页未读，继续阅读
2019-12-31 上传
2020-06-17 上传
2023-03-28 上传
2023-04-06 上传
2023-04-01 上传
2023-05-19 上传
2023-05-23 上传
2023-04-01 上传
2023-03-29 上传
2023-05-15 上传
weixin_38605538
- 粉丝: 4
- 资源: 991
我的内容管理
展开
最新资源
- 新型智能电加热器：触摸感应与自动温控技术
- 社区物流信息管理系统的毕业设计实现
- VB门诊管理系统设计与实现(附论文与源代码)
- 剪叉式高空作业平台稳定性研究与创新设计
- DAMA CDGA考试必备：真题模拟及章节重点解析
- TaskExplorer：全新升级的系统监控与任务管理工具
- 新型碎纸机进纸间隙调整技术解析
- 有腿移动机器人动作教学与技术存储介质的研究
- 基于遗传算法优化的RBF神经网络分析工具
- Visual Basic入门教程完整版PDF下载
- 海洋岸滩保洁与垃圾清运服务招标文件公示
- 触摸屏测量仪器与粘度测定方法
- PSO多目标优化问题求解代码详解
- 有机硅组合物及差异剥离纸或膜技术分析
- Win10快速关机技巧：去除关机阻止功能
- 创新打印机设计：速释打印头与压纸辊安装拆卸便捷性
