The structure of your data matters a lot. If one will fit in cache but the other won't, the one that fits in cache will almost always win. Then they have different big-O characteristics: binary searching an array is O(log N) where N is the number of items, a trie is O(k) where k is the length of the key, a hashtable is O(1), but this is misleading because the hash function is usually O(k) and performance can degrade to O(n) if you have lots of hash collisions.

I thought that an autocompletion widget for stock tickers would be the perfect application for tries: short, dense key space, lots of elements, and a fair likelihood of hash collisions. But apparently not, because our data size just happened to be one where cache effects dominate. I talked to one of the GMail guys later and he was quite surprised, from which I inferred (but it was not stated) that GMail probably uses tries to good effect.

Right on. My point was simply that the type of Trie you use has an effect on the data's size in memory. A dual-array setup is pretty good at keeping the data small... There's very little pointer overhead and proximity is fairly good as well.