Serhiy Storchaka: I said a O(log n) data structure, so I was referring to balanced trees, like AVL, RBT or B+-tree. They are not vulnerable to sorted data. The downside is that they need the keys to provide robust comparison methods (like, if z < y < x, then z < x). 

Christian Heimes: Right, the seed indeed doesn't provides protection...

But the collision counting is compatible with your two suggestions, and solves the problem. The only difference is that you don't get the performance hit if not under attack.