Timeline for Improving HashMap in C++
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2011 at 21:12 | comment | added | bsoundra | I like the swapping part | |
| Mar 3, 2011 at 10:33 | comment | added | Mike Seymour | A vector will most likely be faster, as it will involve fewer memory allocations when adding and removing elements, and probably better cache behaviour when iterating through it. Since the order doesn't matter, you can add elements at the end, and remove one by swapping it with the last element, then removing it from the end. These are all constant-time operations, so a list wouldn't improve on that. | |
| Mar 2, 2011 at 18:52 | vote | accept | bsoundra | ||
| Mar 2, 2011 at 18:51 | comment | added | bsoundra | One more question though, instead of using the second dimension as a vector, would it help in performance if I used a List ??? I was thinking about the (1) for few days and this morning I got it and I logged in to say that and I see your comment :) . Now I got the (2) point . Thank you. | |
| Feb 28, 2011 at 14:04 | comment | added | Mike Seymour | 2. You can (and should) overload the hash function for most, if not all, built-in and standard types. However, the user might define a different type (which you have no knowledge of) and want to use it as a hash key. By placing the hash function in the namespace outside your hash table, anyone can create overloads for their own types, and use them as keys in your template. By leaving it as a member, they are restricted to the types that you provide overloads for. | |
| Feb 28, 2011 at 14:01 | comment | added | Mike Seymour |
1. You calculate the table index as hash(key)%hashsize. You are still doing the modulo calculation, but not in the hash function itself; that means the hash function is independent of the hash table.
|
|
| Feb 25, 2011 at 21:45 | comment | added | bsoundra | Thanks Mike. I have been thinking about the implementation details which you suggested. 1. If the implementation is going to be in vector<vector<node>>, where the first dimension will be my effective table and the second will act as the bucket. If this is the case, then how do I decide the place in the table i.e. the first dimension without doing 'h = h%hashsize;'. 2. Moving the hash function. I dont understand what you mean by "any user of the hash template can overload it ". I had initially thought of having overloaded hash function for all data type . Please clarify my doubts | |
| Feb 22, 2011 at 14:16 | history | edited | Mike Seymour | CC BY-SA 2.5 |
|
| Feb 22, 2011 at 11:47 | history | answered | Mike Seymour | CC BY-SA 2.5 |