Simple hash tables

[SumTingWong]

This is a very simple implementation of hash tables. It can be useful for manipulating large text files in memory. For example, if you read a large text file into an array, you have to linearly go through the array to look up an item. Using a hash table, you can look up the item quicker by using the hash function, which in this case is string length mod table size.

To avoid collisions, I am using Chr(3) as the item text separator since it's not really efficient to try and implement a linked list using just arrays.

expandcollapse popup

Global $sItemTextSeparator = Chr(3)

Dim $saHashTable[20], $nIndex, $nOldIndex

_ResetHashTable($saHashTable)
_AddHashItem($saHashTable, "This is a test")
_AddHashItem($saHashTable, "This is a another test")
_AddHashItem($saHashTable, "This is a yet another test")
_AddHashItem($saHashTable, "This is really a test")
_AddHashItem($saHashTable, "This is really really a test")
_AddHashItem($saHashTable, "This is really really really a test")
_AddHashItem($saHashTable, "This is really really really not a test")
_AddHashItem($saHashTable, "This is really really not a test")
_AddHashItem($saHashTable, "This is really not a test")
_AddHashItem($saHashTable, "This is not a test")
_AddHashItem($saHashTable, "This is not really a test")
_AddHashItem($saHashTable, "This is not really really a test")
_AddHashItem($saHashTable, "This is not really really really a test")
_AddHashItem($saHashTable, "This is getting silly")
_AddHashItem($saHashTable, "This is getting really silly")
_AddHashItem($saHashTable, "This is getting really really really silly")
_AddHashItem($saHashTable, "This is really getting silly")
_AddHashItem($saHashTable, "This is really really getting silly")
_AddHashItem($saHashTable, "This is really really really getting silly")

$nIndex = _LookupHashItem($saHashTable, "This is getting silly")
MsgBox(4096,'debug:' , '$nIndex:' & $nIndex);### Debug MSGBOX 
MsgBox(4096,'debug:' , '$sItem:' & $saHashTable[$nIndex]);### Debug MSGBOX 

$nOldIndex = $nIndex
$nIndex = _ReplaceHashItem($saHashTable, "This is getting silly", "Tis the silly season")
MsgBox(4096,'debug:' , '$nIndex:' & $nIndex);### Debug MSGBOX 
MsgBox(4096,'debug:' , '$sItem:' & $saHashTable[$nIndex]);### Debug MSGBOX 
MsgBox(4096,'debug:' , '$nOldIndex:' & $nOldIndex);### Debug MSGBOX 
MsgBox(4096,'debug:' , '$sOldItem:' & $saHashTable[$nOldIndex]);### Debug MSGBOX 


Func _ResetHashTable(ByRef $saTable)
   Local $n
   
   For $n = 0 To UBound($saTable)-1
      $saTable[$n] = ""
   Next
EndFunc

Func _AddHashItem(ByRef $saTable, $sItem)
   Local $nIndex = Mod(StringLen($sItem), UBound($saTable))
   If Not StringInStr($saTable[$nIndex], $sItem) Then
      $saTable[$nIndex] = $saTable[$nIndex] & $sItem & $sItemTextSeparator
      Return $nIndex
   Else
      Return -1
   EndIf
EndFunc

Func _LookupHashItem($saTable, $sItem)
   Local $nIndex = Mod(StringLen($sItem), UBound($saTable))
   If StringInStr($saTable[$nIndex], $sItem) Then
      Return $nIndex
   Else
      Return -1
   EndIf
EndFunc

Func _ReplaceHashItem(ByRef $saTable, $sOldItem, $sNewItem)
   Local $nIndex = _LookupHashItem($saTable, $sOldItem)
   If $nIndex > -1 Then
      $saTable[$nIndex] = StringReplace($saTable[$nIndex], $sOldItem & $sItemTextSeparator, "")
      Return _AddHashItem($saTable, $sNewItem)
   Else
      Return -1
   EndIf
EndFunc

[Insolence]

So basically it's like one big line with delimeters?

[SumTingWong]

So basically it's like one big line with delimeters?

<{POST_SNAPBACK}>

Yeah, but the big line is broken up into smaller chunks so it's more efficient. It's a half way between storing each line as an array element and storing the whole file in a single string.