For hash tables you need to compute the hash function and execute an equals operation. Computing the hash function might take longer than traversing a tree. For example, if you key is "sdolkfhasodfgkokjhdfgfnaryksfdksfdgkjgf" the hash function will probably take every single letter into account (>20 operations, didn't count), whereas a binary tree might only need to look at the first letter at most nodes. So at least for relatively few entries, trees might perform better than hashtables, O(1) nonwithstanding.