After a weekend of looking at my whiteboard, this is what I've come up with.
I'm pleased to announce that after nearly ten years of using hash maps in ZPE, I've switched to using my new binary search tree implementation. This improves performance further than before since in some cases my hash map, which is some 8 years old, would lead to collisions that in turn presented a O(n) case. This was not good.
The worst case for a binary search tree is indeed O(n) also and it's best case is actually worse than that of a hash map, which is O(1), but I've been testing out a new binary search tree I've developed and it performs marginally better. What's really cool about the binary search tree implementation is that it is actually a drop in replacement for the hash map I've been using for the last few years with methods like put, get and so on.
Throughout the next few weeks I'll continue to assess this.
