用户名自动完成算法

本贴最后更新于 2922 天前,其中的信息可能已经时过境迁

概述

发帖、回帖有时需要 @ 用户,这个时候需要用自动完成来辅助用户输入。

总的来说有两种思路:

  1. 纯前端:自动完成候选数据在前端渲染时就给定,比如回帖时 @ 本贴的参与者,参与者相对与较少,是可以在帖子渲染时就填充好的
  2. 后端交互:发送请求到后端,由后端在整个用户列表中做匹配

社区目前选择的是第二种思路。

关键点

后端在进行用户名匹配时需要到整个用户列表中进行搜索,如果直接查库性能上肯定是不能接受的,所以这个时候引入一个缓存来解决性能问题。

因为需求比较简单,不涉及到写数据和一致性,所以也没必要引入分布式缓存这样高大上的产品,直接从数据库用户表中将所有用户名捞出放后放内存,并定时重捞(新用户注册、用户名变更等)。

目前感觉还是蛮好用的,但是有个问题一直没解决好:用户名匹配算法。

整体流程

用户输入 @ 并打出 A 时将发送一个自动完成请求到后端,后端接收到这个查询前缀为 A 的用户名时在缓存的用户名列表(按字母排序)中进行二分查找,然后选择命中条目和后面 4 个条目:

public List<JSONObject> getUserNamesByPrefix(final String namePrefix) {
    final List<JSONObject> ret = new ArrayList<JSONObject>();

    final JSONObject nameToSearch = new JSONObject();
    nameToSearch.put(User.USER_NAME, namePrefix);

    // 二分查找,userNames 是缓存好的用户名列表
    final int index = Collections.binarySearch(userNames, nameToSearch, new Comparator<JSONObject>() {
        @Override
        public int compare(final JSONObject u1, final JSONObject u2) {
            final String u1Name = u1.optString(User.USER_NAME).toLowerCase();
            final String inputName = u2.optString(User.USER_NAME).toLowerCase();

            if (u1Name.startsWith(inputName)) {
                return 0;
            } else {
                return namePrefix.compareTo(u1Name);
            }
        }
    });

    if (index >= 0) {
        final int max = index + 5 <= userNames.size() - 1 ? index + 5 : userNames.size() - 1;

        for (int i = index; i < max; i++) {
            ret.add(userNames.get(i));
        }
    }

    return ret;
}

至此,@ 时用户名自动完成的基本原理阐述完毕,下面分享一个细节。

前缀匹配

在进行二分查找时,上面的代码用了 startsWith 进行前缀匹配,乍一看感觉没错,因为自动完成时用户就是按照从左到右的输入顺序进行。

实际上,漏了一个非常重要的前提。前面提到过用户名列表是按字母排序的,但这还不够,还需要再按长度再排序,否则按前缀匹配就不可能准确。

总结

分享完了,大家还有什么要了解的请跟帖,非常欢迎任何改进!

打赏 10 积分后可见
10 积分 • 4 打赏

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • blague 1

    我觉得可以前端加载一点:

    1. 参与帖子的人
    2. 帖子参与过帖子里关键词的
    3. 回帖人的圈子里的人
  • 其他回帖
  • flhuoshan

    @88250 覆盖后的 Collections.binarySearch 要是能返回一组命中 index 而不是一个 index,这个问题不就没有了

  • R

    感觉用户名不要只限于英文,比如一些工作室想在论坛注册交易,用户名是一个很好的品牌展示。

  • 88250

    @ouzhouyou 嗯,是存在泄漏账号的风险,后续优化将考虑你的建议

    @DevAPI @kevinle 目前达不到这个用户量级,暂时没有性能问题

  • 查看全部回帖