B*****7
发帖数: 137 | 1 我最近在学clrs，觉得universal hashing这节挺dry的，看的比较困惑，想跟大家请教
一些问题。
在实际应用中，the size of the set of hashing functions大概有多大？几百？几千
？对每个hashing function，是不是都在内存中存一份hash table? If so, is it
fair to say that universal hashing is a trade off between memory and CPU
time?
另外，以数据库为例，如果库的数据更新了，比如插入或删除了一个纪录，那更新所有
的hash tables的时间复杂度是不是O(n), where n is the number of hash tables?
先谢谢啦～ |
d**********x
发帖数: 4083 | 2 为啥要每个function村一个table。。。
它只是每次换个不同的hash function算吧。。
【在 B*****7 的大作中提到】
: 我最近在学clrs，觉得universal hashing这节挺dry的，看的比较困惑，想跟大家请教
: 一些问题。
: 在实际应用中，the size of the set of hashing functions大概有多大？几百？几千
: ？对每个hashing function，是不是都在内存中存一份hash table? If so, is it
: fair to say that universal hashing is a trade off between memory and CPU
: time?
: 另外，以数据库为例，如果库的数据更新了，比如插入或删除了一个纪录，那更新所有
: 的hash tables的时间复杂度是不是O(n), where n is the number of hash tables?
: 先谢谢啦～
|
B*****7
发帖数: 137 | 3 这也是我比较困惑的地方。如果不换hash table, 换hashing function的意义在哪里呢
？因为hashing function最终要map到hash table去找地址，如果不换hash table, n个
key占一个slot的情况永远都不会变啊，如果有的话。
【在 d**********x 的大作中提到】
: 为啥要每个function村一个table。。。
: 它只是每次换个不同的hash function算吧。。
|
d**********x
发帖数: 4083 | 4 减少collision啊。
只用一个hash function的话，如果数据有天然的bias或者人造的bias，很容易导致
collision的
【在 B*****7 的大作中提到】
: 这也是我比较困惑的地方。如果不换hash table, 换hashing function的意义在哪里呢
: ？因为hashing function最终要map到hash table去找地址，如果不换hash table, n个
: key占一个slot的情况永远都不会变啊，如果有的话。
|
B*****7
发帖数: 137 | 5 这个我理解，但我不理解的是如何用多个hashing function却只用一个hash table。
举个例子吧。key1 and key2 are mapped to m1 by hashing function h1, and to m2
by hashing function h2. Apparently, the addresses of elements with key1 and
key2, respectively, are stored in slot m1 by h1. When the hashing function
is changed to h2, how do their addresses magically appear in slot m2 without
storing another hash table with their keys already mapped to m2?
困惑中～～
【在 d**********x 的大作中提到】
: 减少collision啊。
: 只用一个hash function的话，如果数据有天然的bias或者人造的bias，很容易导致
: collision的
|
d*s
发帖数: 699 | 6 universal hashing，按我的理解，是在每次create instance的时候用随机的hash
function, 一旦instantiated之后就不变了，也就是说你的table只要存在就用同样的
hash function访问，但你想攻击我的系统，我只要做一个新的table出来，然后把原来
的数据全部copy过来就行了。这个cost amortized之后就忽略不计了 |
B*****7
发帖数: 137 | 7 如果以数据库为例，也就是说，系统如果受恶意request攻击就换个hashing function
，然后以新的hashing function重新生成index？
【在 d*s 的大作中提到】
: universal hashing，按我的理解，是在每次create instance的时候用随机的hash
: function, 一旦instantiated之后就不变了，也就是说你的table只要存在就用同样的
: hash function访问，但你想攻击我的系统，我只要做一个新的table出来，然后把原来
: 的数据全部copy过来就行了。这个cost amortized之后就忽略不计了
|
d*s
发帖数: 699 | 8 恶意攻击要有效的话需要知道你用的具体参数，如果没有universal hashing，就靠实
现时候对参数的保密，显然不靠谱。有了之后就算公开源代码一般也没办法进行攻击，
因为根本不知道具象化之后的database用的p, q, m是多少，我认为需要换函数的情况
是十分罕见的
function
【在 B*****7 的大作中提到】
: 如果以数据库为例，也就是说，系统如果受恶意request攻击就换个hashing function
: ，然后以新的hashing function重新生成index？
|
B*****7
发帖数: 137 | 9 Make sense. 谢谢～
哪位数据库大牛给confirm一下？
【在 d*s 的大作中提到】
: 恶意攻击要有效的话需要知道你用的具体参数，如果没有universal hashing，就靠实
: 现时候对参数的保密，显然不靠谱。有了之后就算公开源代码一般也没办法进行攻击，
: 因为根本不知道具象化之后的database用的p, q, m是多少，我认为需要换函数的情况
: 是十分罕见的
:
: function
|
