How to implement an associative array/map/hash table data structure (in general and in C++)

Question

Well I'm making a small phone book application and I've decided that using maps would be the best data structure to use but I don't know where to start. (Gotta implement the data structure from scratch - school work)

Answer 1

A simple approach to get you started would be to create a map class that uses two vectors - one for the key and one for the value. To add an item, you insert a key in one and a value in another. To find a value, you just loop over all the keys. Once you have this working, you can think about using a more complex data structure.

Answer 2

Tries are quite efficient for implementing maps where the keys are short strings. The wikipedia article explains it pretty well.

To deal with duplicates, just make each node of the tree store a linked list of duplicate matches

Here's a basic structure for a trie

struct Trie {
   struct Trie* letter;
   struct List *matches;
};

malloc(26*sizeof(struct Trie)) for letter and you have an array. if you want to support punctuations, add them at the end of the letter array.

matches can be a linked list of matches, implemented however you like, I won't define struct List for you.

Answer 3

Simplest solution: use a vector which contains your address entries and loop over the vector to search.

A map is usually implemented either as a binary tree (look for red/black trees for balancing) or as a hash map. Both of them are not trivial: Trees have some overhead for organisation, memory management and balancing, hash maps need good hash functions, which are also not trivial. But both structures are fun and you'll get a lot of insight understanding by implementing one of them (or better, both :-)).

Also consider to keep the data in the vector list and let the map contain indices to the vector (or pointers to the entries): then you can easily have multiple indices, say one for the name and one for the phone number, so you can look up entries by both.

That said I just want to strongly recommend using the data structures provided by the standard library for real-world-tasks :-)

Answer 4

Wow thanks for the quick help guys... Umm yeah about that - maps not handling collisions... how different is a binary tree from a map? I looked at Hash Tables and maps because it seems to suit the way a phone book is used well.

I'm also not too clear on the difference between hash tables and maps and all that.

I was thinking of a Hash Table but the impression I was getting is that it's too complex for me to learn because of all the efficiency considerations taken into account like load factor and all whatnot... along with the limited notes I could find on implementing the data structure...

Edit: Oh and also... in this course we've been taught Arrays, Linked Lists, Queues, Stacks and Trees so I'm somewhat familiar with those, now we're supposed to implement one of those or any other data structure in some simple application. We're also not allowed to use the STL so that's one limitation I have.