Algorithms Lecture 12: Hash Tables [Fa’13]
One property of ideal random hash functions that seems intuitively useful is
uniformity
. A
family
H
of hash functions is uniform if choosing a hash function uniformly at random from
H
makes every hash value equally likely for every item in the universe:
Uniform: Pr
h∈H
h(x) = i
=
1
m
for all x and all i
We emphasize that this condition must hold for every item
x ∈ U
and every index
i
. Only the
hash function h is random.
In fact, despite its intuitive appeal, uniformity is not terribly important or useful by itself.
Consider the f amily
K
of constant hash f unctions defined as follows. For each integer
a
between
0
and
m −1
, let
const
a
denote the constant function
const
a
(x) = a
for all
x
, and let
K = {const
a
| 0 ≤ a ≤ m −1}
be the set of all such functions. It is easy to see that the set
K
is
both perfectly uniform and utterly useless!
A much more important goal is to minimi ze the number of collisions. A f amily of hash
functions is
universal
if, for any two items in the universe, the probability of collision is as small
as possible:
Universal: Pr
h∈H
h(x) = h( y)
=
1
m
for all x 6= y
(Trivially, if
x = y
, then
Pr[h(x) = h( y)] = 1
!) Again, we emphasize that this equation must hold
for every pair of distinct items; only the function
h
is random. The family of constant functions
is uniform but not universal; on the other hand, universal hash families are not necessarily
uniform.¹
Most elementary hashing analysis requires a weaker versions of universality. A family of hash
functions is near-universal if the probability of collision is close to ideal:
Near-universal: Pr
h∈H
h(x) = h( y)
≤
2
m
for all x 6= y
There’s nothing special about the number
2
in this definition; any other explicit constant will do.
On the other hand, some hashing analysis requires reasoning about larger sets of collisions.
For any integer
k
, we say that a family of hash functions is
strongly k -universal
or
k-uniform
if
for any sequence of
k
disjoint keys and any sequence of
k
hash values, the probability that each
key maps to the corresponding hash value is 1/m
k
:
k-uniform: Pr
k
^
j=1
h(x
j
) = i
j
=
1
m
k
for all distinct x
1
, . . . , x
k
and all i
1
, . . . , i
k
Ideal random hash functions are k-uniform for every positive integer k.
12.4 Chaining
One of the most common methods for resolving collisions in hash tables is called chaining. In a
chained hash table, each entry
T [i]
is not just a single item, but rather (a pointer to) a linked
list of all the items that hash to
T [i]
. Let
`(x)
denote the length of the list
T [h(x)]
. To see if
¹
Confusingly, universality is often called the
uniform hashing assumption
, even though it is not an assumption
that the hash function is uniform.
3
剩余14页未读，继续阅读
weixin_38739837
- 粉丝: 2
- 资源: 912
我的内容管理
展开
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测：静态代码分析与数据流方法
- 青苔数据CEO程永：技术生态与阿里云开放创新
- 制造业转型： HyperX引领企业上云策略
- 赵维五分享：航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛：AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器：设计与实现
- 猩便利工程师仲小玉：Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享：高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会：阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
