0

Let's say I want to model a phonebook.

I would like a phonebook to be maintained in sorted order by name of the person that the phonebook entry is created for. However, since it is quite possible that there are two people with the same name, I cannot use any of the sorted collections, because they require the use of keys (which, by definition, must be unique). On the other hand, I must have some sort of unique identifier for each entry, should I desire to implement the phonebook as a service, otherwise, I would have no way to identify the entry that I would like to update or delete.

I would like to hear suggestions and ideas on how to organize the data and the process of adding and updating it, so it is ordered in a desired way, and yet maintain the possibility of quick lookup of a single entry based on a unique id.

The idea that is closest to me goes something like this.

Phonebooks are organized alphabetically, so one of the approaches might be something like this:

SortedDictionary<char, List<PhonebookEntry>> phonebook = new SortedDictionary<char, List<PhonebookEntry>>();

The key would be the first character of the PhonebookEntry primary identifier (name).

The list would be maintained in sorted order on insert and update. The insert would search for the index in the list where the entry should be added, and then insert the entry at that index. Alternative would be a brute force approach: to simply sort the list after each insert. Update would check whether the name of the entry was updated. If so, it would sort the list accordingly if the entry remains in the same list, or it would remove it from that list and insert it in the appropriate list of the dictionary.

Now, the problem is how to find the entry based on some sort of unique identifier that would be assigned to each entry (some GUID, for instance). I am closest to the idea to have another dictionary, like this:

Dictionary<Guid, Tuple<char, long>> phonebookEntryMap = new Dictionary<Guid, Tuple<char, long>>();

The key would be the unique ID of the entry, the value would be a Tuple that contains the first character of the entry (to identify it in the main structure) and the index in the list. The obvious downside to this approach is that this structure needs to be carefully maintained. The upside is that it is a minimal memory overhead, while providing all the information required for a quick access to the desired entry.

An alternative would be to keep a reference to PhonebookEntry in the mapping dictionary instead of the Tuple. It would require more memory, but no mapping overhead.

Are there any other suggestions on how to elegantly resolve this problem?

  • May I ask the background to this question, i.e. why you are looking for efficiency? These days, computational power is so good that very large lists can be searched and sorted very quickly. That causes me to give much greater emphasis to code readability and ease-of-understanding rather than having data structures that are too fancy. – Brad Thomas Jan 18 '17 at 20:17
  • This is just an example that demonstrates what was bothering me in an application that requires maximum efficiency (where every ms counts) – Vladimir Stokic Jan 19 '17 at 9:39
1

I think what you're looking for is a "MultiMap". It's basically a map which can have several values per key. You can also do it based on a normal Map<String, List<PhoneEntry>> but it's less convinient.

The more important aspect is that it's a tree based map. Then you'll have insertions and removals in O(log(N)) and ordered listing in O(1) since it's just "walking the tree".

...and if you want lookups / listings according to several keys (i.e. name or guid), just maintain multiple maps. That's it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.