But could we create a hash table that would be truly constant-time? No. As the size of your data structure grows, it requires progressively slower memory.
At a large enough size to be interesting, everything is dominated by IO and because IO is slow, at any interesting size performance is a matter of tailoring the implementation to the details of the data {0}.
Engineering is hard work, not naive math.
[0] Data might be arbitrary but it is never random. Not being random is what makes it data.
At a large enough size to be interesting, everything is dominated by IO and because IO is slow, at any interesting size performance is a matter of tailoring the implementation to the details of the data {0}.
Engineering is hard work, not naive math.
[0] Data might be arbitrary but it is never random. Not being random is what makes it data.