全域散列概念理解(try)

其中重合是指&＃xff0c;对任意 x !&＃61; y&＃xff0c;使散列函数集合 H 中 h(x) &＃61;&＃61; h(y) 的散列函数个数。
随机选择散列函数后&＃xff0c;对于恶意的精心设计来引起尽可能多的冲突的破坏行为的输入k1!&＃61;k2&＃xff09;&＃xff0c;能够被这个 k1,k2 命中的散列函数个数就会 ≤t&＃61; |H|/m&＃xff0c;
(在这里需要注意一下,函数越多,那么被命中函数就可能f风险越多,如果对于|H|个(所有的)散列函数,
对于输入同一对k1,k2输给所有散列函数,能够命中次数不超过t&＃61;|H|/m;
则若指定其中的一个散列函数,那么k1,k2输入能够使得冲突的发生的概率满足:不超过t/|H|&＃61;1/m的命中率
即命中概率 ≤ |H|/m / |H| &＃61; 1/m。
也就是说&＃xff0c;对于精心构造的(恶意要引起冲突)的输入&＃xff0c;冲突率仍然能够控制在 1/m内。

H:全域散列函数组
一组有限的散列函数
它将给定的关键字全域U&＃xff0c;映射到{0,1,…,m-1}(m为散列表的长度)中
如果每一对关键字k,l(k!&＃61;l),满足h(k)&＃61;h(l)的散列函数h(h属于H)的个数至多位|H|/m