Which data structure is best suited for making a simple phone book program that returns a number given users name and vice versa?

Answer by Vishnu Jayvel:

Thanks for the A2A.
It depends … There is a tradeoff between space and time complexity when you use any datastructure, be it trie or ternary search tree or hash table.
Trie
  Trie uses a lot of space but we can search in O(n) where n= maximum string length.
But how much memory could you afford ?
If there is 2000 contacts and each contact at the max requires 64 bytes ( 64 character),
Worst case approximately 2000X64 bytesX(nodesize=64 bytes) = 8000KB of memory is required. If your RAM could accomodate such huge trie then you can go for it.  You will need 2 tries ( one for contact name and other for phone number) on the whole.
Ternary search tree
 Space efficient compared to Trie and it searches in O(logn) time. But you can go for either trie or Ternary search tree only if the memory could satisfy the space complexity.
Database ( Hashing)
Create a table with Phone number and contact as fields and do indexing for both the fields. You will be storing the database in the internal phone storage . Based on the query you can send back the result set from the database.
You can take advantage of pagination !You need not show entire result at the same time .For example, if the result set has 50 records fetch 10 records first and then display it the screen , at the same time keep ready of the next 10 records to be displayed in the next page and later when there is time fetch 10 more records and so on.
Since indexing is done by hashing the key(search term),If there is collision more buckets will be created.So it is important to create a good hash function so that there is little or no collision.
Blend of both trie and Hashing
If the collision is unavoidable and if there is so many buckets, hash table might take more time in fetching the result. The you can create a trie initially which can be used to fetch the correct bucket in the hash table which has the result and later you can do binary search in the set of values in the respective bucket and fetch the result.

I hope this helps. Correct me if iam wrong.

Which data structure is best suited for making a simple phone book program that returns a number given users name and vice versa?