False positives

[Jonathan Wight]

I'm playing with the sample code:

const char *vector[] = {"aaaaaaaaaa", "bbbbbbbbbb", "cccccccccc", "dddddddddd", "eeeeeeeeee", "ffffffffff", "gggggggggg", "hhhhhhhhhh", "iiiiiiiiii", "jjjjjjjjjj"};
unsigned int nkeys = 10;
cmph_io_adapter_t *source = cmph_io_vector_adapter((char **)vector, nkeys);
cmph_config_t *config = cmph_config_new(source);
cmph_t *hash = cmph_new(config);
cmph_config_destroy(config);
const char *key = "jjjjjjjjjj";
unsigned int id = cmph_search(hash, key, strlen(key));
fprintf(stderr, "Id:%u\n", id);
cmph_destroy(hash);
cmph_io_vector_adapter_destroy(source);

When I search for values NOT in the original vector I also get valid indexes/identifiers. How do I detect if a value is not in the original hash?

(For example the key "sheep" returns an index 3)

[Jonathan Wight]

I can also reproduce this with the cmph command line tool:

Generate keys_file.mph from keys_file

cmph -v -g keys_file

Test keys_file.mph against original keys:

[schwa@cobweb] ~$ cmph -v -m keys_file.mph keys_file
aaaaaaaa -> 0
bbbbbbbb -> 1
cccccccc -> 2
dddddddd -> 3
eeeeeeee -> 4
ffffffff -> 5
gggggggg -> 6
hhhhhhhh -> 7
iiiiiiii -> 8
jjjjjjjj -> 9

Modify keys_file to contain bogus keys:

[schwa@cobweb] ~$ cmph -v -m keys_file.mph keys_file
aaaaaaaa -> 0
jjjjjjjj -> 9
Duplicated or unknown key banana in the input
banana -> 0
abc -> 8
Duplicated or unknown key def in the input
def -> 9
Duplicated or unknown key  in the input
-> 8
foo -> 4
aaaa -> 3

This is on Mac OS X 10.5 Intel.

[Thomas Mueller]

This is normal and expected for a perfect hash function.