g*********s
发帖数: 1782 | 1 hartime123 once posted the doubt and it seems not answered yet.
we all know universal hash is a hash function family H that has the
similar hash property.
for the insert op, we randomly select h from H and apply h to the input
key k and put it to h(k)
but what if now we need to query if k is in the hash table? we don't know
which hash function h is used to insert k. iterating H one by one
looks too naive. |
r**d
发帖数: 316 | 2 在java里hash函数不是随机选择的，而是由class定死的，所以给定key，所映射的
index是一定的。
如果hash函数发生碰撞就需要遍历table[index]链表里的所有元素了。
【在 g*********s 的大作中提到】
: hartime123 once posted the doubt and it seems not answered yet.
: we all know universal hash is a hash function family H that has the
: similar hash property.
: for the insert op, we randomly select h from H and apply h to the input
: key k and put it to h(k)
: but what if now we need to query if k is in the hash table? we don't know
: which hash function h is used to insert k. iterating H one by one
: looks too naive.
|
g*********s
发帖数: 1782 | 3 but here the focus is universal hashing ah.
【在 r**d 的大作中提到】
: 在java里hash函数不是随机选择的，而是由class定死的，所以给定key，所映射的
: index是一定的。
: 如果hash函数发生碰撞就需要遍历table[index]链表里的所有元素了。
|
l*********9
发帖数: 12 | 4 iterating Hash functions is acceptable, the searching time is still O(1). |
g*****k
发帖数: 623 | 5 我理解的是每一个hash table建立之后hash function h就已经绑定了。
只是建立hash table之前你随机选择H中的一个h而已。
不是每次都要随机选择h来compute hash key
【在 g*********s 的大作中提到】
: hartime123 once posted the doubt and it seems not answered yet.
: we all know universal hash is a hash function family H that has the
: similar hash property.
: for the insert op, we randomly select h from H and apply h to the input
: key k and put it to h(k)
: but what if now we need to query if k is in the hash table? we don't know
: which hash function h is used to insert k. iterating H one by one
: looks too naive.
|
j**w
发帖数: 382 | 6
Insert: When save h(k), save the original k together.
Query: Compute h_i(y) for every hash function h_i in H, then check all
content at h_i(y)
【在 g*********s 的大作中提到】
: hartime123 once posted the doubt and it seems not answered yet.
: we all know universal hash is a hash function family H that has the
: similar hash property.
: for the insert op, we randomly select h from H and apply h to the input
: key k and put it to h(k)
: but what if now we need to query if k is in the hash table? we don't know
: which hash function h is used to insert k. iterating H one by one
: looks too naive.
|
s********i
发帖数: 17328 | 7 这个回答不及格啊。
【在 g*****k 的大作中提到】
: 我理解的是每一个hash table建立之后hash function h就已经绑定了。
: 只是建立hash table之前你随机选择H中的一个h而已。
: 不是每次都要随机选择h来compute hash key
|
s********i
发帖数: 17328 | 8 这个题出得不make sense啊，之所以用universal hashing就是遍历hash function的时
间是固定的，从而减少可能search collision的时间。
【在 l*********9 的大作中提到】
: iterating Hash functions is acceptable, the searching time is still O(1).
|
g*****k
发帖数: 623 | 9 are you sure? how about reading the text again?
这个回答不及格啊。
【在 s********i 的大作中提到】
: 这个回答不及格啊。
|
c**y
发帖数: 172 | 10 Your understanding is correct. I had the same question before and checked
with a Professor in our CS department, who teaches Algorithms. What he said
is the same as you did.
Hope this is helpful
【在 g*****k 的大作中提到】
: 我理解的是每一个hash table建立之后hash function h就已经绑定了。
: 只是建立hash table之前你随机选择H中的一个h而已。
: 不是每次都要随机选择h来compute hash key
|
s********i
发帖数: 17328 | 11 楼上几位，我错了，没学好。楼主的问题误导了我，也就是说universal hashing不存
在iterate hash function的问题。 |
