gregorius - there are a few different ways you might go about this. Could you give a few more requirements?
Are you interested in a highly optimised solution, or will something simple be preferable?
Does the program need to be relatively fast, i.e. does it need to do, say, more than 1,000 lookups/second?
Will the program add to the data, i.e. add new numbers and names, while it is being used?
Are updates frequent, i.e. several/second, or rare, i.e. one/day.
Will the program need to remove names and numbers while it's being used (unusual to do this, but maybe)?
Are deletions frequent or rare?
Is there any information about 'hit' patterns, i.e. is a small number of caller-IDs likely to be the majority of lookups?
Does the program need to store a relatively short name, like older mobiles which might only have 12-14 characters, or does it need to store a name no matter how long it is?
If it is fixed data, all known ahead of time, and it must be extremely quick at lookup, you could use a perfect hash:
http://en.wikipedia.org/wiki/Perfect_hash_function
Make it even easier by using a fixed size for names. Run the algorithm to generate the perfect hash on a host PC. To decouple the code from the data, load the data and hash terms into serial flash (with a little program), and the lookup program might read the hash terms when it starts.
For a more traditional solution, almost any algorithm book will give plenty of solutions. Look for something which is suitable for disk access. If the names are fixed length, or you are willing to allocate multiples of a fixed length, you can treat the actual storage as an array of entries which makes storage management easier.
If it can afford a few seconds start up time, the program can scan the entire flash, and come up with in-RAM structures to help with access.
If additions are rare, and could be handled as a 'batch', you could hash with an overflow, and do a linear search on the overflow, then reorganise periodically.
If simplicity dominates over speed, just keep a big array of entries in flash and do a binary search. The memory is 4MByres, so about 200,000 entries. With a binary search, that is only 18 'probes' into the flash memory.
Anyway, please tells us whatever requirements you feel comfortable share, and we might be able to help.
(full disclosure: I am not a member of LeafLabs staff)
