Timeline for Hash table using open-addressing with linear probing
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Jul 10, 2014 at 9:31 | comment | added | Thomas Ahle | You need a hash, at least as strong as tabulation hashing, if you want to use open addressing. This problem has been studied extensively, and not understanding this has let many people to dislike open addressing. | |
| Dec 15, 2012 at 12:52 | vote | accept | FUZxxl | ||
| Nov 25, 2012 at 21:08 | comment | added | Gareth Rees | Don't try to invent your own: use a standard hash function. If you need to be robust against the collision attack (and if the space overhead is acceptable) then tabulation hashing is fine (but you have to fix your implementation, as I pointed out in my comment above; also you only need one set of pseudo-random numbers, not one per hash table). If you don't care about the collision attack, try MurmurHash — it operates on 32-byte chunks so it's ideal for your case. | |
| Nov 23, 2012 at 23:16 | comment | added | FUZxxl | That makes sense. I am sorry for not providing enough information to really answer the question. Do you have a better idea for a hash function? I did also think about using a few iterations of the xorshift random number generator as it yields good distribution without any extra memory needed. Also, one iteration can be calculated in about 6 instructions. | |
| Nov 23, 2012 at 22:54 | comment | added | Gareth Rees | It looks to me as though you were trying to do tabulation hashing, but you missed these bits in bold: "The initialization phase of the algorithm creates a two-dimensional array T of dimensions 2^r by t". | |
| Nov 23, 2012 at 20:44 | comment | added | Gareth Rees | Aha! That's exactly the kind of useful information that explains why you've made some of your design decisions. You might want to copy it into a comment at the head of the source code. | |
| Nov 23, 2012 at 17:51 | comment | added | FUZxxl | Thank you for the commentary. I am going to go through all errors and fix them, especially the parts where my code is wrong. The hash table is going to be used in a data-compression program where an upper bound on the number of entries is known beforehand. I am planning to make the hashtable twice the size I need. The hash-function really is problematic, the function I use here was suggested somewhere on Wikipedia. The index to the hashtable is a set of two 32-bit symbols and the value is a pointer to such a set. Thank you really much for this deep review! | |
| Nov 23, 2012 at 15:48 | history | edited | Gareth Rees | CC BY-SA 3.0 |
note about pointless 32-bit dependency
|
| Nov 23, 2012 at 15:11 | history | edited | Gareth Rees | CC BY-SA 3.0 |
ht_get is also buggy
|
| Nov 23, 2012 at 14:24 | history | answered | Gareth Rees | CC BY-SA 3.0 |