C/sorting.and.searching.cormen.algo/src/vph.txt

   1 Attribute VB_Name = "Hash"
   2 Option Explicit
   3
   4 ' hash table algorithm, object method
   5
   6 Private hashTableSize As Long       ' size of hashTable
   7 Private hashTable() As CHash     ' hashTable(0..hashTableSize-1)
   8
   9 Public Function Hash(ByVal KeyVal As Variant) As Long
  10 '   inputs:
  11 '       KeyVal                key
  12 '   returns:
  13 '       hashed value of key
  14 '   action:
  15 '       Compute hash value based on KeyVal.
  16 '
  17     Hash = KeyVal Mod hashTableSize
  18 End Function
  19
  20 Public Sub Insert(ByVal KeyVal As Variant, ByRef RecVal As Variant)
  21 '   inputs:
  22 '       KeyVal                key of node to insert
  23 '       RecVal                record associated with key
  24 '   action:
  25 '       Inserts record RecVal with key KeyVal.
  26 '
  27     Dim p As CHash
  28     Dim p0 As CHash
  29     Dim bucket As Long
  30
  31     ' allocate node and insert in table
  32
  33     ' insert node at beginning of list
  34     bucket = Hash(KeyVal)
  35     Set p = New CHash
  36     Set p0 = hashTable(bucket)
  37     Set hashTable(bucket) = p
  38     Set p.Nxt = p0
  39     p.key = KeyVal
  40     p.rec = RecVal
  41 End Sub
  42
  43
  44 Public Sub Delete(ByVal KeyVal As Variant)
  45 '   inputs:
  46 '       KeyVal                key of node to delete
  47 '   action:
  48 '       Deletes record with key KeyVal.
  49 '   error:
  50 '       errKeyNotFound
  51 '
  52     Dim p0 As CHash
  53     Dim p As CHash
  54     Dim bucket As Long
  55
  56    ' delete node containing key from table
  57
  58     ' find node
  59     Set p0 = Nothing
  60     bucket = Hash(KeyVal)
  61     Set p = hashTable(bucket)
  62     Do While Not p Is Nothing
  63         If p.key = KeyVal Then Exit Do
  64         Set p0 = p
  65         Set p = p.Nxt
  66     Loop
  67     If p Is Nothing Then Raise errKeyNotFound, "Hash.Delete"
  68
  69     ' p designates node to delete, remove it from list
  70     If Not p0 Is Nothing Then
  71         ' not first node, p0 points to previous node
  72         Set p0.Nxt = p.Nxt
  73     Else
  74         ' first node on chain
  75         Set hashTable(bucket) = p.Nxt
  76     End If
  77
  78     ' p will be automatically freed on return, as it's no longer referenced
  79
  80 End Sub
  81
  82 Public Function Find(ByVal KeyVal As Variant) As Variant
  83 '   inputs:
  84 '       KeyVal                key of node to delete
  85 '   returns:
  86 '       record associated with key
  87 '   action:
  88 '       Finds record with key KeyVal
  89 '   error:
  90 '       errKeyNotFound
  91 '
  92     Dim p As CHash
  93
  94     '  find node containing key
  95
  96     Set p = hashTable(Hash(KeyVal))
  97     Do While Not p Is Nothing
  98         If p.key = KeyVal Then Exit Do
  99         Set p = p.Nxt
 100     Loop
 101
 102     If p Is Nothing Then Raise errKeyNotFound, "Hash.Find"
 103
 104     ' copy data fields to user
 105     Find = p.rec
 106
 107 End Function
 108
 109 Public Sub Init(ByVal tableSize As Long)
 110 '   inputs:
 111 '       tableSize               size of hashtable
 112 '   action:
 113 '       initialize hash table
 114 '
 115     hashTableSize = tableSize
 116     ReDim hashTable(0 To tableSize - 1)
 117 End Sub
 118
 119 Public Sub Term()
 120 '   action
 121 '       terminate hash table
 122 '       chained nodes are deleted automatically,
 123 '       as they're no longer referenced
 124 '
 125     Erase hashTable
 126
 127 End Sub