Hacker News Reader

Comment by btilly | Hacker News Reader

You're wrong. What's worse, you're being pedantic about being wrong.

If your hash function works properly, and you are dynamically resizing your hash by a constant fraction whenever it gets too full, you can bound the probability of hash collisions above, and bound the number of expected hash collisions by a constant. As is standard in resized data structure, the resizing is individually O(n) with frequency O(1/n) for an amortized cost of O(1) per insert.

Put all of that together, and the amortized average cost of an insert into the hash is O(1). This is a well-known standard result, and is the reason why hashes are useful.

View on HN

To be a pedantic here, I don't think term amortized average cost is useful.

For what I've understood, average cost means average over all possible random inputs. So for specific set inputs, the cost can be larger than that.

Amortized cost means the average cost of the operation over any combination of inputs. So for specific set of inputs, the cost is the stated.

For hash table insertion, both the amortized and average cost can be O(1) with linked-list confliction resolution, but whereas average time of a lookup operation is O(1), amortized is larger (I don't know if there's analysis on this, but O(n) seems correct by gut-feeling).

You have understood incorrectly. Here is http://www.cs.cornell.edu/courses/cs312/2006sp/lectures/lec1... on the topic:

Amortized analysis refers to determining the time-averaged running time for a sequence of operations.

Note that you are averaging over a sequence of operations, and not any combination of inputs. As that article goes on to explain, amortized analysis is the right thing to use for figuring out the total running time of a sequence of operations.

Let's be concrete. In the case of a dynamically resized hash, the bound on an individual hash insertion when the hashing function works is O(n) because you could be looking at the unlucky insertion that resized the hash. The amortized cost is O(1) because you get to spread that expensive resize over many individual operations. If you're building a hard real time system, you should focus on the O(n) and not use that data structure. If you just want to build a hash table, the O(1) is what matters.

What about the amortized cost of many random hash lookups with linked-list conflict resolution? The distribution of buckets with different numbers of items approximately follows a Poisson distribution. From that we can estimate the average number of comparisons. And find out that the amortized cost is on average O(1).

Reply on news.ycombinator.com