Our analysis of the efficiency of hash table operations concluded that
runs in expected constant time, where the modifier "expected" is needed to
express the fact the performance is on average and depends on the hash function
satisfying certain properties.
We also concluded that
insert would usually run in expected constant time,
but that in the worst case it would require linear time because of needing
to rehash the entire table. That kind of defeats the goal of a hash table,
which is to offer constant-time performance, or at least as close to it
as we can get.
It turns out there is another way of looking at this analysis that allows us to
insert does have "amortized" expected constant time
performance—that is, for excusing the occasional worst-case linear
performance. Right away, we have to acknowledge this technique is just a change
in perspective. We're not going to change the underlying algorithms. The
insert algorithm will still have worst-case linear performance. That's a fact.
But the change in perspective we now understake is to recognize that if it's
very rare for
insert to require linear time, then maybe we can "spread out"
that cost over all the other calls to
insert. It's a creative accounting
Sushi vs. Ramen. Let's amuse ourselves with a real-world example for a moment. Suppose that you have $20 to spend on lunches for the week. You like to eat sushi, but you can't afford to have sushi every day. So instead you eat as follows:
- Monday: $1 ramen
- Tuesday: $1 ramen
- Wednesday: $1 ramen
- Thursday: $1 ramen
- Friday: $16 sushi
Most of the time, your lunch was cheap. On a rare occasion, it was expensive. So you could look at it in one of two ways:
- My worst-case lunch cost was $16.
- My average lunch cost was $4.
Both are true statements, but maybe the latter is more helpful in understanding your spending habits.
Back to Hash Tables.
It's the same with hash tables. Even though
insert is occasionally expensive,
it's so rarely expensive that the average cost of an operation is actually
constant time! But, we need to do more complicated math (or more complicated
than our lunch budgeting anyway) to actually demonstrate that's true.