Rust 什么数据 struct 最适合对字符串集合进行快速查找和内存效率

如果你需要exact匹配，那么你应该使用HashSet.它应该比BTreeSet更快、更高效.

但如果您需要更复杂的搜索/匹配功能，例如按公共前缀搜索，则区分大小写和；不敏感的搜索，大量带有大公共前缀的单词，等等，那么hashmap就不适合了.

在这种情况下，你可以使用trie也被称为prefix tree.它一个字符一个字符地存储单词，从而"压缩"公共前缀，如果搜索以公共前缀开头的many个单词，这也会大大加快搜索速度.

一个非常基本的实现只是散列映射的包装器:

struct Node {
    ptr: HashMap<u8, Node>,

    // you can also use a boolean to mark the end of word, but then you would need additional code to rebuild it from the bytes 
    word: Option<String>,
}

通过递归地将下一个单词字符添加到树中，或使用性能更高的迭代方法，可以将一个单词添加到树中:

   pub fn insert(&mut self, word: String) {
        let w = word.as_bytes();

        let mut node = self;
        for ch in w.iter().copied() {
            node = node.ptr.entry(ch).or_default()
        }

        // attach the word
        node.word = Some(word);
    }

基本的搜索也非常简单:

    fn find(&self, word: String) -> Option<String> {
        let word = word.as_bytes()
        let mut node = self;

        for ch in word.iter() {
            match node.ptr.get(ch) {
                Some(link) => node = link,
                None => return None,
            }
        }

        node.word.clone()
    }

但是，如果你想利用"同时"搜索任何带有前缀的单词，你应该利用递归 struct ，如图leetcode problem所示

还有一些实施方面的考虑:

• 使用更快的散列函数，因为我们只对单个字节进行散列，而rust中的默认散列函数非常慢
• 找到 node 后，可以从trie中"软删除" node ，以加快后续搜索.

您可以在提供的github链接中找到此类示例