Tries are rarely the most efficient option.

Kind of like linked lists...conceptually pleasant but rarely if ever the best option for real-world perf.

There's a reason everybody uses hashing - if your data is trusted, it does very few operations.

Tries have to allocate, walk, and interpret multiple nodes. Perhaps not as bad as trees (though that depends on how many possible trie node representations there are, vs what the data density is at each level), but still worse than the non-colliding hash.

That said, with a finite dataset a perfect hash would probably beat a general hash though.

Was the list of city names known? Could you statically pre-build the Trie structure?

It was known, but the requirement was that the program keep working for an arbitrary keyset that conforms to the specified rules (up to 10,000 unique keys, each up to 100 bytes in length).

There is one entry which uses a trie, but it's not at the top, IIRC (which may or may not be related to using a trie, there's many other relevant design decisions).

Interestingly enough, that was my first idea. But when you consider the tiny keyset size, it would be hard to beat two machine instructions to calculate the hash + a single array lookup.

Top solutions tend to use hashes that ignore many input bytes. Even if they did not, they would use hashes that consume 4 or 8 bytes of input at a time (you could do more if the language exposed aesenc)