Skip to main content
MathOverflow

Return to Question

Post Closed as "Not suitable for this site" by Gro-Tsen, Alexey Ustinov, user44191, Ben McKay, Friedrich Knop
added 21 characters in body
Source Link
Glorfindel
Glorfindel
  • 2.8k
  • 6
  • 28
  • 38

The literature on minimal perfect hashing functions (mphf) says that the best function we can do will have to store 1/ln(2)$\frac1{\ln(2)}$ (~1.44) bits per key. There are some sets though that require 0 bits per key, eg the key set {apple, banana, cherry}{apple, banana, cherry} can have a mphf of the form uint32 getIndex(string key) { return key[0] - 'a'; } This

uint32 getIndex(string key) { return key[0] - 'a'; }

This function doesn't need to store information. Is the lower bound saying that given an arbitrary set there might not exist any mphf that can go lower than 1.44 bits/key but there is guaranteed to exist a mphf which only requires 1.44 bits/key?

The literature on minimal perfect hashing functions (mphf) says that the best function we can do will have to store 1/ln(2) (~1.44) bits per key. There are some sets though that require 0 bits per key, eg the key set {apple, banana, cherry} can have a mphf of the form uint32 getIndex(string key) { return key[0] - 'a'; } This function doesn't need to store information. Is the lower bound saying that given an arbitrary set there might not exist any mphf that can go lower than 1.44 bits/key but there is guaranteed to exist a mphf which only requires 1.44 bits/key?

The literature on minimal perfect hashing functions (mphf) says that the best function we can do will have to store $\frac1{\ln(2)}$ (~1.44) bits per key. There are some sets though that require 0 bits per key, eg the key set {apple, banana, cherry} can have a mphf of the form

uint32 getIndex(string key) { return key[0] - 'a'; }

This function doesn't need to store information. Is the lower bound saying that given an arbitrary set there might not exist any mphf that can go lower than 1.44 bits/key but there is guaranteed to exist a mphf which only requires 1.44 bits/key?

Source Link
Forrest Jablonski
Forrest Jablonski
  • 31
  • 1

information theoretic lower bound for hashing functions

The literature on minimal perfect hashing functions (mphf) says that the best function we can do will have to store 1/ln(2) (~1.44) bits per key. There are some sets though that require 0 bits per key, eg the key set {apple, banana, cherry} can have a mphf of the form uint32 getIndex(string key) { return key[0] - 'a'; } This function doesn't need to store information. Is the lower bound saying that given an arbitrary set there might not exist any mphf that can go lower than 1.44 bits/key but there is guaranteed to exist a mphf which only requires 1.44 bits/key?