ShowUsYour<Blog>

Irregular expressions regularly

Messing around with a HashTable

I was messing around with collections today and decided to try and work out how the HashTable stores/returns it's items so, I ran the following test:

Dim nums As Integer() = {99, 4, 60, 110, 5}
Dim ht As New Hashtable
For Each num As Integer In nums
    ht.Add(num, num)
Next
Label1.Text = ""
For Each key As Object In ht.Keys
    Label1.Text &= key.ToString() & " :: " & key.GetHashCode() & Environment.NewLine
Next
    ' Prints
    ' 110 :: 110
    ' 5 :: 5
    ' 60 :: 60
    ' 4 :: 4
    ' 99 :: 99

I'm not sure exactly what that means with regard to how the enumerator algorithms traverses it's children but, I'm kinda guessing that, under the covers the HashTable uses an algorithm to re-order its children to stop it becoming lopsided which probably resulted in a structure resembling:

    110
    / \
   5   60 
  /     \
 4       99

While on the subject of structures, I just noticed that Scott Mitchell has a new series starting on them at Msdn : Read Part 1 here.

Posted: Nov 21 2003, 12:34 PM by digory | with 1 comment(s)
Filed under: ,

Comments

Scott Mitchell said:

Woot! That article is up! Hehe. Darren, I have already written part 2, which talks about Hashtables, so your questions will be answered!

Ok, here's a sneak peak. The hashtable does not store the data in any sort of tree structure. Rather, it stores the data in an array. Hashing is the process of mapping the key to an array index. This value is computed by a formula that involves the hashcode of the object being added to the hash (which is accessible via the GetHashCode() method). (I discuss the precise equation in my Part 2 article...)

Anywho, when you enumerate through the hashtable it enumerates from the first item in the underlying array on down - NOT in the order of insertion. The ordering in that underlying array is based on the equation aforementioned, which in part involves the GetHashCode() value of the object being stored.

If this makes no sense, don't worry. I discuss hashtables in detail in Part 2. Essentially, hashtables provide a means for constant-time access (like an array), but better than an array because it offers constant time searching too!
# November 21, 2003 12:11 AM
Leave a Comment

(required) 

(required) 

(optional)

(required)