4 ms·
> Hashtables can never guarantee constant time operations. A bit mask is a form of hash table and is guaranteed O(1) lookup for O(lg(Universe)) space. When yo
by inlined 7y ago
> Hashtables can never guarantee constant time operations.
A bit mask is a form of hash table and is guaranteed O(1) lookup for O(lg(Universe)) space.
When you have fixed universes, all kinds of options open up. I personally love vEB Trees, which can do set operations in O(lg(lg(U)))
- dahfizz 7y agoYes, in cases where direct addressing is possible you get guaranteed constant time. That's really more of an array than a hashtable IMO.