Hacker News Reader

Not being funny, I actually don't know:

Is the n in log2(n) the size of thing you're hashing? AFAIK the O(1) statement is referring to how many things you have hashed.

View on HN

In context, n is the number of things in the hashmap. You need log2(n) bits per item to store n unique items. So the hash function is operating on an input of log2(n) bits. There's no way the hash function takes less than log2(n) time to work on log2(n) bits of input.

You don't need hash codes to be unique for items in the table so there doesn't need to be any relation between the size of the hash and the size of the table. The time taken by the hash function depends on the size of the keys not the size of the table.

If they're not unique, it will have to linearly search through items with duplicate keys. This situation will begin to approach O(n) time, which isn't good.

Unless you're using an Open addressing scheme like cookoo which ensures constant lookup time in the worst case

If the cost of a hash function is related to anything, it is more usually the number of bits in the input.

Reply on news.ycombinator.com