java - 我需要一种快速的方法来搜索子字符串

Question

我正在重新设计一个框架，我需要一个快速算法来搜索字符串集合中的子字符串。

简而言之，当触发子关联的任何事件时，类都会收到警报。

事件包含一个路径，该路径是从当前类到触发的事件(通常是属性更改)的路径。

每个类都具有到集合中加载的路径的静态绑定(bind)。 绑定(bind)由实际路径和绑定(bind)到所述路径的一组属性名称组成。

当类接收事件时，它需要检查是否有任何属性名称绑定(bind)到事件的路径，并在任何具有绑定(bind)的属性上触发某些内容。

现在，我只是在寻找存储这些绑定(bind)的最佳集合类型以及在静态绑定(bind)中搜索事件路径的最佳方法。

现在我的实现非常基本。我正在使用 HashMap，键是可能的路径，而值是绑定(bind)到路径的一组属性。

我正在循环遍历键集，并将startsWith 与事件的路径一起使用。 (事件的路径必须是从索引 0 开始的绑定(bind)的子字符串)

例如，路径如下所示:“association1.association2.propertyInAssociation2”或“association1.association2.association3”

绑定(bind)映射看起来是这样的(实际上并没有像这样初始化，这只是一个示例):

HashMap<String, Set<String>> bindings = new HashMap<>();
{
    bindings.put("association1.association2.propertyInAssociation2", new HashSet<>());
    bindings.get("association1.association2.propertyInAssociation2").add("property1");
    bindings.get("association1.association2.propertyInAssociation2").add("property2");
    bindings.get("association1.association2.propertyInAssociation2").add("property3");

    bindings.put("association1.association2.association3.propertyInAssociation3", new HashSet<>());
    bindings.get("association1.association2.association3.propertyInAssociation3").add("property4");
    bindings.get("association1.association2.association3.propertyInAssociation3").add("property5");
    bindings.get("association1.association2.association3.propertyInAssociation3").add("property6");
    bindings.get("association1.association2.association3.propertyInAssociation3").add("property7");
}

因此，对于具有这些绑定(bind)的类，接收具有“association1.association2.association3.propertyInAssociation3”或“association1.association2.association3”等路径的事件 两者都需要在 property4、property5、property6 和 property7 上触发某些内容。

就像我说的，我需要的是搜索哪些属性(如果有)绑定(bind)到事件路径的最有效方法。

我使用 Java 8，所以我不介意使用 lambda 或任何可用的东西。 将绑定(bind)重新设计为任何其他格式的字符串集合也不是不可能的，如果有帮助的话。

非常感谢!

Answer 1

既然你这么说了

I am looping through the keyset and I use startsWith with the event's path. (The event's path needs to be a substring of a binding starting from index 0)

您应该考虑使用不同的数据结构。 HashMap 提供高效的全键查找，但对于部分键查找没有多大帮助。您可以考虑使用 SortedMap，例如 TreeMap。对于 String 键，SortedMap.tailMap() 或 SortedMap.subMap() 将帮助您直接导航到您要查找的键，如果他们在场的话。

当然，插入、删除和全键查找在 TreeMap 中的效率低于在 HashMap 中(平均而言)；这是对提高关键子串搜索效率的权衡。