#6 Lookup collision for keys not present in .mph

[Keith Lazuka]

When I try to lookup the value for a key that is not in the generated .mph file, both the 'cmph' command-line tool and the cmph_search() function return an id that collides with the id for a valid key.

Maybe I'm missing something, but it seems like cmph should be able to tell you whether a key was found. Looking at main.c for the cmph tool, it seems that when given a key that was not in the original set of keys from which the .mph file was generated, it should display a message like 'Unknown key foobar in the input' and exit with a non-zero return code. But when I run it, I see no such message and the process exits with a 0 return code. (see attached file for a reproducible test case).

My setup:
Mac OS X 10.6.4
cmph 1.0 official src distribution

I also cloned your git repository and checked out an old commit (47a73e7) from July 2009 and ran the same test, and I saw the same behavior (searching for a key that should not be found returned a valid id and exited with a 0 return code).

[Keith Lazuka]

Test case

[Davi de Castro Reis]

This is expected behavior. It is impossible to implement membership queries in a perfect hash function since the input space is infinite. If you want to do membership queries, you need to store the keys and check collisions.

[Keith Lazuka]

I figured that that was the case. Thanks for the clarification.

[Benoit Favre]

Can you write that on the main page? It is not obvious in the current writing that MPHs are not hash tables and do only half of the job.