Firebase集成Trie搜索：已搜索文本无结果问题排查

问题场景 #

开发Android应用时，采用Firebase Database结合Trie数据结构实现用户名实时搜索，出现重复查询历史文本无结果的异常。

现有实现代码 #

UserTrie类 #

class TrieNode { 
    Map<Character, TrieNode> children;
    List<User> users;
    boolean isEndOfWord;
    
    TrieNode() {
        users = new ArrayList<>();
        children = new HashMap<>();
        isEndOfWord = false;
    } 
}

public class UserTrie { 
    private TrieNode root;
    
    public UserTrie() {
        root = new TrieNode();
    }
    
    public void insert(String word, User user) {
        if (word.isEmpty()) return;
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            if (!current.children.containsKey(ch)) {
                current.children.put(ch, new TrieNode());
            }
            current = current.children.get(ch);
            current.users.add(user);
        }
        current.isEndOfWord = true;
    }
    
    public List<User> search(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            if (!current.children.containsKey(ch)) {
                break;
            }
            current = current.children.get(ch);
        }
        return current.users;
    }
}

Firebase集成代码 #

DatabaseReference reference = FirebaseDatabase.getInstance().getReference();
Query query = reference.child(getString(R.string.user));
query.addListenerForSingleValueEvent(new ValueEventListener() {
    @Override
    public void onDataChange(DataSnapshot dataSnapshot) {
        for(DataSnapshot singleSnapshot :  dataSnapshot.getChildren()){

            try {
                User user = singleSnapshot.getValue(User.class);
                if (user != null) {
                    userTrie.insert(user.getName(), user);
                }
            } catch (Exception e) {
                Log.e(TAG, "Failed to convert value to User: " + e.getMessage());
            }
        }

        mSearchParam.addTextChangedListener(new TextWatcher() {
            @Override
            public void beforeTextChanged(CharSequence s, int start, int count, int after) {

            }

            @Override
            public void onTextChanged(CharSequence s, int start, int before, int count) {
                mUserList.clear();
                String text = mSearchParam.getText().toString();

                if (text != null && !text.isEmpty() && text.length() > 0) {
                    mUserList = userTrie.search(text);
                    //update the users list view
                    updateUsersList();
                }
            }

            @Override
            public void afterTextChanged(Editable s) {
            }
        });
    }

    @Override
    public void onCancelled(DatabaseError databaseError) {

    }
});

Firebase数据库结构 #

{
  "users": {
    "0pnms": {
      "detail": "",
      "name": "name1"
    },
    "0qx6l": {
      "detail": "",
      "name": "name2"
    },
    "1WgTv": {
      "detail": "",
      "name": "name3"
    }
  }
}

异常表现 #

首次搜索任意文本结果正常，但后续再次搜索已查询过的文本（如先搜"abc"，再搜"a"、"ab"）时无结果返回。尝试过将List设为final、搜索后重置current到root，均未解决问题。

问题原因与解决方案 #

核心原因 #

onTextChanged方法中，执行mUserList = userTrie.search(text)时，直接将mUserList的引用替换为Trie节点内部存储的users列表。后续调用mUserList.clear()时，会直接清空Trie节点中保存的原始用户数据，导致再次搜索对应前缀时，节点的users列表已为空。

修复方案 #

1. 修改onTextChanged逻辑，避免替换mUserList的引用，改为将搜索结果添加到现有列表中：

@Override
public void onTextChanged(CharSequence s, int start, int before, int count) {
    mUserList.clear();
    String text = mSearchParam.getText().toString();

    if (text != null && !text.isEmpty() && text.length() > 0) {
        List<User> searchResult = userTrie.search(text);
        mUserList.addAll(searchResult);
        updateUsersList();
    }
}

2. 为防止外部代码意外修改Trie内部数据，修改UserTrie的search方法，返回不可修改的列表副本：

public List<User> search(String word) {
    TrieNode current = root;
    for (char ch : word.toCharArray()) {
        if (!current.children.containsKey(ch)) {
            break;
        }
        current = current.children.get(ch);
    }
    return Collections.unmodifiableList(current.users);
}

内容的提问来源于stack exchange，提问作者Ekagra Sinha