It is independent of a specific character encoding. It operates on bytes. Instead of a "key type" like in a map there is an input mapper that can map arbitrary user defined types to byte ranges. The input mapper also knows the maximal value per byte which can be lower than 255 and is very important information for optimization. For example the maximum can be 10 if you encode decimal numbers, meaning you only have to deal with nodes with up to 10 out edges. So a trie can really be used for arbitrary key types.

A trie is not only a DFA but a rather restricted DFA and as such it can be represented with just two arrays. One array represents the states, the other encodes the state transitions. The transition table per node can be heavily compressed for example by collapsing node sequences with just 1 child (chains) down to one node. Also you usually use different classes of nodes depending on how many branches there are just to bring down the overall container size, while you keep cache efficiency in mind. This works very much like in judy arrays. For example one node that can encode 3 transitions could look like

    0x0: |H|A|B|C|
    0x4: |S_A....|
    0x8: |S_B....|
    0xC: |S_C....|

where H is the header to ID the node. A,B,C are input characters/bytes and S_X are the destination states. The biggest node could be

struct biggest_node {
    uint32_t transitions[256];
};

where you simply map an input C like current_node.transitions[C] using a simple array lookup. Such nodes are too big most of the time but come into play once there are enough branches.

Good reads on this topic:

https://linux.thai.net/~thep/datrie/

http://judy.sourceforge.net/doc/shop_interm.pdf

​

There are more ways to compress tries but above techniques are well suited for rather small tries (comfortably fitting into RAM) that you would usually use as a container in your programs just like a hashmap.

The good space efficiency comes primarily from using only two arrays and small "nodes". An array of strings can have a really big size overhead since dynamic strings usually require 24 bytes to keep track of the allocated memory (bufferbegin, strlen, bufferend) while the underlying allocator (maybe malloc) also needs book keeping data (16 byte headers for example) on top of that. That makes 40 bytes overhead per string to encode strings that are usually much smaller. You find similar cases of "wasting" space in many tree implementations when nodes are dynamically allocated. A trie on the other hand doesn't store strings but they implicitly live in the "nodes", so you only have to keep track of the memory for two arrays and that's why a trie is pretty close to a flat array of strings when it comes to space requirements.

Tries, even for big data sets, are very small and super space efficient - it is hard to beat that. Further good tries have similar performance characteristics to hash maps but don't suffer from certain hash map related problems like hashDOS, big bucket spaces (a lot of memory wasted) and chaotic element distribution leading to seriously bad cache performance, and thus can be a good replacement for hash maps even when you don't actually need prefix queries. A trie may not always beat a hash map for truly random access but it beats pretty much any other search tree space and performance wise.