Making your own dictionary

Disclaimer: I know your going to say just use the Dictionary<> class but I want to know how to do this.

Making a dictionary sounds pretty easy but I get stuck right away. I don't know how to match up the keys and values. I thought of a few methods but I would like your input on how to do this.

Method 1:
Have 2 arrays each holding the keys and values and I could just match them up on there positions in the array. This would require itterating over the keys array everytime I want to find the value though.

Method 2:
Almost the same as method 1 but use 2 List<>. It would work the same way, the key and the value would have the same position in the lists and I could get them easily. I'm not sure if there is really much of a difference between this and the first method.

So what do you guys think I should do?

The second is more object oriented. I just had a sort of nutty idea in my head. You have a tree structure that can branch like 'a'-'z' times. Then to search the tree, for each letter you would at max need to go through 26 things (or however many character symbols you want to include). If the tree automatically had 26 leaves, then the searching would be constant time I think, but that's a lot of wasted space (bad idea). Se, when you get to the bottom of that tree, indicating you found a match, it will be connected to it's definition. I made this pretty picture to illustrate my idea. There might be drawbacks to such a datastructure, and I'm thinking about what they could possibly be.

Thats a very neat idea. Not good for every situation as the keys would have to be strings. To me it apears one of the only draw backs are if the key is long in length, but that is totaly up to the user so it shouldn't be much of a problem.

What I think your saying is that each leaf would be a struct. That struct would either hold an array of more leafs or contain the value/definition. If that is what you mean, that sounds really good.

btw nice picture

Code:

---

root node { array of child nodes };
child node type 1 { letter, state, union { array of child nodes, definition } };

---

Or also what I was thinking in a more C like sense

Code:

---

root node { pointer to array of child nodes }
child node type 1 { letter, pointer to array of child nodes };
child node type 2 { letter, pointer to array of child nodes = 0, definition };

---

And once the app detects that the array of child nodes is NULL, it changes how it looks at the type, and see's that it will have a definition.

>> Not good for every situation as the keys would have to be strings. To me it apears one of the only draw backs are if the key is long in length, but that is totaly up to the user so it shouldn't be much of a problem.

What else would the key be if you're looking through a dictionary? You could even be going through the tree as the user types, I can't see why the length would be a drawback.

>I just had a sort of nutty idea in my head.
That's the idea behind a data structure called a trie. It's very efficient for exact matches and can easily be adapted to handle fuzzy matches as well.

>Making a dictionary sounds pretty easy but I get stuck right away.
Making a dictionary isn't terribly difficult. Making a good one takes quite a bit of effort. ;)

>I don't know how to match up the keys and values.
Keys and values are stored as pairs in whatever data structure you choose. Something like this would work for a simple dictionary made out of a list:

Code:

---

using System.Collections.Generic; // For List<>
using System.Web.UI;              // For Pair

// Create a list of key/value pairs
List<Pair> dict = new List<Pair>();

// Add a new key/value pair to the list
dict.Add( new Pair( key, value ) );

---

Of course, you might want something a little more detailed than the Pair provided by .NET.

Okay, I just realized I need 2 dictionaries. 1 for string string pairs and anouther for type type (type being any type, generic). The string dictionary I think I got down and I can do that from here, thanks for the help. But the second one I only face 1 minor problem now. Prelude's code works fine (only difference is I use KeyValuePair<> instead because it is generic). But if I use pairs I don't see any efficient way of getting the collections of the keys and values seperate from each other wich is one of the big things I want to do.

>> But if I use pairs I don't see any efficient way of getting the collections of the keys and values seperate from each other wich is one of the big things I want to do.

Why would you want to get either one in isolation of the other?

Because somtimes I need to access with the key, but other times I need to access just the values, or in rare cases just the keys.

Well, why would you want access to the key alone? Dictionaries don't work like phonebooks. And if you were designing something like a phoinebook where you could do reverse lookups, you would probably have different design granted. Would you go from value -> get a key?

Why would you want to access just the values? With my design, you could visit the tips of all the branches, and then definition would be there. You could do that operation in order and read the dictionary like a book.

Hmm maybe I didn't mention this but your idea for the dictionary with the strings is great. I am going to do something like that, but now I also need a dictionary class (like the Dictionary<>) that can take any type (in my case an int). So what I'm talking about now is a whole nouther class here completely seperate from the one you told me about.

So the one I am talking about making now is not for a real dictionary with definitions.