java - 在更大的字符串集合中查找大量的字符串集合

Question

我有一组要过滤的字符串。他们将采用这种模式:

xxx_xxx_xxx_xxx

所以总是由三个下划线分隔的字母或数字序列。每个字符串的最大长度为 60 个字符。我的 Collection 中可能有几百万个。

我可以使用什么数据结构来有效地做这样的事情:

Get all strings starts with: "abc_123_456"

Get all strings starts with: "def_999_888"

etc..

例如，我可以这样做:

List<String> matched = new ArrayList<String>();
for (String it : strings) {
    if (it.startsWith(match)) {
        matched.add(it);
    }
}

但如果我的集合有数百万个字符串，那将需要很长时间，如果匹配字符串的数量也很高，则更糟。

高级问题是我想为我正在编写的应用程序回答以下问题:“我的哪些 friend 为产品 B 推荐了产品 A？”。我可以将此信息存储在 sql 表中并运行以下语句:

select recommender from recs where username='me' and prodIdA='a' and prodIdB='b';

我很好奇，如果使用像我上面那样的编码扁平字符串，java/C/C++ 中的自定义内容是否可以运行得更快:

myusername_prodIdA_prodIdB_recommenderusername

想法是您可以对整个编码字符串集合执行 starts-with 操作以获得答案。

我知道尝试实现像这样的自定义解决方案很可能在生产环境中不可用，所以一些 sql 数据库会更好，但只是好奇，

谢谢

Answer 1

要在 Java 中执行此操作，您可以使用 Trie结构。

话虽如此，我认为这不是一个好主意。将“几百万”条记录转储到内存中并不总是有效。

这就是数据库的用途；通过正确的设计和适当的索引，您可以单独使用数据库获得非常好的性能。