Presence and Data Structure - Part III

关于在线好友场景的说明参看前文：在线好友状态列表与数据结构(1)-list

我们再评估一下平衡二叉树在前文场景中的性能。平衡二叉树(Self-balancing binary search tree)是一种将树的深度自动保持最小化的一种数据结构。

1) 红黑树 Red Black Tree
Red-Black Tree是如图所示一种数据结构，它最深的叶子最多是最短的叶子深度的2倍，是通过红色和黑色的控制来达到目的。 它的Insert/Delete/lookup算法复杂度是O(Log n)
Red-Black的插入/删除有非常直观的Applet动画演示
http://gauss.ececs.uc.edu/RedBlack/redblack.html

2) AVL tree
AVL tree也 是一种自平衡的二叉树,和Red-Black Tree非常相似。原理上AVL insert/delete比Red Black tree慢，lookup更快，因此AVL Tree在查找密集型操作中表现更好。由于我们考察的案例是insert/delete密集操作且set比较小，所以就不对AVL tree做性能比较了。

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

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

测试结果
HashMap 20秒
TreeMap 18秒

这和平时理解有点区别，因为一般的Java教材都是说不要直接使用TreeMap,当需要排序时候再用构建好的HashMap传递进去，但在上述测试中，对于数字的key，TreeMap的性能和HashMap大致是一样的,甚至性能更好。

简单小结
对于前文的场景，就是比较各种数据结构之后，还是HashMap领先。对于数字类型的账号，也可考虑使用Red-Black Tree, 即TreeMap

补充说明
Java Collection Framework 其实用来进行各种数据结构原理的性能比较，可能结果不一定100%反应该数据结构原理的优劣，因为Java集合类不是完全照搬按教科书来实现，而是做了很 多实用性及性能的优化。而且Java集合类的开发者是Java界最优秀的两位高手Joshua Bloch及Doug Lea

HashMap 的作者
* @author Doug Lea
* @author Josh Bloch

TreeMap 的作者
* @author Josh Bloch and Doug Lea

另外还有一个多线程下性能更好的 ConcurrentHashMap
* @since 1.5
* @author Doug Lea

尽管这样，我们通常关注是实际环境下使用基于数据结构原理的JDK集合类的性能，所以上述测试对实际生产环境是有借鉴意义的。

参看：
在线好友列表与数据结构(2) - Radix Tree
在线好友状态列表与数据结构(1)-list