4 ms·

I ran into the same thing when implementing a hash table sorting algorithm from a recent paper. Nowhere in the paper does it mention that table size MUST be a p

I ran into the same thing when implementing a hash table sorting algorithm from a recent paper. Nowhere in the paper does it mention that table size MUST be a power of two. The new table structure is supposedly more memory efficient than anything else out there. That's the whole point of it. So it's nice that they leave out "btw only works with size power of two". I got 2/3 of the way through an optimized implementation before I realized it wasn't any more efficient than the previous contender, in fact much less so, if you couldn't fit your set into exactly a power of two size. Not outright lying but creative ommission for sure

ur-whale 7y ago
I think it's ok to names names in this specific instance: you'll save other people a lot of pain.
- nullwasamistake 7y ago
  It's only been implemented ~3 times besides the paper reference and I do too much ranting on HN to risk connecting it to my professional image. Particularly critisicm of big tech companies I may want to work for someday. Sorry. It's very niche, I doubt many will run into it. Writing your own hash table is generally considered a bad idea :). I was just very bored and annoyed with memory limits. It will only affect implementors, which is less than 5 people in 4 years. Good example of implementor beware though, I'm sure it's a common issue
opportune 7y ago
Is it more efficient in terms of algorithmic complexity or just performance on real systems? I don't think it's creative omission if it's a complexity improvement but it's definitely worse if the performance gains were just empirical but relied on that one condition.
bjourne 7y ago
Backing arrays for fast hash tables are always powers of 2. That's how they are implemented in all mainstream languages. Details are often omitted in academia because of publishing constraints or because the authors thought they were obvious.
- rurban 7y ago
  Fast yes, but more insecure. Using prime sized tables will get all hash bits being used. With power of 2 you can get away with the mod, but it's easier to crack, and the grow factor is bigger than the ideal fibonacci sequence, or a prime sequence.
  - bjourne 7y ago
    As long as you have a decent hash function that distributes the bits properly it doesn't matter. IME, it makes no difference performance wise if you the golden ratio (1.61...) as the growth factor or 2.

ur-whale 7y ago

I think it's ok to names names in this specific instance: you'll save other people a lot of pain.

nullwasamistake 7y ago
It's only been implemented ~3 times besides the paper reference and I do too much ranting on HN to risk connecting it to my professional image. Particularly critisicm of big tech companies I may want to work for someday. Sorry. It's very niche, I doubt many will run into it. Writing your own hash table is generally considered a bad idea :). I was just very bored and annoyed with memory limits. It will only affect implementors, which is less than 5 people in 4 years. Good example of implementor beware though, I'm sure it's a common issue

opportune 7y ago

Is it more efficient in terms of algorithmic complexity or just performance on real systems? I don't think it's creative omission if it's a complexity improvement but it's definitely worse if the performance gains were just empirical but relied on that one condition.

bjourne 7y ago

Backing arrays for fast hash tables are always powers of 2. That's how they are implemented in all mainstream languages. Details are often omitted in academia because of publishing constraints or because the authors thought they were obvious.

rurban 7y ago
Fast yes, but more insecure. Using prime sized tables will get all hash bits being used. With power of 2 you can get away with the mod, but it's easier to crack, and the grow factor is bigger than the ideal fibonacci sequence, or a prime sequence.
- bjourne 7y ago
  As long as you have a decent hash function that distributes the bits properly it doesn't matter. IME, it makes no difference performance wise if you the golden ratio (1.61...) as the growth factor or 2.