Thus, for each pair (q, r) ∈ [p]
2
, there is at most on e pair (a, b) ∈ [p]
2
satisfying (3) and (4). On
the other hand, (3) and (4) define a u n ique pair (q, r) ∈ [p]
2
for each pair (a, b) ∈ [p]
2
. We have p
2
pairs of each kind, so th e correspondence must be 1-1.
Since x 6= y, by Fact 2.1,
r = q ⇐⇒ a = 0. (7)
Thus, when we pick (a, b) ∈ [p]
+
× [p], we get r 6= q.
Returning to the proof of (2), we get a collision h
a,b
(x) = h
a,b
(y) if and only if q mod m =
r mod m. Let us fix q and set i = q mod m. There are at most ⌈p/m⌉ values r ∈ [p] wit h
r mod m = i and one of them is r = q. Therefore, the nu mber of r ∈ [p] \ {q} with r mod m =
i = q mod m is at most ⌈p/m⌉ − 1 ≤ (p + m − 1)/m − 1 = (p − 1)/m. However, there are
values of i
′
∈ [m] wit h only ⌊p/m⌋ values of q
′
∈ [p] with q
′
mod m = i
′
, and then the num ber
of r
′
∈ [p] \ {q
′
} with r
′
mod m = i
′
= q
′
mod m is ⌊p/m⌋ − 1 < ⌈p/m⌉ − 1. Summing over
all p values of q ∈ [p], we get that the number of r ∈ [p] \ {q} with r mod m = i = q mod m is
strictly l ess than p(⌈p/m⌉−1) ≤ p(p −1)/m. Then our 1-1 correspondence imp lies that there are
strictly less than p(p − 1)/m collision pairs (a, b) ∈ [p]
+
× [p]. Since each of the p(p − 1) pairs
from [p]
+
×[p] are equally likely, we concl u de that the collision probabil ity is st rictly below 1/m,
as claimed in (2).
Exercise 2.6 Suppose we for o ur hash functio n also consider a = 0, that is, for random (a, b) ∈
[p]
2
, we define the hash function h
a,b
: [p] → [m] by
h
a,b
(x) = ((ax + b) mod p ) mod m.
(a) Show that this function may n ot be universal.
(b) Prove t hat it is always 2-approximat el y universal, that is, for any distinct x, y ∈ [p],
Pr
(a,b)∈[p]
2
[h
a,b
(x) = h
a,b
(y)] < 2/m.
2.2.1 Implementation for 64-bit keys
Let us now consider the implementation of our hashing scheme
h(x) = ((ax + b) mod p) mod m
for the ty pical case of 64-bit keys in a s tandard imperative programming language such as C. Let’s
say the hash values are 20 bits, s o we have u = 2
64
and m = 2
20
.
Since p > u = 2
64
, we generally need to reserve more than 64 bits for a ∈ [p]
+
, so the product
ax has m ore than 128 bits. To compute ax, we now have the issue that multi plication of w-bit
numbers automatically discards overflow, returning only the w least significant bits of the produ ct .
However, we can get t he produ ct of 32-bit numbers, representi n g them as 64-bit numb ers, and
getting the full 64-bit result . We need at least 6 such 64-bit multiplications to compute ax.
Next issue is, how do we compute ax mod p? For 64-bit numbers we have a general mod-
operation, though it is rather slow, and here we have more than 128 bits.
5
剩余21页未读，继续阅读
weixin_38634323
- 粉丝: 7
- 资源: 899
我的内容管理
展开
最新资源
- OptiX传输试题与SDH基础知识
- C++Builder函数详解与应用
- Linux shell (bash) 文件与字符串比较运算符详解
- Adam Gawne-Cain解读英文版WKT格式与常见投影标准
- dos命令详解：基础操作与网络测试必备
- Windows 蓝屏代码解析与处理指南
- PSoC CY8C24533在电动自行车控制器设计中的应用
- PHP整合FCKeditor网页编辑器教程
- Java Swing计算器源码示例：初学者入门教程
- Eclipse平台上的可视化开发：使用VEP与SWT
- 软件工程CASE工具实践指南
- AIX LVM详解：网络存储架构与管理
- 递归算法解析：文件系统、XML与树图
- 使用Struts2与MySQL构建Web登录验证教程
- PHP5 CLI模式：用PHP编写Shell脚本教程
- MyBatis与Spring完美整合：1.0.0-RC3详解
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
