George Peter Staplin Nov 28, 2008 - A hashing trie is a type of trie. They are much more scalable than hash tables, though they use a lot more memory. When I originally created my first trie (in C), I called it a pig structure, as I was unaware of the trie data structure.
#By George Peter Staplin
#
#This is a simple hashing trie in Tcl.
#A trie uses the actual values of a key for the path to the data.
#This uses 4 bits per path for 16 directions per node.
#
#A would generate a path of: 1 4
#AB would generate a path of: 1 4 2 4
package require Tcl 8.5 ;#uses {*}
proc trie-path str {
set r [list]
foreach c [split $str ""] {
set n [scan $c %c]
while {$n > 0} {
#We use 4 bits for each path, so we have 16 nodes.
set p [expr {$n & 15}]
#Append this to the path.
lappend r $p
#Shift 4 bits to the right now that we got 2^4 - 1 with our & earlier.
set n [expr {$n >> 4}]
}
}
return $r
}
proc trie-create {} {
#We create 17 list items. The 17th is for the value of the association.
return [lrepeat 17 [list]]
}
proc trie-set {tvar key value} {
upvar 1 $tvar t
set pathlist [trie-path $key]
#First build up a path of valid sublists.
set path [list]
foreach p $pathlist {
lappend path $p
set subt [lindex $t {*}$path]
if {![llength $subt]} {
lset t {*}$path [trie-create]
}
}
lset t {*}$pathlist 16 $value
#Enable this to see the actual serialized structure of the trie.
#puts $t
}
proc trie-get {t key valuevar} {
upvar 1 $valuevar value
set pathlist [trie-path $key]
set path [list]
foreach p $pathlist {
lappend path $p
if {![llength [lindex $t {*}$path]]} {
#This key's path is not in the trie.
return 0
}
}
set value [lindex $t {*}$pathlist 16]
#We found the value associated with the key.
return 1
}
proc main {} {
set t [trie-create]
set key1 "Peachy!"
set key2 "Harder! Better! Faster! Stronger!"
trie-set t $key1 123
if {[trie-get $t $key1 value]} {
puts "$value is associated with $key1"
}
if {[trie-get $t "invalid" value]} {
puts "err invalid key generated: $value"
}
trie-set t $key2 456
if {[trie-get $t $key2 value]} {
puts "$value is associated with $key2"
}
}
main