-2

Regular hash functions, in which collisions are probable, run in constant time: O(1). But what is the time complexity of a perfect hash function? Is it 1?

user9518322
  • 1
  • 1
  • 2
    There is no requirement, therefore it is arbitrary. – user1095108 Dec 21 '18 at 19:30
  • [Perfect hash function](https://tools.ietf.org/html/rfc5958). – President James K. Polk Dec 21 '18 at 20:16
  • From https://en.wikipedia.org/wiki/Perfect_hash_function: *A perfect hash function with values in a limited range can be used for efficient lookup operations, by placing keys from S (or other associated values) in a lookup table indexed by the output of the function. One can then test whether a key is present in S, or look up a value associated with that key, by looking for it at its cell of the table. Each such lookup takes constant time in the worst case.* – Jim Mischel Dec 24 '18 at 18:57

1 Answers1

0

If the hash function is intended to be used to access a hash table, then there is no difference in terms of complexity between perfect and regular hash functions, since both of them may also create collisions in the table. The reason is that the index associated to an element in a hash table is the remainder of the division of the hash by the length of the table (usually a prime number). This is why two elements which hash to different values will collide if their remainder modulo the (said) prime is the same for both of them. This means that the time complexity of accessing the table is O(1) in both cases.

Note also that the computation of the hash usually depends on the size of the input. For instance, if the elements to be hashed are strings, good hashes take all their characters into account. Therefore, for the complexity to remain O(1), one has to limit the size (or length) of the inputs. Again, this applies to both perfect and regular hashes.

Leandro Caniglia
  • 14,495
  • 4
  • 29
  • 51
  • @JamesKPolk, Thanks for calling my attention on this. I now see that I misinterpreted the question as related to hash tables. I'll change my answer. – Leandro Caniglia Dec 23 '18 at 15:04
  • You can construct a lookup table with constant access time using a [perfect hash function](https://en.wikipedia.org/wiki/Perfect_hash_function) that produces values in a limited range, *with no collisions*. See also minimal perfect hash function, https://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function. – Jim Mischel Dec 24 '18 at 18:56
  • @JimMischel Thanks. Do you know if that is practical? I mean, if the prime involved in the algorithm is too large you would be allocating an equally large table. From a time-complexity perspective this would also be bad because you will lose the benefits of CPU caches and will need to read from RAM at every access ([https://stackoverflow.com/a/53797722/4081336](https://stackoverflow.com/a/53797722/4081336)) . – Leandro Caniglia Dec 24 '18 at 22:04
  • Perfect hashing is best used when you have a known set of keys. You create a function that generates values within a limited range, usually not much larger than your known set of keys. So your hash table size is fixed, and your cache behavior is no worse than with a normal hash table.With no collisions, the discussion of collision resolution is irrelevant: there is one probe per lookup. And since every lookup is basically a random probe into the hash table, cache behavior isn't a particular concern here, either. – Jim Mischel Dec 25 '18 at 04:04