A trie is O(k), where k is the length of the key on inserts and deletes. Generally, any hashing algorithm is also O(k) with the additional overhead of the lookup in the table. This also ignores that most hashes have only amortized O(1) inserts. A trie usually also exhibits better memory locality and caching behavior. Also, a trie (like most tree data structures) can be implemented in a lock-free format fairly easily.