86 ms·

What kind of hash table is O(1)? Or did I forgot everything from university already? You cannot have a general O(1) hash Well maybe in best case/average case,

What kind of hash table is O(1)? Or did I forgot everything from university already? You cannot have a general O(1) hash Well maybe in best case/average case, when you design the hash space big enough. Ugh I really did forgot everything.

hailwren 5y ago
The trick with O and hash tables is to remember that they're amortized O(1). Imagine a bag with the cost of resizing sitting inside it. Then, spread the cost across all inserts. There are always more inserts than the cost of resizing, so you end up w/ amortized O(1).
vlovich123 5y ago
Not sure I understand your concern. Are you asking about worst case? All hash tables I believe are O(n) worst case because of the possibility of collisions (or the need to resize in the case of an insert). Most people talk about amortized performance though (ie when you are successful at reducing the likelihood of worst case to a rare event). Amortized time is obviously dangerous if you’re in a real-time system (eg games) where it’ll manifest as stuttering or latency spikes or potentially even worse if you’re having to respond to hardware events in a timely manner for proper operation.
- Dylan16807 5y ago
  It's possible to gradually resize a hash table to prevent spikes. For collisions, if you use a good hash then you can adjust your load factor and chaining strategy to make sure it's never a problem. Where 'never' is 'less likely than the computer spontaneously self-destructing'.
  - vlovich123 5y ago
    > It's possible to gradually resize a hash table to prevent spikes. Can you provide details? The only trick I know of is the same one as with arrays where you overallocate. That still doesn't get rid of spikes and the C++ STL and Wikipedia both list worst case time as O(size of hash table). It's also not enough to just have capacity - often times hash tables will abort finding a slot if gone far enough in favor of resizing & rehashing the table. > For collisions, if you use a good hash then you can adjust your load factor and chaining strategy to make sure it's never a problem. Where 'never' is 'less likely than the computer spontaneously self-destructing'. Yes, but the vast majority of implementations don't do a good job here. Howard's "Types Don't Know #"[1] paper is extremely well thought out and I have yet to see this adopted (except for Rust - Rust has a good track record of adopting good ideas like this and having the benefit of coming late to the game). I think it's safe to say that most hash tables don't have good worst case times (which when combined with resizing behavior of insertions, means you have super-linear worst case times on insertion). [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n398...
    - Dylan16807 5y ago
      > Can you provide details? The only trick I know of is the same one as with arrays where you overallocate. That still doesn't get rid of spikes and the C++ STL and Wikipedia both list worst case time as O(size of hash table). When you want to grow your hash table, go ahead and allocate a bigger but blank chunk of memory. (You can either design your memory allocation system to make this fast, or you can prerequest the memory when you're x% away from full.) Put your new item in the big chunk of memory. Every time you search for something, check both chunks. Every time the hash table has to allocate a new slot, move over four items from the small chunk of memory to the big chunk. Eventually the big chunk of memory will be 65% full and the small chunk will be empty, and then you deallocate the small chunk. And that'll work forever just fine. The ability to shrink is only slightly more complicated, exercise for the reader. > It's also not enough to just have capacity - often times hash tables will abort finding a slot if gone far enough in favor of resizing & rehashing the table. Either use methods that won't abort, or use a secure hash and tune the hash table so you can make a statistical guarantee that the chance of an emergency resize is a million times smaller than the chance of the computer spontaneously self-destructing. Edit: > C++ STL and Wikipedia It's no surprise the STL wouldn't so something as fussy as keeping two most-of-a-hash-tables behind the curtain. As for Wikipedia, it has a whole section talking about how you don't have to resize all-at-once. The O(n) at the top is an oversimplification.
      - vlovich123 5y ago
        That's a really neat idea. I don't think I've seen any containers that implement this idea. Wonder why.

hailwren 5y ago

The trick with O and hash tables is to remember that they're amortized O(1). Imagine a bag with the cost of resizing sitting inside it. Then, spread the cost across all inserts. There are always more inserts than the cost of resizing, so you end up w/ amortized O(1).

vlovich123 5y ago

Not sure I understand your concern. Are you asking about worst case? All hash tables I believe are O(n) worst case because of the possibility of collisions (or the need to resize in the case of an insert). Most people talk about amortized performance though (ie when you are successful at reducing the likelihood of worst case to a rare event). Amortized time is obviously dangerous if you’re in a real-time system (eg games) where it’ll manifest as stuttering or latency spikes or potentially even worse if you’re having to respond to hardware events in a timely manner for proper operation.

Dylan16807 5y ago
It's possible to gradually resize a hash table to prevent spikes. For collisions, if you use a good hash then you can adjust your load factor and chaining strategy to make sure it's never a problem. Where 'never' is 'less likely than the computer spontaneously self-destructing'.
- vlovich123 5y ago
  > It's possible to gradually resize a hash table to prevent spikes. Can you provide details? The only trick I know of is the same one as with arrays where you overallocate. That still doesn't get rid of spikes and the C++ STL and Wikipedia both list worst case time as O(size of hash table). It's also not enough to just have capacity - often times hash tables will abort finding a slot if gone far enough in favor of resizing & rehashing the table. > For collisions, if you use a good hash then you can adjust your load factor and chaining strategy to make sure it's never a problem. Where 'never' is 'less likely than the computer spontaneously self-destructing'. Yes, but the vast majority of implementations don't do a good job here. Howard's "Types Don't Know #"[1] paper is extremely well thought out and I have yet to see this adopted (except for Rust - Rust has a good track record of adopting good ideas like this and having the benefit of coming late to the game). I think it's safe to say that most hash tables don't have good worst case times (which when combined with resizing behavior of insertions, means you have super-linear worst case times on insertion). [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n398...
  - Dylan16807 5y ago
    > Can you provide details? The only trick I know of is the same one as with arrays where you overallocate. That still doesn't get rid of spikes and the C++ STL and Wikipedia both list worst case time as O(size of hash table). When you want to grow your hash table, go ahead and allocate a bigger but blank chunk of memory. (You can either design your memory allocation system to make this fast, or you can prerequest the memory when you're x% away from full.) Put your new item in the big chunk of memory. Every time you search for something, check both chunks. Every time the hash table has to allocate a new slot, move over four items from the small chunk of memory to the big chunk. Eventually the big chunk of memory will be 65% full and the small chunk will be empty, and then you deallocate the small chunk. And that'll work forever just fine. The ability to shrink is only slightly more complicated, exercise for the reader. > It's also not enough to just have capacity - often times hash tables will abort finding a slot if gone far enough in favor of resizing & rehashing the table. Either use methods that won't abort, or use a secure hash and tune the hash table so you can make a statistical guarantee that the chance of an emergency resize is a million times smaller than the chance of the computer spontaneously self-destructing. Edit: > C++ STL and Wikipedia It's no surprise the STL wouldn't so something as fussy as keeping two most-of-a-hash-tables behind the curtain. As for Wikipedia, it has a whole section talking about how you don't have to resize all-at-once. The O(n) at the top is an oversimplification.
    - vlovich123 5y ago
      That's a really neat idea. I don't think I've seen any containers that implement this idea. Wonder why.