tree vs a flat hashtable.

[William Stacey [MVP]]

I am doing a dns zone type of project which has an inverted tree like you
all know.
test.com. (top node. value contains arraylist of all test.com records)
www.test.com. (node. value contains arraylist of all matching rrs)
www.sub1.test.com.
....

Bind and (probably) MSs dns, use a tree structure (i.e. red-black tree, etc)
to store and search this data. However, I am thinking this is not required.
I could just use a hash table with the ownerNames as keys. Any rr with
duplicate ownerName is stored in the node (i.e. the value object), so not
sure why I would need/want a tree when I could just use the key for a direct
lookup with the hash code. Naturally, the tree would make it easier to
convert to a GUI Tree control, but that can built by walking the hash and
figuring the heirarcy out in one pass. Although this is a dns specific
example, I am sure others have had similar dev issues with other tree like
data and could provide some thoughts. Cheers!

 

[Nicholas Paldino [.NET/C# MVP]]

William,

I think this is perfectly feasable. If anything, looking at the
examples you gave, if you process the DNS names backwards, you can cycle
through this easily. Basically, you have this:

www.test.com -> com, test, www
www.sub1.test.com -> com, test, sub1, www

When cycling through the parts, you access them backwards. Your initial
hashtable starts with com, and gets the hashtable using that as the key.
You then take the next part, and search for that entry (in this case, test).
That returns another hashtable to you. In that one, you then search for
www, or sub1 (depending on which input you are using) and so on, and so on.

It would be pretty easy to implement, if you ask me.

Hope this helps.

 

[William Stacey [MVP]]

Thanks Nicholas. That is what I was thinking as well. Direct hits would be
faster then a tree as you would find it in one hash operation.

www.test.com -> com, test, www
www.sub1.test.com -> com, test, sub1, www

When cycling through the parts, you access them backwards. Your initial
hashtable starts with com, and gets the hashtable using that as the key.
You then take the next part, and search for that entry (in this case,

test).

I was thinking it could be even simpler with no nesting other then
collecting same named records in the value object of that hash key. Both of
the above are unique names, so don't have to nest (I think.) If
www.sub1.test.com exists, I find it with one operation. If I look for
"sub1.test.com.", it does not exist, so return not found. Using a tree,
"sub1" would an empty node, but I don't think I need it here. I am getting
that feeling that this can not be this easy and maybe I am missing
something. But I can't think of how this fails at the moment. This method
will take more string space, because I have to use all the labels and not
just the next label as a tree would allow, but not sure that is big thing
unless talking 100s of thousands of records. Does clr string "interning"
eliminate this issue? hmmm. Cheers!