回调接口
至于收到其他客户端发来的消息时则是利用之前预留的消息回调接口来写入日志。
收到消息后会执行自定义的回调接口。
于是在这个回调方法中实现写入逻辑即可,当后续还有其他的消息处理逻辑时也能在这里直接添加。
当处理逻辑增多时最好是改为责任链模式,更加清晰易维护。
查找算法
接下来是本文着重要讨论的一个查找算法,准确的说是一个前缀模糊匹配的算法。
实现的效果如下:
使用命令 :qu prefix
可以按照前缀的方式搜索用户信息。
当然在命令行中其实意义不大,但是在移动端中确是比较有用的。类似于微信按照用户名匹配:
因为后期打算出一个移动端 APP,所以就先把这个功能实现了。
从效果也看得出来:就是按照输入的前缀匹配字符串(目前只支持英文)。
在没有任何限制的条件下最快、最简单的实现方式可以直接把所有的字符串存放在一个容器中 (List、Set),查询时则挨个遍历;利用 String.startsWith("prefix")
进行匹配。
但这样会有几个问题:
- 存储资源比较浪费,不管是 list 还是 Set 都会有额外的损耗。
- 查询效率较低,需要遍历集合后再遍历字符串的
char
数组
(String.startsWith
的实现方式)。
字典树
基于以上的问题我们可以考虑下:
假设我需要存放 java,javascript,jsp,php
这些字符串时在 ArrayList 中会怎么存放?
很明显,会是这样完整的存放在一个数组中;同时这个数组还可能存在浪费,没有全部使用完。
但其实仔细观察这些数据会发现有一些共同特点,比如 java,javascript
有共同的前缀 java
;和 jsp
有共同的前缀 j
。
那是否可以把这些前缀利用起来呢?这样就可以少存储一份。
比如写入 java,javascript
这两个字符串时存放的结构如下:
当再存入一个 jsp
时:
最后再存入 jsf
时:
相信大家应该已经看明白了,按照这样的存储方式可以节省很多内存,同时查询效率也比较高。
比如查询以 jav
开头的数据,只需要从头结点 j
开始往下查询,最后会查询到 ava
以及 script
这两个个结点,所以整个查询路径所经历的字符拼起来就是查询到的结果java+javascript
。
如果以 b
开头进行查询,那第一步就会直接返回,这样比在 list
中的效率高很多。
但这个图还不完善,因为不知道查询到啥时候算是匹配到了一个之前写入的字符串。
比如在上图中怎么知道
j+ava
是一个我们之前写入的java
这个字符呢。
因此我们需要对这种是一个完整字符串的数据打上一个标记:
比如这样,我们将 ava、script、p、f
这几个节点都换一个颜色表示。表明查询到这个字符时就算是匹配到了一个结果。
而查到 s
这个字符颜色不对,代表还需要继续往下查。
比如输入关键字 js
进行匹配时,当它的查询路径走到 s
这里时判断到 s 的颜色不对,所以不会把 js
作为一个匹配结果。而是继续往下查,发现有两个子节点 p、f 颜色都正确,于是把查询的路径 jsp
和 jsf
都作为一个匹配结果。
而只输入 j,则会把下面所有有色的字符拼起来作为结果集合。
这其实就一个典型的字典树。