I was explaining to Aura on MSN how to do Hash Tables, and he suggested that I post the functions up here for others to use. A hash table allows you to store and retrieve values in a table based on a string 'key'. This has many uses, such as storing user details by name, managing variables in a script interpreter, etc. These functions don't allow a dynamic hash table, but I'll do that later(or you can, if you can work out how).
Functions
result = HashTable_Insert(key as string, value as integer)
Inserts a value into the table based on the key. You later use the key to access this data. This function returns 1 on success, or 0 if the table is full.
result = HashTable_Remove(key as string)
Removes an entry from the table.
result = HashTable_GetValue(key as string)
Retrieves a value from the table that corresponds with
key. If there is no such entry in the table, this function returns 0.
result = HashTable_GetKeyEntry(key as string)
Used by the other functions. This gives you the index of an entry in the table's array that has a matching key. If there is no such entry in the table, this function returns -1.
result = HashTable_ResetTable(key as string)
Removes all entries from the table.
result = HashTable_HashGen(key as string)
Used by other functions. A very simple hash generating function. This function returns a hash based on the key you give it. You may want to have a go at creating your own hashing function however, as you may be able to make it more efficient to your needs.
function HashTable_Insert(key as string, value as integer)
`This function adds a new entry to the table.
`If the entry already exists, it is updated.
local added as boolean
local hash as integer
local entry as integer
hash = HashTable_HashGen(key)
`If key found, update it, else add it
entry = HashTable_GetKeyEntry(key)
if entry>-1
hashtable(entry).key = key
hashtable(entry).value = value
exitfunction 1
else
while hash<HASHTABLESIZE
if hashtable(hash).key=""
exit
endif
inc hash
if hash = HASHTABLESIZE then exitfunction -1
endwhile
hashtable(hash).key = key
hashtable(hash).value = value
exitfunction 1
endif
endfunction 0
function HashTable_Remove(key as string)
local entry as integer
entry = HashTable_GetKeyEntry(key)
if entry = -1 then exitfunction
hashtable(entry).key = ""
hashtable(entry).value = -1
endfunction
function HashTable_GetValue(key as string)
local found as boolean
local hash as integer
local value as integer
hash = HashTable_HashGen(key)
while hash<HASHTABLESIZE
if hashtable(hash).key=key
value = hashtable(hash).value
exitfunction value
else
if hashtable(hash).key="" and hashtable(hash).value = 0
exitfunction 0
endif
endif
inc hash
endwhile
endfunction 0
function HashTable_GetKeyEntry(key as string)
local hash as integer
hash = HashTable_HashGen(key)
while hash<HASHTABLESIZE
if hashtable(hash).key=key
exitfunction hash
else
`If found blank entry, exit
if hashtable(hash).key="" and hashtable(hash).value = 0
exitfunction -1
endif
endif
inc hash
endwhile
endfunction -1
function HashTable_ResetTable()
for x=0 to HASHTABLESIZE
hashtable(x).key = ""
hashtable(x).value = 0
next x
endfunction
function HashTable_HashGen(key as string)
local output as integer
for x=1 to len(key)
output = output + asc(mid$(key, x))
next x
output = output mod HASHTABLESIZE
endfunction output
The type, hash table size, and the table itself must be created (this goes before any other code):
type element
key as string
value as integer
endtype
global HASHTABLESIZE as integer = 100
dim hashtable(HASHTABLESIZE) as element
Next you need to copy and paste the functions to the bottom of your code(or in an include file).
And now a little example of them in action:
local myVariable as string
local myValue as integer
local choice as integer
do
cls
set cursor 0, 0
print "What do you want to do?"
print "1. Add/Update a variable"
print "2. Delete a variable"
print "3. View a variable's contents"
input "Choice: ", choice
print ""
select choice
case 1:
input "Variable name: ", myVariable
input "Variable value: ", myvalue
HashTable_Insert(myVariable, myValue)
print "Inserted variable into table"
endcase
case 2:
input "Variable name: ", myVariable
HashTable_Remove(myVariable)
print "Removed variable from table"
endcase
case 3:
input "Variable name: ", myVariable
print "Contents of "+myVariable+" = "+str$(HashTable_GetValue(myVariable))
endcase
endselect
print
print "Press any key to continue"
wait key
loop
end
Tempest - P2P UDP Multiplayer Plugin - 80% - 15%
Want to try the beta? E-mail me.
