Code archives/Algorithms/Container: hash table
This code has been declared by its author to be Public Domain code.
Download source code
| |||||
| This library makes it painless to add many independant hash table containers for many different types of objects. This is done by storing Handle()s to your objects. Each container should hold objects of only one type. For more information on containers, an example of how to use them, and a tutorial, click here. A hash table (or map, or dictionary) is similar to an array, but you refer to elements with a key$ instead of an index%. You also don't have to worry about the size of the container. This library is dependant upon Container: double-linked list For an example of how to use this library, scroll down to the test() function at the very bottom. This code will run standalone if you uncomment the line at the top which runs the test code. Please post bugs or feature requests in comments. Fundamentals hash_new.hashC() - create a new hash hash_destroy(our_hash.hashC) - delete a hash and all of its elements Standard Operations hash_set(our_hash.hashC, key$, value) - set a key-value pair in a hash hash_exists(our_hash.hashC, key$) - check to see if a key exists in a hash hash_delete(our_hash.hashC, key$) - delete a key-value pair in a hash, returning the value hash_get(our_hash.hashC, key$) - get a value from a hash by its key$ hash_count(our_hash.hashC) - return the number of elements in the hash Iterators ; for item.type = each our_hash it.hashC_iter = hash_iterator_begin(our_hash) while hash_iterator_next(it) key$ = hash_iterator_get_key$(it) item.type = object.type(hash_iterator_get_value(it)) ; do stuff with key$ and item wend Convenience hash_get_list.listC(our_hash.hashC, key$) - get a list from a hash by its key$, autovivifying (for hashes-of-lists) --- The Code | |||||
;test_hashC()
; ------------------------------------------------------------------------------
;= TO DO
; ------------------------------------------------------------------------------
; iterator sanity checking (try to catch problems which might be caused by deleting elements while iterating)
; replace hashC\bucket[] array with a vectorC so hashes aren't all forced to share the same number of buckets?
; ------------------------------------------------------------------------------
;= CHANGE LOG
; ------------------------------------------------------------------------------
; 12/11/2005 - iterator sample usage for quick copying and pasting
; 06/11/2005 - new() for forwards compatibility
; 06/11/2005 - dropped humpBack notation in favour of under_score
; 06/11/2005 - sexy new hash_get_list() function for hashes-of-lists
; 03/11/2005 - renamed class from hashType
; 02/11/2005 - iterators now treat null hash objects as empty hashes
; 02/11/2005 - added hash_destroy, iterators
; ------------------------------------------------------------------------------
;= INCLUDES
; ------------------------------------------------------------------------------
include "listC.bb" ; http://blitzbasic.com/codearcs/codearcs.php?code=1438
; ------------------------------------------------------------------------------
;= CONSTANTS
; ------------------------------------------------------------------------------
const HASH_MAX_BUCKETS = 512
; more buckets will make lookups faster in crowded hashes, but will use more memory
; theoretically, overhead memory usage is (buckets * 16 bytes)
; ------------------------------------------------------------------------------
;= TYPES
; ------------------------------------------------------------------------------
type hashC
field bucket.listC[HASH_MAX_BUCKETS-1] ; a list of hashC_elems
field elements%
end type
type hashC_elem
field key$
field value
end type
type hashC_iter
field hash.hashC
field current_bucket%
field current_node.listC_node
field next_node.listC_node ; keep track of this so we can safely delete the current_node
end type
; ------------------------------------------------------------------------------
;= FUNDAMENTAL
; ------------------------------------------------------------------------------
; ------------------------------------------------------------------------------
function hash_new.hashC()
; create a new hash
return new hashC
end function
; ------------------------------------------------------------------------------
function hash_destroy(our_hash.hashC)
; delete a hash and all of its elements
if our_hash = null then runtimeerror("not a valid hashC: null")
; loop through each bucket
for bucket_index% = 0 to HASH_MAX_BUCKETS-1
local this_element_list.listC = our_hash\bucket[bucket_index]
if this_element_list <> null then
; loop through each node in each bucket's list
local this_node.listC_node = this_element_list\first_node
while this_node <> null
; destroy the element
delete object.hashC_elem(this_node\value)
; advance to next node in list
this_node = this_node\next_node
wend
; destroy the bucket
list_destroy(this_element_list)
endif
next
; destroy the hash
delete our_hash
end function
; ------------------------------------------------------------------------------
function hash_set(our_hash.hashC, key$, value)
; set a key-value pair in a hash
if our_hash = null then runtimeerror("not a valid hashC: null")
; find the appropriate bucket
local our_element_list.listC = hash_choose_bucket(our_hash, key$)
; look for an element with a matching key
local this_node.listC_node = our_element_list\first_node
while this_node <> null
local this_element.hashC_elem = object.hashC_elem(this_node\value)
; if the keys match, update the value and return from the function
if (this_element\key$ = key$) then
this_element\value = value
return
endif
; look at the next node
this_node = this_node\next_node
wend
; if we didn't find an element to update, add a new element
local new_element.hashC_elem = new hashC_elem
new_element\key$ = key$
new_element\value = value
list_push(our_element_list, handle(new_element))
; update element count
our_hash\elements = our_hash\elements + 1
end function
; ------------------------------------------------------------------------------
function hash_exists(our_hash.hashC, key$)
; check to see if a key exists in a hash
if our_hash = null then runtimeerror("not a valid hashC: null")
if (hash_get(our_hash, key$) > 0) then
return true
else
return false
endif
end function
; ------------------------------------------------------------------------------
function hash_delete(our_hash.hashC, key$)
; delete a key-value pair in a hash, returning the value
if our_hash = null then runtimeerror("not a valid hashC: null")
; find the appropriate bucket
local our_element_list.listC = hash_choose_bucket(our_hash, key$)
; look for an element with a matching key
local this_node.listC_node = our_element_list\first_node
while this_node <> null
local this_element.hashC_elem = object.hashC_elem(this_node\value)
; if the keys match, remove this element and return the value
if (this_element\key$ = key$) then
local value = this_element\value
delete this_element
list_remove_node(this_node)
; update element count
our_hash\elements = our_hash\elements - 1
return value
endif
; look at the next node
this_node = this_node\next_node
wend
; if we didn't find an element to update, return 0
return 0
end function
; ------------------------------------------------------------------------------
function hash_get(our_hash.hashC, key$)
; get a value from a hash by its key$
if our_hash = null then runtimeerror("not a valid hashC: null")
; find the appropriate bucket
local our_element_list.listC = hash_choose_bucket(our_hash, key$)
; look for an element with a matching key
local this_node.listC_node = our_element_list\first_node
while this_node <> null
local this_element.hashC_elem = object.hashC_elem(this_node\value)
; if the keys match, update the value and return from the function
if (this_element\key$ = key$) then
return this_element\value
endif
; look at the next node
this_node = this_node\next_node
wend
; we didn't find the key, so return 0
return 0
end function
; ------------------------------------------------------------------------------
function hash_count(our_hash.hashC)
; return the number of elements in the hash
if our_hash = null then runtimeerror("not a valid hashC: null")
return our_hash\elements
end function
; ------------------------------------------------------------------------------
;= INTERNAL
; ------------------------------------------------------------------------------
; ------------------------------------------------------------------------------
function hash_choose_bucket.listC(our_hash.hashC, key$)
; return the linked list which corresponds with the key$
; find the appropriate bucket index
local bucket_index% = hash_key_to_bucket_index(key$, HASH_MAX_BUCKETS)
; make sure bucket has been initialized
if (our_hash\bucket[bucket_index%] = null) then
our_hash\bucket[bucket_index%] = list_new()
endif
return our_hash\bucket[bucket_index%]
end function
; ------------------------------------------------------------------------------
function hash_key_to_bucket_index%(key$, modulus%)
; come up with an index for any string, dependably coming up with the same index
; for the same string, and attempting to distribute strings evenly over the
; available indexes
local bucket_index%
local character_index
for character_index = 1 to len(key$)
local character$ = mid$(key$, character_index, 1)
bucket_index% = (bucket_index% * 123) + asc(character) ; arbitrary math, whee!
next
; force the index to be valid (overflows might make the number negative)
bucket_index% = abs(bucket_index% mod modulus)
return bucket_index%
end function
; ------------------------------------------------------------------------------
;= ITERATORS
; ------------------------------------------------------------------------------
; sample usage
; ; for item.type = each hash
; it.hashC_iter = hash_iterator_begin(hash)
; while hash_iterator_next(it)
; key$ = hash_iterator_get_key$(it)
; item.type = object.type(hash_iterator_get_value(it))
; wend
; ------------------------------------------------------------------------------
function hash_iterator_begin.hashC_iter(our_hash.hashC)
; create a new iterator for traversing the hash
; note that elements will be returned in arbitrary order!
it.hashC_iter = new hashC_iter
if our_hash <> null then
it\hash = our_hash
it\current_bucket = -1
it\current_node = null
it\next_node = null
endif
return it
end function
; ------------------------------------------------------------------------------
function hash_iterator_next(it.hashC_iter)
; advance the iterator to the next item in the hash
; drop out immediately if this iterator is void
if it\hash = null then return false
; if we aren't already going through a bucket's list, advance until we find one
while (it\next_node = null)
it\current_bucket = it\current_bucket + 1
; if we've run out of buckets, delete the iterator and return false
if it\current_bucket >= HASH_MAX_BUCKETS then
delete it
return false
endif
local bucket_list.listC = it\hash\bucket[it\current_bucket]
if (bucket_list <> null) then
; try the first node of this bucket
; (if the bucket list is empty, this will be null and the next bucket will be tried,
; otherwise the last part of this function will advance us onto this node)
it\next_node = bucket_list\first_node
endif
wend
; while we're in a bucket list, simply advance to the next node
it\current_node = it\next_node
it\next_node = it\current_node\next_node
return true
end function
; ------------------------------------------------------------------------------
function hash_iterator_get_key$(it.hashC_iter)
; return the key of the element the iterator is currently on
local this_element.hashC_elem = object.hashC_elem(it\current_node\value)
return this_element\key$
end function
; ------------------------------------------------------------------------------
function hash_iterator_get_value(it.hashC_iter)
; return the key of the element the iterator is currently on
local this_element.hashC_elem = object.hashC_elem(it\current_node\value)
return this_element\value
end function
; ------------------------------------------------------------------------------
;= CONVENIENCE
; ------------------------------------------------------------------------------
; ------------------------------------------------------------------------------
function hash_get_list.listC(our_hash.hashC, key$)
; get a list from a hash by its key$, autovivifying (for hashes-of-lists)
if our_hash = null then runtimeerror("not a valid hashC: null")
list.listC = object.listC(hash_get(our_hash, key$))
if list = null then
list = list_new()
hash_set(our_hash, key$, handle(list))
endif
return list
end function
; ------------------------------------------------------------------------------
;= TESTING
; ------------------------------------------------------------------------------
type hash_sample_type
field value$
end type
function hash_sample_type_new.hash_sample_type(value$)
i.hash_sample_type = new hash_sample_type
i\value$ = value$
return i
end function
function test_hashC()
print "test_hashC()"
local our_hash.hashC = new hashC
hash_set(our_hash, "apples", 1)
hash_set(our_hash, "oranges", 2)
hash_set(our_hash, "bananas", 8)
print "displaying all elements..."
it.hashC_iter = hash_iterator_begin(our_hash)
while hash_iterator_next(it)
key$ = hash_iterator_get_key$(it)
value = hash_iterator_get_value(it)
print key$ + " => " + value
wend
hash_delete(our_hash, "apples")
hash_delete(our_hash, "bananas")
hash_delete(our_hash, "grapefruit")
print hash_get(our_hash, "oranges")
print hash_exists(our_hash, "oranges")
print hash_delete(our_hash, "oranges")
print hash_get(our_hash, "oranges")
print hash_exists(our_hash, "oranges")
print "displaying all elements..."
it.hashC_iter = hash_iterator_begin(our_hash)
while hash_iterator_next(it)
key$ = hash_iterator_get_key$(it)
value = hash_iterator_get_value(it)
print key$ + " => " + value
wend
hash_destroy(our_hash)
; test new hash_get_list() function
print "test new hash_get_list() function..."
local HoL.hashC = new hashC
list_push(hash_get_list(HoL, "milk"), handle(hash_sample_type_new("cow")))
list_push(hash_get_list(HoL, "milk"), handle(hash_sample_type_new("goat")))
list_push(hash_get_list(HoL, "cheese"), handle(hash_sample_type_new("gouda")))
list_push(hash_get_list(HoL, "cheese"), handle(hash_sample_type_new("edam")))
list_push(hash_get_list(HoL, "cheese"), handle(hash_sample_type_new("cheddar")))
it.hashC_iter = hash_iterator_begin(HoL)
while hash_iterator_next(it)
key$ = hash_iterator_get_key$(it)
value = hash_iterator_get_value(it)
print key$ + ":"
list_it.listC_iter = list_iterator_begin(object.listC(value))
while list_iterator_next(list_it)
i.hash_sample_type = object.hash_sample_type(list_iterator_get(list_it))
print " " + i\value$
wend
wend
print "press any key to exit..."
waitkey
end
end function |
Comments
None.
Code Archives Forum
   |