a*****k
发帖数: 704 | 1 如果想自己写个hashtable， 在有collision的情况下是不是很难处理？
假设没有collision是不是比较容易？ |
c*********u
发帖数: 361 | 2 use linked list to handle collision.
【在 a*****k 的大作中提到】
: 如果想自己写个hashtable， 在有collision的情况下是不是很难处理？
: 假设没有collision是不是比较容易？
|
a*****k
发帖数: 704 | 3 buckets of linked lists?
how does that work? any reference? Thanks
【在 c*********u 的大作中提到】
: use linked list to handle collision.
|
c*********u
发帖数: 361 | 4 see the Hash Table section in "Introduction to Algorithms"
【在 a*****k 的大作中提到】
: buckets of linked lists?
: how does that work? any reference? Thanks
|
w****u
发帖数: 3147 | |
a*****k
发帖数: 704 | 6 So I can use a vector of linkedlist?
whenever there is a new hash value, I add a linkedlist to the vector.
Would that work? any other things needs to pay attention?
【在 c*********u 的大作中提到】
: see the Hash Table section in "Introduction to Algorithms"
|
s**9
发帖数: 207 | 7 用vector > 就好了。
【在 a*****k 的大作中提到】
: 如果想自己写个hashtable， 在有collision的情况下是不是很难处理？
: 假设没有collision是不是比较容易？
|
a*****k
发帖数: 704 | 8 How to scale this up or down in this case?
Say my hash function calculate the hash code by dividing the size of the
vector,
and when number of the items accumulate/decrease to some critical value,
what should I do? I can put some slots in the vector, but then do I have to
go through the whole collection, recalculate their hash values, and put
them in the right places?
【在 s**9 的大作中提到】
: 用vector > 就好了。
|
w*****1
发帖数: 245 | 9 一个vector 不够吧，hashtable.put(key, value);
那key存在哪啊， 是不是要有两个vector, 一个存key, 一个value |
b*******y
发帖数: 239 | 10 You can also use Linear Probe, when collision happens, take the next
available slot, if the hash table is not that huge and complex. |
a*****k
发帖数: 704 | 11 in general, if I want to scale up the hash table, I have to recalculate hash
values of previous elemetns, and put them in the right places, right?
to
【在 a*****k 的大作中提到】
: How to scale this up or down in this case?
: Say my hash function calculate the hash code by dividing the size of the
: vector,
: and when number of the items accumulate/decrease to some critical value,
: what should I do? I can put some slots in the vector, but then do I have to
: go through the whole collection, recalculate their hash values, and put
: them in the right places?
|
