CODEWITHSUNDEEP
c++hashperfect-hash
user1377000
user1377000

Reputation: 1473

Perfect hash for string with known number of keys

Is it possible to have a perfect hash function from strings to integers, when the number of elements to be hashed is known? By perfect hash function I mean that there is no chance of collision.

Basically I am reading the signatures of multiple tables from a file (e.g. id, name, address). Different tables might have common attributes (e.g. name), but on different positions (i.e. columns). I would like to be able to ask something like: what is table1["name"]? or table2["name"].

UPDATE: I would prefer learning to do it myself than using something already out there.

Upvotes: 4

Views: 2455

Answers (1)

Shantanu
Shantanu

Reputation: 383

See GNU gperf.

GNU gperf is a perfect hash function generator. For a given list of strings, it produces a hash function and hash table, in form of C or C++ code, for looking up a value depending on the input string. The hash function is perfect, which means that the hash table has no collisions, and the hash table lookup needs a single string comparison only.

Upvotes: 4

Related Questions