- It looks up the same key on every iteration, so every level of the trie stays in the cache, no matter how large the nominal data set size is.
- The setup appears to be such that even though the key is 128 bytes, it's probably not going to share a prefix longer than 4-5 bytes.
- The code is constructing a temporary string of the 128 byte key for every lookup in the hash table (by going from a string to char-pointer to string), but not for the trie.
So it first eliminates the problems of a trie (especially the cache inefficiency) by an unrealistic test setup, and then has a bug introducing probably a factor of 2 unnecessary overhead to the hash table.