3 ms·
If you assume the usual primitives (memory, arithmetic) are O(1), can't you still get an amoratized, expected performance of hashtables. Given O(1) arithmatic,
by gizmo686 11y ago
If you assume the usual primitives (memory, arithmetic) are O(1), can't you still get an amoratized, expected performance of hashtables.
Given O(1) arithmatic, you should be able to use an O(1) hash function. At that point, you only have to deal with realocation as your tables grows without bound. You can solve that problem by using the 2n allocation method that gives us O(1) amortized appending to vectors.
Of course, you still need to make messy assumptions about randomness.
- SilasX 11y agoAny bounded size hash function has a bounded size output, which means a bounded number of buckets (number of possible outputs). That means that as the hash table gets arbitrarily large, you have to keep stacking new elements in each bucket. As the size goes to infinity, each bucket has a linear number of elements which have to be accessed in linear time.
- gizmo686 11y agoWhy do we need to use a bounded size hash function?
- SilasX 11y agoYou don't: that's the other alternative. But if you allow the hash table to resize as you increase the hash function (that is, adapt the function to one that has a larger output), then that's still not constant with respect to the table size. Computing a larger output requires logarithmically more operations to compute the hash, assuming you use one with the same well-mixedness properties. A hash function with 5 bits of output needs more operations than one with 2 bits of output.