b******e 发帖数: 120 | 1 我说REHASH, 然后他问我第一个HASH后怎么知道在那个地址的是你要的值还是另一个值
,我说直接比较啊,不是就REHASH,那个阿三说什么HASH只能比较对KEY 进行操作,没
办法比较VALUE什么的,把我批得体无完肤,我还真没弄懂了 如果只能对HASH后的
VALUE 找值,怎么判断第一轮的是我想要的还是第二轮是我想要的 |
y*******g 发帖数: 6599 | 2 collision之后是append linkedlist
rehash 的过程可以理解为把现有的所有数据插到一个新的hash table.之后, 再新的
hash table中找。 |
y*******g 发帖数: 6599 | 3 阿三说只能比较hash不能比较value应该是扯淡了。会不会是交流有问题?
要加深对hash 的了解可以看看Java的源码,比如
http://www.docjar.com/html/api/java/util/HashMap.java.html |
b******e 发帖数: 120 | 4 他的意思是有两个值,他们用第一个HASH FUNCTION 都对应一个KEY,那么对后加入的
用REHASH 找到另一个KEY或者说地址存放,那么在SEARCH 第二个值的时候,都会开始
用第一个HASH FUNCTION, 那么你怎么判断第一个HASH FUNCTION 找到的那个KEY是第
一个值对应的还是第二个值对应的,我说要比较,他说没有办法比较,因为算出来的
KEY是一样的 |
y*******g 发帖数: 6599 | 5 嗯,的确没办法比较。
这属于collision, 解决的方法是在同一个bucket 里面用linked list,然后再
linkedlist里面逐一比较value
他大概再提示你 rehash不work吧
rehash是当hash 太满的时候,太多bucket 会有一个常常的linked list,那么大量的
操作就不是O(1) 而是O(k), k是linkedlist的长度
所以需要扩大hash array的size,然后重新插入value
【在 b******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 他的意思是有两个值,他们用第一个HASH FUNCTION 都对应一个KEY,那么对后加入的 : 用REHASH 找到另一个KEY或者说地址存放,那么在SEARCH 第二个值的时候,都会开始 : 用第一个HASH FUNCTION, 那么你怎么判断第一个HASH FUNCTION 找到的那个KEY是第 : 一个值对应的还是第二个值对应的,我说要比较,他说没有办法比较,因为算出来的 : KEY是一样的
|
j********x 发帖数: 2330 | 6 这都搞笑呢吧。。。
hash table,hash(key)是作为index,插入对应bucket;
query的时候,找到对应的bucket,然后查找对应的key。。。
rehash(应该叫double hashing)只是放到另一个bucket
query的时候先用第一个hash,找到bucket,找key;没有,第二个hash,第二个bucket
,找key,有,return,没有,拉倒。。。
什么跟什么,阿三是生物学毕业的码工吧。。。 |
k****n 发帖数: 369 | 7 到底是open addressing还是chaining?
如果是Open addressing, 就是定一个继续找下一个slot的策略就好了,线性的或者二
次的什么的
我还是没听懂什么第一个第二个值的
【在 b******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 他的意思是有两个值,他们用第一个HASH FUNCTION 都对应一个KEY,那么对后加入的 : 用REHASH 找到另一个KEY或者说地址存放,那么在SEARCH 第二个值的时候,都会开始 : 用第一个HASH FUNCTION, 那么你怎么判断第一个HASH FUNCTION 找到的那个KEY是第 : 一个值对应的还是第二个值对应的,我说要比较,他说没有办法比较,因为算出来的 : KEY是一样的
|
b******e 发帖数: 120 | 8 open addressing,他的意思是怎么判断你search 的时候这个slot 就是你想要的,以为
KEY HASH 后的值是一样的,我说找到数据比较,他说无法,我也说了这个要定一个
consistent 的找下一个slot的策略,他说这不是他想问的,他想知道的是怎么判断是
要找下一个SLOT 还是当前这个就是想要的结果
【在 k****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 到底是open addressing还是chaining? : 如果是Open addressing, 就是定一个继续找下一个slot的策略就好了,线性的或者二 : 次的什么的 : 我还是没听懂什么第一个第二个值的
|
b*****c 发帖数: 1103 | 9 请问hashtable里面存的不是(key,value)的pair吗?我不懂耶
假设H()是hash function,
H(key1)=H(key2)无所谓,因为能够比较key1和key2,是这样吗?
【在 b******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 他的意思是有两个值,他们用第一个HASH FUNCTION 都对应一个KEY,那么对后加入的 : 用REHASH 找到另一个KEY或者说地址存放,那么在SEARCH 第二个值的时候,都会开始 : 用第一个HASH FUNCTION, 那么你怎么判断第一个HASH FUNCTION 找到的那个KEY是第 : 一个值对应的还是第二个值对应的,我说要比较,他说没有办法比较,因为算出来的 : KEY是一样的
|
s**********e 发帖数: 326 | 10 楼主说的key实际上是index,感觉是不是沟通的问题啊,把key 和index混淆了 |