Hi Jimmy, I am really sorry for my long silence.
> Does this cause a little confliction with spec, which annouced the TreeMap is Red-Black tree based? How it can be checked? There are no way to check if three is RB tree outside. What we have it is TreeMap interface which completely satisfied to specification. RB-tree of not RB-tree can't be checked with public interface. > This algorithm works very well on small number of pairs (as we see, 4%-10% improvement ), but will it pause huge regression if the number of pairs grows to a great number? I've based my implementation on the following steps: 1. small array is always faster then tree on all operations. 2. If we create Tree of small arrays we will get benifits on tree sizes. And the latest fact is proved by my measurements. I am really want to collect all my data and share it here. But, please, expect some delay in this. > I have a simple idea here, is it possible to just to apply only binary search array when total size of the tree is small (e.g, small than 64) and change it to RB-tree aglorithm(rebuild a RB-Tree) when the size exceed the bar? If you check history of TreeMap you can find that this first (initial) idea was implemented (probably somewhere in August/September 2007 I don't remember exactly when). After that I was woking on expanding thiso idea to all tree sizes. -- Best regards, --- Sergey Kuksenko.
