Just store a bit (for a set) at each internal node, denoting whether a string ends there. For a map you also need a value pointer. Hashing keys is also easy: a

Just store a bit (for a set) at each internal node, denoting whether a string ends there. For a map you also need a value pointer. Hashing keys is also easy: add a pointer to a linked list of key-value pairs to each leaf node. To save space you could even use a flag bit and then a pointer to a single key-value pair, or a linked list in case of collision. Note that you can store tuples directly as the concatenation of their fields; no need to use hashing.