Menu Introduction Open Hashing Hash Functions Data Structures Comparison Conclusion Bibliography

Data Structures

If you plan to code your own hashing algorithm, you'll need a way to store data in nodes, and a method for referencing the nodes. This may be done by storing nodes in objects and arrays. I'll use a linked-list to illustrate each method.

Objects

References to objects are implemented as pointers in Visual Basic. One implementation simply defines the data fields of the node in a class, and accesses the fields from a module:

' in class CObj
Public NextNode As CObj
Public Value As Variant

' in module Main
Private hdrObj As CObj
Private pObj As CObj

' add new node to list
Set pObj = New CObj
Set pObj.NextNode = hdrObj
Set hdrObj = pObj
pObj.Value = value

' find value in list
Set pObj = hdrObj
Do While Not pObj Is Nothing
    If pObj.Value = value Then Exit Do
    Set pObj = pObj.NextNode
Loop

' delete first node
Set pObj = hdrObj.NextNode
Set hdrObj = pObj
Set pObj = Nothing

In the above code, pObj is internally represented as a pointer to the class. When we add a new node to the list, an instance of the node is allocated, and a pointer to the node is placed in pObj. The expression pObj.Value actually de-references the pointer, and accesses the Value field. To delete the first node, we remove all references to the underlying class.

Arrays

An alternative implementation allocates an array of nodes, and the address of each node is represented as an index into the array.

' list header
Private hdrArr As Long

' next free node
Private nxtArr As Long

' fields of node
Private NextNode(1 To 100) As Long
Private Value(1 To 100) As Variant

' initialization
hdrArr = 0
nxtArr = 1

' add new node to list
pArr = nxtArr
nxtArr = nxtArr + 1
NextNode(pArr) = hdrArr
hdrArr = pArr
Value(pArr) = value

' find value in list
pArr = hdrArr

Do While pArr <> 0
    If Value(pArr) = value Then Exit Do
    pArr = NextNode(pArr)
Loop

Each field of a node is represented as a separate array, and referenced by subscripts instead of pointers. For a more robust solution, there are several problems to solve. In this example, we've allowed for 100 nodes, with no error checking. Enhancements could include dynamically adjusting the arrays size when nxtArr exceeds array bounds. Also, no provisions have been made to free a node for possible re-use. This may be accomplished by maintaining a list of subscripts referencing free array elements, and providing functions to allocate and free subscripts. Included in the download is a class designed to manage node allocation, allowing for dynamic array resizing and node re-use.