Jump to content
Sign in to follow this  
SumTingWong

Simple hash tables

Recommended Posts

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.

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

Share this post


Link to post
Share on other sites
Insolence

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


"I thoroughly disapprove of duels. If a man should challenge me, I would take him kindly and forgivingly by the hand and lead him to a quiet place and kill him." - Mark TwainPatient: "It hurts when I do $var_"Doctor: "Don't do $var_" - Lar.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.