定义一个从有限集合U到有限集合B上的散列表簇H为全域的，如果

[问答题]

定义一个从有限集合U到有限集合B上的散列表簇H为 $\epsilon$ 全域的，如果对U中所有的不同元素对k和l，都有

$Pr{h(k)=h(l)}\leq \epsilon$

其中概率是相对从函数簇H中随机抽取的散列函数h而言的。试证明：一个 $\epsilon$ 全域的散列函数簇必定满足：

$\epsilon\geq \frac{1}{\left| B \right|}-\frac{1}{\left| U \right|}$

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小

难度：

0条回答 0收藏 285浏览

扫一扫，把题目装进口袋