自己山寨了一个红黑树，拿来和 Dictionary 作性能对比，结果发现速度慢很多（N < 1,000,000 时，接近一个数量级）。山寨的代码未经优化，和 BCL 里面的代码拼速度的确没啥意义。该红黑树的读写速度严格按照 Log(N) 退化，这说明我的实现和测试方法没有大的问题。而 Dictionary 虽然性能也在退化，但是却要平缓得多。红黑树唯一的优势是内存占用较低，基本上是 Dictionary 的一半。

    不过，从理论上很容易证明红黑树在性能上的劣势。红黑树是一个有序的结构，为了保持其有序的结构，自然需要付出更高的代价（从这个角度而言，红黑树和 Dictionary 的差别，正如基于 Heap 的 PriorityQueue 和 SortedList 的区别一样，前者只维护一个偏序）。Dictionary 中间的数据是无序的（因此 Hash 被某些人翻译成“杂凑”），如果不快一点实在对不起它消耗的内存（空间换速度）。此外，Dictionary 的性能与 hashcode 的质量有很大的关系，因此在存在 Hash Collision 的情况下性能会退化；Dictionary 不能像红黑树那样保证最坏情况下具有 log(N) 的性能，从而在更普遍的场合提供更高的性能和更好的 Scalability。

    其实，在大多数场合下，红黑树和 Dictionary 并不具备可比性——Dictionary 的应用场合要广很多。大概，这就是 .NET BCL 不提供红黑树（或者 AVL 树）的理由吧。更正：BCL 中的 TreeSet 就是一个非标准版本的红黑树，并且提供了 TreeDictionary 作为关联数组。神奇的是，在我的简单 Benchmark 下面，我的山寨版本读速度慢，写速度快，差距都低于 20%。至于内存占用，还是山寨版本用得少（因为简陋）。

    最后，再谈谈红黑树的一些鲜为人知的优点：红黑树可以通过 path copy 在操作时保留原有的树结构，其空间开销为 log(N)；红黑树可以通过 Sleator, Tarjan 的方法构造 persistent 版本，即保留所有历史版本，一次操作的空间开销仅为常数。而这些，都是 Dictionary 等基于 hash 的数据结构所不具备的优良特性。

    但是，在下面这篇文章中，作者认为 Java 的 TreeMap 和 HashMap 性能相当。这是否说明 CLR 的 Dictionary 要比 Java 的 HashMap 效率要高呢？我表示谨慎的怀疑。水木上的一位网友认为，这是测试者的使用不当，HashMap 的性能主要被 resize 所限制（相信很多人受过 StringA = StringA + StringB 的罪吧）。

性能比较

我们仍然比较Red-Black Tree同Hash table的性能区别。Red-Black Tree使用Java的TreeMap来实现；Hash Table使用HashMap来实现。

5千万数据, 每50个为一组，插入50个8位长的随机数，在达到30个之后再每次删除一个元素。

测试结果

HashMap 20秒

TreeMap 18秒

源文档 <http://hi.baidu.com/jabber/blog/item/46ddc3ef383cfa30acafd5c8.html>