[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
----
!!!!!!
%| |%
!!!!!!