Presence and Data Structure - Part I

在一个典型的IM Server上，每个登录的用户都需要维护一份自己在线用户列表，需要频繁进行以下操作

iterate
循环与遍历，很多操作需要调用iterator

insert/delete
由于在线的好友随时会产生上下线的变化，所以需要增加或删除列表的内容。

lookup
同时由于列表的元素需要保持唯一性，insert时候也需要查找已有的元素是否存在。

同时还具有以下一些特性

长度
在线的好友列表不会太长，通常都是几十个。

规律
假如系统使用的是基于号码的数字账号，这些数字通常有一定程度集中性，比如很多系统活跃用户集中在最新的号码段。


对于一个这样的需求，我尝试去了解一下需要知道在已有的数据结构中哪一种数据结构是最适合的。

在以下及后续的评估中，主要是考虑时间复杂度，即程序性能，对空间复杂度关注较少。

1) Array/List

对于这样一个列表，最简单的做法就是用数组或list实现。这就是往往现在大部分程序员不懂数据结构也能写出正常执行的程序。`

但是，Array/List都存在查找慢的问题，频繁的增删性能很慢。

2) Linked List
Linked List解决了增删性能问题，是一种最常采用的做法，如下代码片断。但仍然存在查找慢的问题。

/**
 * remove a jid from a list, returning the new list
 *
 * @param id the JabberID that should be removed
 * @param ids the list of JabberIDs
 * @return the new list
 */
static jid _mod_presence_whack(jid id, jid ids) {
       jid curr;

       if (id == NULL || ids == NULL)
       return NULL;

       /* check first */
       if (jid_cmp(id,ids) == 0)
       return ids->next;

       /* check through the list, stopping at the previous list entry to a matching one */
       for (curr = ids; curr != NULL; curr = curr->next) {
       if (jid_cmp(curr->next, id) == 0)
           break;
       }

       /* clip it out if found */
       if(curr != NULL)
           curr->next = curr->next->next;

       return ids;
}

(Jabberd 1.4 更新好友列表的代码, mod_presence.cc)

(待续: 在线好友列表与数据结构(2) - Radix Tree)