An appropriate data structure to search for a person’s phone number, given their name?

Question

Suppose you want to write a program that implements a simple phone book. Given a specific name, you want to get the person’s phone number as quickly as possible. What data structure would you use to store your phone book and why?

Answer 1

The text below answers your question.

In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys (for example, a person’s name) , to their associated values (for example, their phone number) . Thus, the hash table implements an associative array. The hash function is used to convert the key to an index (hash) array (slot or bucket), where the corresponding value is equal to look for.

text from wiki: hashtable.

there are some additional discussions, such as collision, hash functions ... for more details see the wiki page.

Answer 2

I respect and love hashtables :), but even a balanced binary tree would be great for your phone book application, giving you in the worst case logarithmic complexity and avoiding you for good hash functions, collisions, etc., which are more suitable for huge amount of data.

When I talk about huge data, what I mean refers to the repository. Each time you fill all the buckets in the hash table, you will need to allocate a new repository and rename everything. This can be avoided if you know the size of the data in advance. Balanced trees will not allow you to delve into these problems. The domain must be considered when designing data structures, for example, for storing small devices.

Answer 3

I was wondering why "Tries" did not appear in one of the answers, Tries is suitable for the type of phone book.

In addition, space savings compared to HashTable at the same cost (almost) extraction efficiency (provided that the alphabet names are of constant size and constants)

Also helps when searching for 'Prefix Matches' 'Prefix Matches' .

Answer 4

The dictionary is dynamic and fast.

Answer 5

You need a dictionary in which you use the name as the key, and the number as the stored data. Check this out: http://en.wikipedia.org/wiki/Dictionary_%28data_structure%29

Answer 6

Why not use a singly linked list? Each node will have a name, number and link information.

One of the drawbacks is that your search may take some time, since you will have to go through the entire list from link to link. You can order the list during insertion of the node itself!

PS: To speed up the search, keep a link to the middle of the list. The search may continue to the left or right of the list, depending on the value of the "name" field in this node. Please note that this requires a double-linked list.