为什么要成为美国公民？大家都说说。。。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Immigration - 落地生根

为什么要成为美国公民？大家都说说。。。

为什么要成为美国公民？大家都说说。。。# Immigration - 落地生根

B*72012-04-04 07:04

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?
先谢谢啦～

c*m2012-04-04 07:04

2 楼

我自己先来吧，可能说的不好：
1. 美国社会所持有的平等概念是中国在未来50年都还不会有的。
2. 大部分中国人不信教，社会论理道德没有平判的标准。
本人不才，只是想抛砖引玉。

d*x2012-04-04 07:04

3 楼

为啥要每个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?
: 先谢谢啦～

Y*a2012-04-04 07:04

4 楼

据说护照好用，可以去政府部门

B*72012-04-04 07:04

5 楼

这也是我比较困惑的地方。如果不换hash table, 换hashing function的意义在哪里呢
？因为hashing function最终要map到hash table去找地址，如果不换hash table, n个
key占一个slot的情况永远都不会变啊，如果有的话。

【在 d**********x 的大作中提到】

: 为啥要每个function村一个table。。。
: 它只是每次换个不同的hash function算吧。。

c*n2012-04-04 07:04

6 楼

除了回国需要中国大使馆签证以外，成为美国公民也没有啥弱势啊？

d*x2012-04-04 07:04

7 楼

减少collision啊。
只用一个hash function的话，如果数据有天然的bias或者人造的bias，很容易导致
collision的

【在 B*****7 的大作中提到】

: 这也是我比较困惑的地方。如果不换hash table, 换hashing function的意义在哪里呢
: ？因为hashing function最终要map到hash table去找地址，如果不换hash table, n个
: key占一个slot的情况永远都不会变啊，如果有的话。

T*u2012-04-04 07:04

8 楼

美国这么好的自然资源，不来占一份亏啊

B*72012-04-04 07:04

9 楼

这个我理解，但我不理解的是如何用多个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的

K*N2012-04-04 07:04

10 楼

从来没有想过变成美国公民，不过现在绿卡还木有呢，嘿嘿。

d*s2012-04-04 07:04

11 楼

universal hashing，按我的理解，是在每次create instance的时候用随机的hash
function, 一旦instantiated之后就不变了，也就是说你的table只要存在就用同样的
hash function访问，但你想攻击我的系统，我只要做一个新的table出来，然后把原来
的数据全部copy过来就行了。这个cost amortized之后就忽略不计了

z*y2012-04-04 07:04

12 楼

除了回国需要中国大使馆签证以外，成为美国公民也没有啥弱势啊？
碰到恐怖分子，拿美国护照被tutu的可能性大增

B*72012-04-04 07:04

13 楼

如果以数据库为例，也就是说，系统如果受恶意request攻击就换个hashing function
，然后以新的hashing function重新生成index？

【在 d*s 的大作中提到】

: universal hashing，按我的理解，是在每次create instance的时候用随机的hash
: function, 一旦instantiated之后就不变了，也就是说你的table只要存在就用同样的
: hash function访问，但你想攻击我的系统，我只要做一个新的table出来，然后把原来
: 的数据全部copy过来就行了。这个cost amortized之后就忽略不计了

c*r2012-04-04 07:04

14 楼

大圣神教算教么？

【在 c***m 的大作中提到】

: 我自己先来吧，可能说的不好：
: 1. 美国社会所持有的平等概念是中国在未来50年都还不会有的。
: 2. 大部分中国人不信教，社会论理道德没有平判的标准。
: 本人不才，只是想抛砖引玉。

d*s2012-04-04 07:04

15 楼

恶意攻击要有效的话需要知道你用的具体参数，如果没有universal hashing，就靠实
现时候对参数的保密，显然不靠谱。有了之后就算公开源代码一般也没办法进行攻击，
因为根本不知道具象化之后的database用的p, q, m是多少，我认为需要换函数的情况
是十分罕见的

function

【在 B*****7 的大作中提到】

: 如果以数据库为例，也就是说，系统如果受恶意request攻击就换个hashing function
: ，然后以新的hashing function重新生成index？

d*r2012-04-04 07:04

16 楼

1.回国不会被城管打
2.免签去欧洲旅游

B*72012-04-04 07:04

17 楼

Make sense. 谢谢～
哪位数据库大牛给confirm一下？

【在 d*s 的大作中提到】

: 恶意攻击要有效的话需要知道你用的具体参数，如果没有universal hashing，就靠实
: 现时候对参数的保密，显然不靠谱。有了之后就算公开源代码一般也没办法进行攻击，
: 因为根本不知道具象化之后的database用的p, q, m是多少，我认为需要换函数的情况
: 是十分罕见的
:
: function