4

我需要将数据存储在内存中，在内存中我将一个或多个键字符串映射到一个对象，如下所示：

"green", "blue" -> object1
"red", "yellow" -> object2

因此，在 Java 中，数据结构可能会实现：

Map<Set<String>, V>

我需要能够有效地接收对象列表，其中字符串匹配一些布尔标准，例如：

("red" OR "green") AND NOT "blue"

我正在使用 Java，因此理想的解决方案是现成的 Java 库。但是，如果有必要，我愿意从头开始实施一些东西。

有人有想法么？如果可能的话，我宁愿避免内存数据库的开销，我希望速度上可以与 HashMap 相媲美（或至少相同的数量级）。

4

9 回答 9

6

实际上，我喜欢这个问题，所以我本着我之前回答的精神实施了一个完整的解决方案：

http://pastebin.com/6iazSKG9

我猜是一个简单的解决方案，不是线程安全的或其他任何东西，但很有趣并且是一个很好的起点。

编辑：根据要求进行一些详细说明

请参阅单元测试以了解用法。

有两个接口，DataStructure<K,V>和Query<V>。DataStructure 的行为有点像地图（在我的实现中它实际上与内部地图一起使用），但它也提供了可重用和不可变的查询对象，可以像这样组合：

    Query<String> combinedQuery = 
    structure.and(
                    structure.or(
                            structure.search("blue"), 
                            structure.search("red")
                    ),
                    structure.not(
                            structure.search("green")
                    )
    );

（搜索标记为（蓝色或红色）而不是绿色的对象的查询）。这个查询是可重用的，这意味着它的结果会随着后备地图的改变而改变（有点像 iTunes 智能播放列表）。

查询对象已经是线程安全的，但支持映射不是，所以这里还有一些改进的空间。此外，查询可以缓存它们的结果，但这可能意味着必须扩展接口以提供 purge 方法（有点像 Wicket 模型中的 detach 方法），这不会很漂亮。

至于许可：如果有人想要这个代码，我很乐意把它放在 SourceForge 等......

肖恩

于 2010-05-20T15:50:14.967 回答
1

该标准是否适用于位图索引：http ://en.wikipedia.org/wiki/Bitmap_index ？

于 2010-05-20T13:36:52.263 回答
0

我想说最简单的方法是简单地进行递归过滤和切割器，例如在评估X AND Y哪里X已经评估为空集时。

然而，映射需要从标签（例如“红色”或“蓝色”）到对象集。

递归的基本情况（解析原子标签）将是此映射中的简单查找。AND将使用交集，OR使用联合等来实现。

于 2010-05-20T13:34:34.840 回答
0

查看Apache Commons-Collections 项目。他们有很多很棒的东西可供您使用，尤其是用于执行强大的基于集合的逻辑的CollectionUtils类。

例如，如果您的值存储在 HashMap 中（如另一个答案所建议），如下所示：

myMap["green"] -> obj1
myMap["blue"] -> obj1
myMap["red"] -> obj2
myMap["yellow"] -> obj2

然后检索匹配的结果：("red" or "green") and not "blue您可以这样做：

CollectionUtils.disjunction(CollectionUtils.union(myMap.get("red"), myMap.get("green")), myMap.get("blue"))

于 2010-05-20T13:46:44.190 回答
0

您可以将字符串键映射到二进制常量，然后使用位移来生成适当的掩码。

于 2010-05-20T16:00:11.593 回答
0

我真的认为某种类型的数据库解决方案是你最好的选择。SQL 轻松支持通过以下方式查询数据

(X and Y) and not Z
于 2010-05-20T16:08:01.507 回答
0

这将工作太可重用条件/表达式类

于 2010-05-20T16:33:37.487 回答
0

Google Collections SetMultimap看起来像是一种获取底层结构的简单方法，然后将其与Maps静态过滤器相结合以获得您想要的查询行为。

建设会像

smmInstance.put(from1,to1);
smmInstance.put(from1,to2);
smmInstance.put(from2,to3);
smmInstance.put(from3,to1);
smmInstance.put(from1,to3);
//...

然后查询看起来像

valueFilter = //...build predicate
Set<FromType> result = Maps.filterValues(smmInstance.asMap(),valueFilter).keySet()

您可以做任何花哨的构建谓词，但Predicates有一些方法可能足以进行包含/不包含样式查询。

于 2010-05-20T17:36:01.770 回答
0

我没能找到令人满意的解决方案，所以我决定自己制作并将它作为一个开源 (LGPL) 项目发布，在这里找到它。

于 2010-07-15T17:26:38.573 回答