h*********3
发帖数: 111 | 1 我看了看书，说是每来个key,随即的选一个hash function 来计算hash的位置，是这
样吗？
如果是这样，那么插入时用了一个function f1, 读出时用了另外一个funciton f2,
怎么可能找到需要找的item呢？
| g*********s
发帖数: 1782 | 2 good question...
【在 h*********3 的大作中提到】
: 我看了看书，说是每来个key,随即的选一个hash function 来计算hash的位置，是这
: 样吗？
: 如果是这样，那么插入时用了一个function f1, 读出时用了另外一个funciton f2,
: 怎么可能找到需要找的item呢？
:
| c**y
发帖数: 172 | 3 I also had the same question before. After carefully studying the related
documents, I found my previous understanding is not correct. The universal
hashing is used in the following way.
Assume that we are given a bunch of keys to process. At the very beginning,
we randomly choose a hash function from a family of hash functions. Then
during execution, we apply this hash function to all the keys. A key
observation here is that the hash function doesn't change from key to key.
Will does universal hashing suffer from the poor performance issue? The
answer is "No". Below is the argument.
这里他们假设哈希函数的选择是独立于给定的keys。另外一方面，哈希函数family是有
一个条件的，就是对任意一个哈希函数（在这个family里面），对任何两个key的
collision概率是小于一个阈值。
之前那个poor performance issue一般是假设已知给定的哈希函数，人为构造一组key
，使得这个哈希函数的performance不好。在universal hash的情况下，是随机选定一
个哈希函数。
如果说用户有能力先知道选定的哈希函数并且再生成key，那么我人为universal hash
也有这个poor performance issue。
这是我的理解，欢迎讨论！！！！
【在 h*********3 的大作中提到】
: 我看了看书，说是每来个key,随即的选一个hash function 来计算hash的位置，是这
: 样吗？
: 如果是这样，那么插入时用了一个function f1, 读出时用了另外一个funciton f2,
: 怎么可能找到需要找的item呢？
:
| b******n
发帖数: 4509 | 4 universal hashing guarantees the collision is smaller than 1/m,
but you need a mechanism to make sure the same key maps to the same slot
,
key
hash
是这
f2,
【在 c**y 的大作中提到】
: I also had the same question before. After carefully studying the related
: documents, I found my previous understanding is not correct. The universal
: hashing is used in the following way.
: Assume that we are given a bunch of keys to process. At the very beginning,
: we randomly choose a hash function from a family of hash functions. Then
: during execution, we apply this hash function to all the keys. A key
: observation here is that the hash function doesn't change from key to key.
: Will does universal hashing suffer from the poor performance issue? The
: answer is "No". Below is the argument.
: 这里他们假设哈希函数的选择是独立于给定的keys。另外一方面，哈希函数family是有
| c**y
发帖数: 172 | 5 Can you provide detailed info about how to implement the mechanism?
【在 b******n 的大作中提到】
: universal hashing guarantees the collision is smaller than 1/m,
: but you need a mechanism to make sure the same key maps to the same slot
:
: ,
: key
: hash
: 是这
: f2,
|
|
