string - 什么数据结构最适合字符串集合的快速查找和内存效率？

Question

在我的程序中，我有一个巨大的字符串列表(非重复)，它们与单词交叉。我想检查这个词是否有效——它的有效性取决于它在列表中的存在。我对许多不同的单词运行此检查，因此速度是我最关心的问题，还有列表存储的内存效率。

所以我的问题是，什么数据结构最适合字符串集合的快速查找和内存效率？

我目前正在使用 BTreeSet，因为它是有序的，并且我认为它可以使搜索更快。另外，由于这些词可能非常相似(“apple”和“app”)，因此我假设基于树的数据结构通过 Vec 存储它们的内存效率更高。

Answer 1

如果您需要精确匹配，那么您应该使用HashSet。它应该比 BTreeSet 更快、更高效。

但是如果您需要更复杂的搜索/匹配功能，例如按公共(public)前缀搜索、区分大小写和不敏感搜索、大量具有大公共(public)前缀的单词等，那么 hashmap 将不太适合。

在这种情况下，您可以使用 trie也称为前缀树。它逐个字符存储单词，从而“压缩”公共(public)前缀，如果您搜索以公共(public)前缀开头的许多单词，这也会显着提高速度。

一个非常基本的实现只是 HashMap 的包装:

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()
    }

但是，如果您想“同时”搜索任何带有前缀的单词，则应该利用递归结构，如 leetcode problem

还有一些实现注意事项:

• 使用更快的哈希函数，因为我们只对单个字节进行哈希处理，而 Rust 中的默认哈希函数非常慢
• 您可以在找到节点后从 trie 中“软删除”节点，以加快后续搜索速度。