Presence and Data Structure - Part II

1) Hash table
在讨论Radix Tree之前先看下 hash table, 它是目前大家都很熟悉使用非常广泛的一种数据结构。它的算法复杂度是O(1)

/** 
 * Roster item cache - table: key jabberid string; value roster item.
 */  
protected ConcurrentHashMap<String, RosterItem> rosterItems = 
     new ConcurrentHashMap<String, RosterItem>();

(Openfire class org.jivesoftware.openfire.roster.Roster)

2) Radix Tree

(图片来源：Wikipedia)

Radix Tree 是如图所示一种数据结构，对于小量范围有一定相似度的字符串具有较高的insert/delete/lookup性能。它的这几个操作算法复杂度是 O(k), k指key长度。与hash table相比，虽然O(k) > O(1)。但是 hash table的O(1)没有考虑计算hash所需时间及hash冲突的时间
。因此在某些情况下Radix Tree性能比hash table好也不足为奇。

性能比较

我们使用Google code中的 Radix Tree Java Library实现,
hash table使用Java Collection中的HashMap

1千万数据，每50个为一组，插入50个5位长的随机数，在达到30个之后再每次删除一个元素。考虑到实际应用中号码段可能会趋于集中，而且为了更好的测试Radix Tree，测试再在所有的号码前加上固定前缀1000。

执行时间：
HashMap 2秒
RadixTree 20秒

虽然构造的测试场景有利于Radix Tree, 但是测试结果是Radix Tree完全不适合此场景。而且还有不足的是上述Radix Tree库没有实现iterator()接口。

参看：
在线好友状态列表与数据结构(1)-list
在线好友列表与数据结构(3) - 平衡二叉树