3 ms·

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 l

by rand_r 10y ago

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.

lkitching 10y ago
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.
- rand_r 10y ago
  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.
  - krona 10y ago
    Unless you're using an Open addressing scheme like cookoo which ensures constant lookup time in the worst case
to3m 10y ago
If the cost of a hash function is related to anything, it is more usually the number of bits in the input.