Java集合的多个索引-最基本的解决方案?

每个索引基本上都是一个单独的 Map . 您可以(也可能应该)将其抽象到一个类后面,该类为您管理搜索、索引、更新和删除。一般来说,这样做并不难。但是,没有,尽管它可以很容易地从Java集合类中构建,但它没有标准的Box类。

看一看 CQEngine (Collection Query Engine) ,它完全适合这种需求,基于 IndexedCollection .

另见相关问题 How do you query object collections in Java (Criteria/SQL-like)? 了解更多背景。

我的第一个想法是为被索引的对象创建一个类,然后创建多个hashmap来保存索引,并在每个hashmap中添加相同的对象。对于add,只需将相同的对象添加到每个hashmap。删除操作需要在每个hashmap中搜索对目标对象的引用。如果需要快速删除,则可能需要为每个索引创建两个哈希映射:一个用于索引到值,另一个用于值到索引。当然,我会用一个定义明确的接口将您所做的一切打包到一个类中。

看起来这并不难。如果您预先知道索引的数量和类型以及小部件的类,这将非常简单,例如:

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 ...

  }
}

如果您想使它成为泛型并接受任何对象、具有变量数和索引类型等,那么它会稍微复杂一些,但不会太复杂。

你有很多非常严格的要求,似乎对你的需求非常特殊。你说的大多数不可行的地方是因为很多人有相同的需求,基本上定义了一个基本的数据库引擎。这就是为什么它们是“大型”图书馆。你说“没有数据库”,但每个索引系统的核心是术语和文档的“数据库”。我认为一个集合就是一个“数据库”。我想说看看 Space4J .

如果你找不到你想要的东西,我会说,在github上启动一个项目,然后自己编写代码并分享结果。

Google Collections LinkedListMultimap

关于你的第一个要求

• 删除值时,必须删除与该值关联的所有索引项。

我想既没有图书馆也没有帮手支持它。

下面是我如何使用LinkedListMultiMap

Multimap<Integer, String> multimap = LinkedListMultimap.create();

// Three duplicates entries
multimap.put(1, "A");
multimap.put(2, "B");
multimap.put(1, "A");
multimap.put(4, "C");
multimap.put(1, "A");

System.out.println(multimap.size()); // outputs 5

为了得到你的第一个要求,一个助手可以做得很好

public static <K, V> void removeAllIndexEntriesAssociatedWith(Multimap<K, V> multimap, V value) {
    Collection<Map.Entry<K, V>> eCollection = multimap.entries();
    for (Map.Entry<K, V> entry : eCollection)
        if(entry.getValue().equals(value))
            eCollection.remove(entry);
}

…

removeAllIndexEntriesAssociatedWith(multimap, "A");

System.out.println(multimap.size()); // outputs 2

谷歌收藏是

• 轻量化
• Joshua Block(JAVA)支持
• ImmutableList、ImmutableMap等不错的特性

你得去看看布恩。:)

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的数据Reo实用工具来查询Java对象。这是第一部分。可能有很多很多部分。:) Boon的数据回购使对集合进行基于索引的查询变得更加容易。 为什么是Boon数据回购

Boon的数据RePO允许您至少在查询集合时更像Java数据库那样对待Java集合。Boon的数据repo不是内存数据库,不能替代将对象排列成针对应用程序优化的数据结构。 如果您想花时间提供客户价值,构建对象和类,并为数据结构使用collections api,那么datarepo就是为您准备的。这并不排除打破knuth书籍和提出一个优化的数据结构。它只是有助于让平凡的事情变得容易,这样你就可以把时间花在让困难的事情成为可能上。 出于需要而生

这个项目是出于需要。我正在做一个项目,计划将大量域对象存储在内存中以提高速度,有人问了一个我忽略的非常重要的问题。我们将如何查询这些数据。我的回答是我们将使用collections api和streaming api。然后我试着这么做…六羟甲基三聚氰胺六甲醚。。。 我还厌倦了在大型数据集上使用jdk 8流api,而且速度很慢。(boon的数据repo与jdk7和jdk8一起工作)。这是一个线性搜索/过滤。这是故意的,但对于我所做的,它没有起作用。我需要索引来支持任意查询。 Boon的数据回购增强了流式API。

boon的data repo并不试图替换jdk 8流api,事实上它与jdk8流api配合得很好。Boon的数据回购允许您创建索引集合。索引可以是任何东西(它是可插入的)。 此时,Boon的数据回购索引基于ConcurrentHashMap和ConcurrentSkipListMap。 从设计上讲,boon的data repo与标准的集合库一起工作。没有计划创建一组自定义集合。一个人应该能够插入番石榴,并发树或特洛伊如果你想这样做。 它为此提供了一个简化的api。它允许线性搜索以获得完成感,但我建议主要使用它来使用索引,然后使用流式api来实现其余部分(为了类型安全和速度)。

潜峰前一步一步

假设您有一个创建200000个Employee对象的方法,如下所示:

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

现在我们有20万员工。让我们搜索他们…

首先在可搜索查询中包装员工:

   employees = query(employees);

现在搜索:

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

那么,上面的api和streamapi的主要区别是什么?

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

使用Boon的Datarepo大约快2万倍!啊,hashmaps和treemaps的威力。:) 有一个api看起来就像您的内置集合。还有一个api看起来更像dao对象或repo对象。

带有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();

如果员工数量很大的话,上面的速度会快得多。它将缩小以史密斯起名、薪水超过5万英镑的雇员的范围。假设你有10万名员工,只有50名叫史密斯,那么现在你可以通过使用有效地从10万名员工中抽取50名员工的索引快速缩小到50名,然后我们只对50名员工进行筛选,而不是全部10万名员工。

以下是线性搜索和索引搜索在纳秒内的数据回购基准:

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,你可以在parralel中运行过滤器。”

让我们看看数学是如何成立的:

3,528,839 / 16 threads vs. 219

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

Indexes赢了,但这是一个照片结束。不是!:)

它的速度只有9500%,而不是40000%。如此接近……

我又增加了一些功能。他们正在大量使用索引。:)

repo.updateByFilter(值(value(“firstname”,“di”)), 以及(eq(“firstname”,“diana”), eq(“姓氏”,“史密斯”), 公式(“SSN”,“21785999”));

以上内容相当于

更新员工E 设置e.firstname='di' 其中e.firstname='戴安娜' 和e.lastname='史密斯' 和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”,真)
.UsePropertyForAccess(真);

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

注意empnum是一个可搜索的唯一索引。

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

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

我不确定这是一个功能还是一个错误的功能。我的想法是,一旦处理数据,就需要以一种不将数据的使用者与实际api联系起来的方式来表示数据。拥有字符串/基本类型的映射似乎是实现这一点的一种方法。 请注意,对象到映射的转换深入到:

  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”));

资产质量(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");

稍后可以使用嵌套索引进行搜索。

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

使用嵌套索引的安全方法是使用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());

data repo在其datarepobuilder.build(…)方法中有一个类似的特性,用于指定子类。这允许您在同一个repo或可搜索集合中查看来自子类和类的无限制查询字段。

我编写了一个表接口,其中包括

V put(R rowKey, C columnKey, V value) 
V get(Object rowKey, Object columnKey) 
Map<R,V> column(C columnKey) 
Set<C> columnKeySet()
Map<C,V> row(R rowKey)
Set<R> rowKeySet()
Set<Table.Cell<R,C,V>> cellSet()

我们想在未来的番石榴发布中加入它,但我不知道什么时候会这样。 http://code.google.com/p/guava-libraries/issues/detail?id=173

您的主要目标似乎是从一个索引中移除对象时,将从所有索引中移除该对象。

最简单的方法是添加另一层间接寻址:将实际对象存储在 Map<Long,Value> ,并使用双向映射(您可以在jakarta commons和可能的google代码中找到)作为索引 Map<Key,Long> . 从特定索引中删除条目时,将 Long 值,并使用它从主映射和其他索引中删除相应的项。

bidimap的另一种选择是将“索引”映射定义为 Map<Key,WeakReference<Long>> ;但是,这将要求您实现 ReferenceQueue 用于清理。

---

另一种方法是创建一个键对象,该对象可以接受任意元组,定义 equals() 方法匹配元组中的任何元素,并将其与 TreeMap . 你不能用 HashMap ,因为您将无法仅基于元组的一个元素计算哈希代码。

public class MultiKey
implements Comparable<Object>
{
   private Comparable<?>[] _keys;
   private Comparable _matchKey;
   private int _matchPosition;

   /**
    *  This constructor is for inserting values into the map.
    */
   public MultiKey(Comparable<?>... keys)
   {
      // yes, this is making the object dependent on externally-changable
      // data; if you're paranoid, copy the array
      _keys = keys;
   }


   /**
    *  This constructor is for map probes.
    */
   public MultiKey(Comparable key, int position)
   {
      _matchKey = key;
      _matchPosition = position;
   }


   @Override
   public boolean equals(Object obj)
   {
      // verify that obj != null and is castable to MultiKey
      if (_keys != null)
      {
         // check every element
      }
      else
      {
         // check single element
      }
   }


   public int compareTo(Object o)
   {
      // follow same pattern as equals()
   }
}

使用 Prefuse Tables . 它们支持任意数量的索引,速度快(索引是treemaps),并且有很好的过滤选项(布尔过滤器?没问题!)。不需要数据库,在许多信息可视化应用程序中使用大型数据集进行测试。

在它们的原始形式中,它们不像标准容器那样方便(您需要处理行和列),但您肯定可以在其周围编写一个小包装器。另外,它们很好地插入了ui组件,比如swing的jtables。

如果需要对数据进行多个索引,则可以创建和维护多个哈希映射或使用类似于库的数据存储:

https://github.com/jparams/data-store

例子:

Store<Person> store = new MemoryStore<>() ;
store.add(new Person(1, "Ed", 3));
store.add(new Person(2, "Fred", 7));
store.add(new Person(3, "Freda", 5));
store.index("name", Person::getName);
Person person = store.getFirst("name", "Ed");

使用数据存储,您可以创建不区分大小写的索引和各种很酷的东西。值得一看。

我不确定我是否理解这个问题,但我认为你需要的是多种方法,从不同的、唯一的键映射到值,并在值消失时进行适当的清理。

我知道你不想自己滚动,但是有一个足够简单的map和multimap组合(我在下面使用了番石榴multimap,但是apache也应该可以)来做你想做的事情。我有一个快速而肮脏的解决方案(跳过构造函数,因为这取决于要使用哪种底层映射/多重映射):

package edu.cap10.common.collect;

import java.util.Collection;
import java.util.Map;

import com.google.common.collect.ForwardingMap;
import com.google.common.collect.Multimap;

public class MIndexLookupMap<T> extends ForwardingMap<Object,T>{

    Map<Object,T> delegate;
    Multimap<T,Object> reverse;

    @Override protected Map<Object, T> delegate() { return delegate; }

    @Override public void clear() {
        delegate.clear();
        reverse.clear();
    }

    @Override public boolean containsValue(Object value) { return reverse.containsKey(value); }

    @Override public T put(Object key, T value) {
        if (containsKey(key) && !get(key).equals(value)) reverse.remove(get(key), key); 
        reverse.put(value, key);
        return delegate.put(key, value);
    }

    @Override public void putAll(Map<? extends Object, ? extends T> m) {
        for (Entry<? extends Object,? extends T> e : m.entrySet()) put(e.getKey(),e.getValue());
    }

    public T remove(Object key) {
        T result = delegate.remove(key);
        reverse.remove(result, key);
        return result;
    }

    public void removeValue(T value) {
        for (Object key : reverse.removeAll(value)) delegate.remove(key);
    }

    public Collection<T> values() {
        return reverse.keySet();
    }   

}

删除是o(键的数量),但其他的都是与典型的映射实现相同的顺序(一些额外的常量缩放,因为您还必须将内容添加到相反的位置)。

我刚刚用过 Object 密钥(应该可以通过适当的 equals() 和 hashCode() 和键的区别),但是你也可以有一个更具体的键类型。

让我们看看项目 http://code.google.com/p/multiindexcontainer/wiki/MainPage 这是如何为javabean getter使用映射和对索引值执行查找的一般方法。 我想这就是你要找的。让我们试一试。

基本上,基于多个散列映射的解决方案是可能的,但在这种情况下,必须手动更新所有散列映射。一个非常简单的集成解决方案可以在这里找到: http://insidecoffe.blogspot.de/2013/04/indexable-hashmap-implementation.html

下面是我实现这一点的方法,现在只有put、remove和get方法可以用于rest,您需要重写所需的方法。

例子:

MultiKeyMap<MultiKeyMap.Key,String> map = new MultiKeyMap<>();
MultiKeyMap.Key key1 = map.generatePrimaryKey("keyA","keyB","keyC");
MultiKeyMap.Key key2 = map.generatePrimaryKey("keyD","keyE","keyF");

map.put(key1,"This is value 1");
map.put(key2,"This is value 2");

Log.i("MultiKeyMapDebug",map.get("keyA"));
Log.i("MultiKeyMapDebug",map.get("keyB"));
Log.i("MultiKeyMapDebug",map.get("keyC"));

Log.i("MultiKeyMapDebug",""+map.get("keyD"));
Log.i("MultiKeyMapDebug",""+map.get("keyE"));
Log.i("MultiKeyMapDebug",""+map.get("keyF"));

输出:

MultiKeyMapDebug: This is value 1
MultiKeyMapDebug: This is value 1
MultiKeyMapDebug: This is value 1
MultiKeyMapDebug: This is value 2
MultiKeyMapDebug: This is value 2
MultiKeyMapDebug: This is value 2

多键映射.java:

/**
 * Created by hsn on 11/04/17.
 */


public class MultiKeyMap<K extends MultiKeyMap.Key, V> extends HashMap<MultiKeyMap.Key, V> {

    private Map<String, MultiKeyMap.Key> keyMap = new HashMap<>();

    @Override
    public V get(Object key) {
        return super.get(keyMap.get(key));
    }

    @Override
    public V put(MultiKeyMap.Key key, V value) {
        List<String> keyArray = (List<String>) key;
        for (String keyS : keyArray) {
            keyMap.put(keyS, key);
        }
        return super.put(key, value);
    }

    @Override
    public V remove(Object key) {
        return super.remove(keyMap.get(key));
    }

    public Key generatePrimaryKey(String... keys) {
        Key singleKey = new Key();
        for (String key : keys) {
            singleKey.add(key);
        }
        return singleKey;
    }

    public class Key extends ArrayList<String> {

    }

}