I think that people just take too seriously the part of "hash tables are O(1) and trees are O(log(n))". But you have to consider complexity of hash generation (in real life sometimes it's worse than tree traversal), rebalancing, order lost and programmer issues (some just ignore at all that hash collisions do happen). At least in my case, I have found that skipkists have similar performance than hash tables (ops/seq for real life loads, not infinite items), and use less memory (at least the Open vSwitch implementation).