Java Collection的多个索引 - 最基本的解决方案？

Question

我正在寻找在Java Collection上创建多个索引的最基本的解决方案.

所需功能:

• 删除值后,必须删除与该值关联的所有索引条目.
• 索引查找必须比线性搜索更快(至少与TreeMap一样快).

边条件:

• 不依赖于大型(如Lucene)库.没有罕见或未经过良好测试的库.没有数据库.
• 像Apache Commons Collections这样的库可以.
• 更好的是,如果单独使用JavaSE(6.0).
• 编辑:没有自我实现的解决方案(感谢答案暗示这一点 - 最好让他们在这里完整,但我已经有一个非常类似Jay的解决方案)每当有几个人发现,他们实现了同样的事情,这应该成为一些公共图书馆的一部分.

当然,我可以写一个自己管理多个地图的课程(这并不难,但感觉就像重新发明轮子一样).所以我想知道,如果没有它可以完成 - 同时仍然得到类似于使用单个索引java.util.Map的简单用法.

谢谢,克里斯

更新

它看起来好像我们没有找到任何东西.我喜欢你所有的答案 - 自我开发的版本,数据库类库的链接.

这就是我真正想要的:在(a)Apache Commons Collections或(b)Google Collections/Guava中使用这些功能.或许是一个非常好的选择.

其他人也会错过这些库中的这个功能吗？他们提供各种各样的东西,如MultiMaps,MulitKeyMaps,BidiMaps,......我觉得,它很适合这些库 - 它可以调用MultiIndexMap.你怎么看？

Answer 1

每个指数基本上都是单独的Map.您可以(也可能应该)在管理搜索,索引,更新和删除的类后面抽象它.一般来说,这并不难做到这一点.但是,虽然它可以很容易地从Java Collections类构建,但是没有标准的开箱即用类.

Answer 2

看看CQEngine(集合查询引擎),它完全适合这种要求,基于一个IndexedCollection.

另请参阅相关问题如何在Java中查询对象集合(Criteria/SQL-like)？了解更多背景资料

Answer 3

我的第一个想法是为被索引的东西创建一个类,然后创建多个HashMap来保存索引,并将相同的对象添加到每个HashMaps中.对于添加,您只需将相同的对象添加到每个HashMap.删除将需要搜索每个HashMap以获取对目标对象的引用.如果删除需要很快,您可能希望为每个索引创建两个HashMaps:一个用于索引到值,另一个用于值到索引.当然,我会用一个明确定义的界面包装你在课堂上做的任何事情.

似乎这不会很难.如果您事先知道索引的数量和类型以及窗口小部件的类,那将非常简单,例如:

public class MultiIndex
{
  HashMap<String,Widget> index1=new HashMap<String,Widget>();
  HashMap<String,Widget> index2=new HashMap<String,Widget>();
  HashMap<Integer,Widget> index3=new HashMap<Integer,Widget>();

  public void add(String index1Value, String index2Value, Integer index3Value, Widget widget)
  {
    index1.put(index1Value, widget);
    index2.put(index2Value, widget);
    index3.put(index3Value, widget);
  }
  public void delete(Widget widget)
  {
    Iterator i=index1.keySet().iterator(); 
    while (i.hasNext())
    {
      String index1Value=(String)i.next();
      Widget gotWidget=(Widget) index1.get(index1Value);
      if (gotWidget.equals(widget))
        i.remove();
    }
    ... similarly for other indexes ...
  }
  public Widget getByIndex1(String index1Value)
  {
    return index1.get(index1Value);
  }
  ... similarly for other indexes ...

  }
}

如果你想使它成为通用的并接受任何对象,拥有可变数量和类型的索引等,那就有点复杂了,但并不多.

Answer 4

您有很多非常紧缩的要求似乎对您的需求非常特别.你说的大多数事情都不可行是因为很多人都有相同的确切需求,基本上定义了一个基本的数据库引擎.这就是为什么它们是"大型"库.你说"没有数据库",但其核心是每个索引系统都是术语和文档的"数据库".我认为Collection是一个"数据库".我想说看看Space4J.

我想说如果你找不到你想要的东西,可以在GitHub上开始一个项目,然后自己编写代码并分享结果.

Answer 5

您需要检查Boon。:)

http://rick-hightower.blogspot.com/2013/11/what-if-java-collections-and-java.html

您可以添加n个搜索索引和查找索引。它还允许您有效地查询原始属性。

这是来自Wiki的示例（我是作者）。

  repoBuilder.primaryKey("ssn")
          .searchIndex("firstName").searchIndex("lastName")
          .searchIndex("salary").searchIndex("empNum", true)
          .usePropertyForAccess(true);

您可以通过提供true标志作为searchIndex的第二个参数来覆盖它。

注意empNum是可搜索的唯一索引。

如果在运行时很容易查询一组复杂的Java对象怎么办？如果有一个API使您的对象索引（实际上只是TreeMaps和HashMaps）保持同步，该怎么办？好吧，您将获得Boon的数据仓库。本文介绍了如何使用Boon的数据仓库实用程序来查询Java对象。这是第一部分。可以有很多很多部分。:) Boon的数据仓库使对集合进行基于索引的查询变得容易得多。为什么要通过Boon数据仓库

通过Boon的数据仓库，至少在查询集合时，您可以将Java集合更像是一个数据库。Boon的数据存储库不是内存数据库，并且不能替代将对象安排到为您的应用程序优化的数据结构中。如果您想花费时间为客户提供价值，构建对象和类并为数据结构使用Collections API，那么DataRepo就是您的理想之选。这并不排除要出版Knuth书籍并提出优化的数据结构。它只是有助于使平凡的事情变得容易，因此您可以花费时间使困难的事情变为可能。出于需要而生

这个项目是出于需要。我正在做一个计划将内存中的大量域对象存储在内存中以提高速度的项目，有人问了一个我忽略的重要问题。我们将如何查询这些数据。我的回答是，我们将使用Collections API和Streaming API。然后，我尝试执行此操作...嗯...我也对大型数据集使用JDK 8流API感到厌倦，而且速度很慢。（Boon的数据仓库可与JDK7和JDK8一起使用）。这是一个线性搜索/过滤器。这是设计使然，但是对于我正在做的事情，它没有用。我需要索引来支持任意查询。Boon的数据存储库增强了流API。

Boon的数据仓库并不努力替换JDK 8流API，实际上，它可以很好地工作。Boon的数据仓库可让您创建索引集合。索引可以是任何值（可插入）。目前，Boon的数据存储索引基于ConcurrentHashMap和ConcurrentSkipListMap。通过设计，Boon的数据存储库可与标准收集库一起使用。没有计划创建一组自定义集合。如果有人愿意，可以插入番石榴，并发树或Trove。它为此提供了简化的API。它允许线性搜索以完成感，但是我建议主要将其用于索引，然后将流API用于其余部分（以确保类型安全和速度）。

先一步一步潜入巅峰

假设您有一个创建200,000个员工对象的方法，如下所示：

 List<Employee> employees = TestHelper.createMetricTonOfEmployees(200_000);

所以现在我们有200,000名员工。让我们搜索它们...

首先将雇员包装在可搜索的查询中：

   employees = query(employees);

现在搜索：

  List<Employee> results = query(employees, eq("firstName", firstName));

那么上述内容与流API的主要区别是什么？

  employees.stream().filter(emp -> emp.getFirstName().equals(firstName)

使用Boon的DataRepo大约快20,000％！HashMaps和TreeMaps的强大功能。:)有一个看起来像您的内置集合的API。还有一个看起来更像DAO对象或Repo对象的API。

使用Repo / DAO对象的简单查询如下所示：

  List<Employee> employees = repo.query(eq("firstName", "Diana"));

涉及更多的查询如下所示：

  List<Employee> employees = repo.query(
      and(eq("firstName", "Diana"), eq("lastName", "Smith"), eq("ssn", "21785999")));

或这个：

  List<Employee> employees = repo.query(
      and(startsWith("firstName", "Bob"), eq("lastName", "Smith"), lte("salary", 200_000),
              gte("salary", 190_000)));

甚至这个：

  List<Employee> employees = repo.query(
      and(startsWith("firstName", "Bob"), eq("lastName", "Smith"), between("salary", 190_000, 200_000)));

或者，如果您想使用JDK 8流API，则可以使用它而不是针对它：

  int sum = repo.query(eq("lastName", "Smith")).stream().filter(emp -> emp.getSalary()>50_000)
      .mapToInt(b -> b.getSalary())
      .sum();

如果员工人数很多，以上方法会更快。这将缩小以史密斯名字开头且年薪超过50,000的员工的范围。假设您有100,000名员工，而只有50名名为Smith的员工，那么现在您可以通过使用索引将其迅速缩小到50名，从而有效地从100,000名员工中抽出50名员工，然后我们仅对50名而不是整个100,000名进行过滤。

这是从线性搜索的数据仓库与以纳秒为单位的索引搜索进行的基准测试：

Name index  Time 218 
Name linear  Time 3709120 
Name index  Time 213 
Name linear  Time 3606171 
Name index  Time 219 
Name linear  Time 3528839

最近有人对我说：“但是，使用流式API，您可以并行运行过滤器。”

让我们看看数学如何成立：

3,528,839 / 16 threads vs. 219

201,802 vs. 219 (nano-seconds).

索引获胜，但这是一张照片。不！:)

它只快了9,500％，而不是快40,000％。很近.....

我添加了更多功能。它们大量使用索引。:)

repo.updateByFilter（values（value（“ firstName”，“ Di”））和（eq（“ firstName”，“ Diana”），eq（“ lastName”，“ Smith”），eq（“ ssn”，“ 21785999 “）））;

以上将等同于

更新员工e SET e.firstName ='Di'在e.firstName ='Diana'和e.lastName ='Smith'和e.ssn ='21785999'

这使您可以一次在多个记录上设置多个字段，以便在进行批量更新时使用。

所有基本类型都有重载的方法，因此，如果您需要一个值来更新从过滤器返回的各项：

  repo.updateByFilter("firstName", "Di",
          and( eq("firstName", "Diana"),
          eq("lastName", "Smith"),
                  eq("ssn", "21785999") ) );

这是一些基本的选择功能：

  List <Map<String, Object>> list =
     repo.query(selects(select("firstName")), eq("lastName", "Hightower"));

您可以选择任意多个。您还可以将列表重新排序：

  List <Map<String, Object>> list =
     repo.sortedQuery("firstName",selects(select("firstName")),
       eq("lastName", "Hightower"));

您可以选择相关属性的属性（例如，employee.department.name）。

  List <Map<String, Object>> list = repo.query(
          selects(select("department", "name")),
          eq("lastName", "Hightower"));

  assertEquals("engineering", list.get(0).get("department.name"));

上面将尝试使用类的字段。如果要使用实际属性（emp.getFoo（）与emp.foo），则需要使用selectPropertyPath。

  List <Map<String, Object>> list = repo.query(
          selects(selectPropPath("department", "name")),
          eq("lastName", "Hightower"));

请注意，select（“ department”，“ name”）的速度比selectPropPath（“ department”，“ name”）的速度要快得多，这可能会造成紧密的循环。

默认情况下，所有搜索索引和查找索引都允许重复（主键索引除外）。

  repoBuilder.primaryKey("ssn")
          .searchIndex("firstName").searchIndex("lastName")
          .searchIndex("salary").searchIndex("empNum", true)
          .usePropertyForAccess(true);

您可以通过提供true标志作为searchIndex的第二个参数来覆盖它。

注意empNum是可搜索的唯一索引。

如果您愿意或需要，甚至可以将简单的搜索返回为地图：

  List<Map<String, Object>> employees = repo.queryAsMaps(eq("firstName", "Diana"));

我不确定这是功能还是功能缺陷。我的想法是，一旦处理数据，就需要以一种不会将数据使用者与实际API绑定在一起的方式来呈现数据。拥有String /基本类型的映射似乎是实现此目的的一种方法。请注意，映射到对象的转换深入如下：

  System.out.println(employees.get(0).get("department"));

产量：

{class=Department, name=engineering}

这对于调试和临时查询工具很有用。我正在考虑添加支持以轻松转换为JSON字符串。

添加了查询集合属性的功能。这应该与深度嵌套的集合和数组一起使用。再读一遍，因为它是实施的真正MF！

  List <Map<String, Object>> list = repo.query(
          selects(select("tags", "metas", "metas2", "metas3", "name3")),
          eq("lastName", "Hightower"));

  print("list", list);

  assertEquals("3tag1", idx(list.get(0).get("tags.metas.metas2.metas3.name3"), 0));

上面的打印看起来像这样：

list [{tags.metas.metas2.metas3.name3=[3tag1, 3tag2, 3tag3,
3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3,
3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3,
3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3,
3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3,
3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3,
3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3,
3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3,
3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3,
3tag1, 3tag2, 3tag3, 3tag1, 3tag2, 3tag3]},
...

我创建了几个关系类来对此进行测试：

public class Employee {
List <Tag> tags = new ArrayList<>();
{
    tags.add(new Tag("tag1"));
    tags.add(new Tag("tag2"));
    tags.add(new Tag("tag3"));

}
...
public class Tag {
...
List<Meta> metas = new ArrayList<>();
{
    metas.add(new Meta("mtag1"));
    metas.add(new Meta("mtag2"));
    metas.add(new Meta("mtag3"));

}

}
public class Meta {
 ...
   List<Meta2> metas2 = new ArrayList<>();
   {
       metas2.add(new Meta2("2tag1"));
       metas2.add(new Meta2("2tag2"));
       metas2.add(new Meta2("2tag3"));

   }

}

...
public class Meta2 {



List<Meta3> metas3 = new ArrayList<>();
{
    metas3.add(new Meta3("3tag1"));
    metas3.add(new Meta3("3tag2"));
    metas3.add(new Meta3("3tag3"));

}
public class Meta3 {

...

您还可以按类型搜索：

  List<Employee> results = sortedQuery(queryableList, "firstName", typeOf("SalesEmployee"));

  assertEquals(1, results.size());
  assertEquals("SalesEmployee", results.get(0).getClass().getSimpleName());

上面找到所有具有简单类名SalesEmployee的雇员。它也可以使用完整的类名，如：

  List<Employee> results = sortedQuery(queryableList, "firstName", typeOf("SalesEmployee"));

  assertEquals(1, results.size());
  assertEquals("SalesEmployee", results.get(0).getClass().getSimpleName());

您也可以按实际类别进行搜索：

  List<Employee> results = sortedQuery(queryableList, "firstName", instanceOf(SalesEmployee.class));

  assertEquals(1, results.size());
  assertEquals("SalesEmployee", results.get(0).getClass().getSimpleName());

您还可以查询实现某些接口的类：

  List<Employee> results = sortedQuery(queryableList, "firstName",      
                              implementsInterface(Comparable.class));

  assertEquals(1, results.size());
  assertEquals("SalesEmployee", results.get(0).getClass().getSimpleName());

您还可以索引嵌套的字段/属性，它们可以是深度嵌套的集合字段或属性非集合字段：

  /* Create a repo, and decide what to index. */
  RepoBuilder repoBuilder = RepoBuilder.getInstance();

  /* Look at the nestedIndex. */
  repoBuilder.primaryKey("id")
          .searchIndex("firstName").searchIndex("lastName")
          .searchIndex("salary").uniqueSearchIndex("empNum")
          .nestedIndex("tags", "metas", "metas2", "name2");

稍后，您可以使用nestedIndex进行搜索。

  List<Map<String, Object>> list = repo.query(
          selects(select("tags", "metas", "metas2", "name2")),
          eqNested("2tag1", "tags", "metas", "metas2", "name2"));

使用nestedIndex的安全方法是使用eqNested。如果具有这样的索引，则可以使用eq，gt，gte等：

  List<Map<String, Object>> list = repo.query(
          selects(select("tags", "metas", "metas2", "name2")),
          eq("tags.metas.metas2.name2", "2tag1"));

您还可以添加对子类的支持

  List<Employee> queryableList = $q(h_list, Employee.class, SalesEmployee.class,  
                  HourlyEmployee.class);
  List<Employee> results = sortedQuery(queryableList, "firstName", eq("commissionRate", 1));
  assertEquals(1, results.size());
  assertEquals("SalesEmployee", results.get(0).getClass().getSimpleName());

  results = sortedQuery(queryableList, "firstName", eq("weeklyHours", 40));
  assertEquals(1, results.size());
  assertEquals("HourlyEmployee", results.get(0).getClass().getSimpleName());

数据仓库在其DataRepoBuilder.build（...）方法中具有类似的功能，用于指定子类。这使您可以在同一存储库或可搜索集合中的子类和类中查询字段看起来没有问题。