Hash tables, in general, have average constant time lookup. Only some hash tables have amortized constant time lookup. An amortized bound is a bound on the to

Hash tables, in general, have average constant time lookup. Only some hash tables have amortized constant time lookup. An amortized bound is a bound on the total cost of a sequence of operations. Loosely speaking, it guarantees that you can't keep hitting the worst case indefinitely. An average bound is averaged over all possible inputs, but doesn't protect you against hitting the worst case over and over.