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

Multiple indexes for a Java Collection - most basic solution?

提问by Chris Lercher

I'm looking for the most basic solution to create multiple indexes on a Java Collection.

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

Required functionality:

所需功能：

• When a Value is removed, all index entries associated with that value must be removed.
• Index lookup must be faster than linear search (at least as fast as a TreeMap).

• 删除值时，必须删除与该值关联的所有索引条目。
• 索引查找必须比线性搜索快（至少和 TreeMap 一样快）。

Side conditions:

附带条件：

• No dependencies on large (like Lucene) libraries. No uncommon or not well tested libraries. No database.
• A library like Apache Commons Collections etc. would be ok.
• Even better, if it works with JavaSE (6.0) alone.
• Edit:No self-implemented solution (thanks for the answers suggesting this - it's good to have them here for completeness, but I already have a solution very similar to Jay's) Whenever several people find out, that they implemented the same thing, this should be part of some common library.

• 不依赖大型（如 Lucene）库。没有不常见或未经充分测试的库。没有数据库。
• 像 Apache Commons Collections 等库就可以了。
• 更好的是，如果它单独与 JavaSE (6.0) 一起工作。
• 编辑：没有自我实现的解决方案（感谢提出这一点的答案 - 为了完整性，将它们放在这里很好，但我已经有了一个与 Jay 非常相似的解决方案）每当有几个人发现他们实现了同样的事情时，这应该成为一些公共图书馆的一部分。

Of course, I could write a class that manages multiple Maps myself (that's not hard, but it feels like reinventing the wheel). So I'd like to know, if it can be done without - while still getting a simple usage similar to using a single indexed java.util.Map.

当然，我可以自己编写一个管理多个 Map 的类（这并不难，但感觉就像重新发明轮子）。所以我想知道，是否可以在没有的情况下完成 - 同时仍然获得类似于使用单个索引的 java.util.Map 的简单用法。

Thanks, Chris

谢谢，克里斯

Update

更新

It looks very much as if we haven't found anything. I like all your answers - the self developed versions, the links to database-like libraries.

看起来我们好像什么也没找到。我喜欢你所有的答案 - 自行开发的版本，类似数据库的库的链接。

Here's what I really want: To have the functionality in (a) Apache Commons Collections or (b) in Google Collections/Guava. Or maybe a very good alternative.

这是我真正想要的：在 (a) Apache Commons Collections 或 (b) Google Collections/Guava 中拥有功能。或者也许是一个非常好的选择。

Do other people miss this functionality in these libraries, too? They do provide all sorts of things like MultiMaps, MulitKeyMaps, BidiMaps, ... I feel, it would fit in those libraries nicely - it could be called MultiIndexMap. What do you think?

其他人是否也错过了这些库中的此功能？他们确实提供了各种各样的东西，比如 MultiMaps、MulitKeyMaps、BidiMaps……我觉得，它很适合这些库——它可以被称为MultiIndexMap. 你怎么认为？

采纳答案by cletus

Each index will basically be a separate Map. You can (and probably should) abstract this behind a class that manages the searches, indexing, updates and removals for you. It wouldn't be hard to do this fairly generically. But no, there's no standard out of the box class for this although it can easily be built from the Java Collections classes.

每个索引基本上都是一个单独的Map. 您可以（并且可能应该）将其抽象为一个为您管理搜索、索引、更新和删除的类。相当普遍地做到这一点并不难。但是不，虽然它可以很容易地从 Java Collections 类构建，但没有标准的开箱即用类。

回答by Jay

My first thought would be to create a class for the thing being indexed, then create multiple HashMap's to hold the indexes, with the same object added to each of the HashMaps. For an add, you'd then simply add the same object to each HashMap. A delete would require searching each HashMap for the reference to the destination object. If deletes need to be fast, you might want to create two HashMaps for each index: one for index-to-value and the other for value-to-index. Of course I'd wrap whatever you do in a class with a clearly-defined interface.

我的第一个想法是为被索引的事物创建一个类，然后创建多个 HashMap 来保存索引，并将相同的对象添加到每个 HashMap。对于添加，您只需将相同的对象添加到每个 HashMap。删除需要在每个 HashMap 中搜索对目标对象的引用。如果删除需要快速，您可能需要为每个索引创建两个 HashMap：一个用于索引到值，另一个用于值到索引。当然，我会将您所做的任何事情都包装在一个具有明确定义接口的类中。

Doesn't seem like this would be hard. If you know the numbers and types of the indexes and the class of the widget up front, it would be pretty easy, like:

这似乎并不难。如果您预先知道索引的数量和类型以及小部件的类，那将非常简单，例如：

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

  }
}

If you want to make it generic and accept any object, have variable number and types of indexes, etc., it's a little more complicated, but not much.

如果你想让它通用并接受任何对象，有可变数量和类型的索引等，它有点复杂，但不多。

回答by Jared Levy

I've written a Table interface that includes methods like

我编写了一个 Table 接口，其中包括诸如

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()

We'd like to include it in a future Guava release, but I don't know when that would happen. http://code.google.com/p/guava-libraries/issues/detail?id=173

我们希望将它包含在未来的 Guava 版本中，但我不知道什么时候会发生。 http://code.google.com/p/guava-libraries/issues/detail?id=173

回答by Arthur Ronald

Google CollectionsLinkedListMultimap

Google Collections LinkedListMultimap

About your first requirement

关于你的第一个要求

• When a Value is removed, all index entries associated with that value must be removed.

• 删除值时，必须删除与该值关联的所有索引条目。

I think There is neither a library nor a Helper that supports it.

我认为既没有图书馆也没有支持它的助手。

Here is how i have done by using 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

To get your first requirement, a Helper can play a good job

得到你的第一个要求，一个Helper可以很好地工作

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

Google collections is

谷歌收藏是

• lightweight
• Supported by Joshua Block (Effective Java)
• Nice features as ImmutableList, ImmutableMap and so on

• 轻的
• 由 Joshua Block (Effective Java) 支持
• ImmutableList、ImmutableMap 等不错的特性

回答by Arthur Ronald

You have a lot of really constrictive requirements are appear to be very particular to your needs. Most of the things you are saying aren't viable are because a lot so of people have the same exact needs which basically defines a basic database engine. That is why they are "large" libraries. You say "no database" but at its core every indexing system is a "database" of terms and documents. I would argue that a Collection is a "database". I would say take a look at Space4J.

您有很多非常严格的要求，它们似乎对您的需求非常特别。您所说的大多数事情都不可行是因为很多人都有相同的确切需求，这基本上定义了基本的数据库引擎。这就是为什么它们是“大型”图书馆的原因。您说“没有数据库”，但其核心是每个索引系统都是术语和文档的“数据库”。我认为 Collection 是一个“数据库”。我会说看看Space4J。

I would say if you don't find what you are looking for, start a project on GitHub and get on with coding it yourself and sharing the results.

我会说如果你没有找到你要找的东西，在 GitHub 上开始一个项目，然后自己编码并分享结果。

回答by Carl

I'm not sure I understand the question, but I think what you're asking for is multiple ways to map from different, unique keys to values and appropriate clean-up when a value goes away.

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

I see that you don't want to roll your own, but there's a simple enough composition of map and multimap (I used the Guava multimap below, but the Apache one should work as well) to do what you want. I have a quick and dirty solution below (skipped the constructors, since that depends on what sort of underlying map/multimap you want to use):

我看到你不想自己动手，但是有一个足够简单的 map 和 multimap 组合（我在下面使用了 Guava 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();
    }   

}

removal is O(number of keys), but everything else is the same order as a typical map implementation (some extra constant scaling, since you also have to add things to the reverse).

删除是 O（键数），但其他所有内容与典型地图实现的顺序相同（一些额外的常量缩放，因为您还必须向相反方向添加内容）。

I just used Objectkeys (should be fine with appropriate implementations of equals()and hashCode()and key distinction) - but you could also have a more specific type of key.

我只是使用了Object键（使用equals()andhashCode()和键区分的适当实现应该没问题）-但是您也可以使用更具体的键类型。

回答by tucuxi

Use PrefuseTables. They support as many indices as you want, are fast (indices are TreeMaps), and have nice filtering options (boolean filters? no problem!). No database required, tested with large data-sets in many information visualization applications.

使用前缀表。它们支持任意数量的索引，速度很快（索引是 TreeMaps），并且有很好的过滤选项（布尔过滤器？没问题！）。无需数据库，在许多信息可视化应用程序中使用大型数据集进行测试。

In their raw form, they are not as convenient as standard containers (you need to deal with rows and columns), but you can surely write a small wrapper around that. Plus, they plug nicely into UI components such as Swing's JTables.

在原始形式中，它们不如标准容器方便（您需要处理行和列），但是您肯定可以围绕它编写一个小包装器。此外，它们可以很好地插入 UI 组件，例如 Swing 的 JTables。

回答by Anon

Your main goal seems to be that you'll remove the object from all indexes when you remove it from one.

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

The simplest approach will be to add another layer of indirection: you store your actual object in a Map<Long,Value>, and use a bidirectional map (which you'll find in Jakarta Commons and probably Google Code) for your indexes as Map<Key,Long>. When you remove an entry from a particular index, you'll take the Longvalue from that index and use it to remove the corresponding entries from the main map and the other indexes.

最简单的方法是添加另一层间接：您将实际对象存储在 中Map<Long,Value>，并使用双向映射（您可以在 Jakarta Commons 和谷歌代码中找到）作为Map<Key,Long>. 当您从特定索引中删除条目时，您Long将从该索引中获取值并使用它从主映射和其他索引中删除相应的条目。

One alternative to the BIDIMap is to define your "index" maps as Map<Key,WeakReference<Long>>; however, this will require you to implement a ReferenceQueuefor cleanup.

BIDIMap 的一种替代方法是将您的“索引”映射定义为Map<Key,WeakReference<Long>>；但是，这将需要您实施ReferenceQueue清理。

---

---

Another alternative is to create a key object that can take an arbitrary tuple, define its equals()method to match on any element in the tuple, and use that with a TreeMap. You can't use a HashMap, because you won't be able to compute a hashcode based on just one element of the tuple.

另一种选择是创建一个可以采用任意元组的键对象，定义其equals()方法以匹配元组中的任何元素，并将其与TreeMap. 您不能使用 a 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()
   }
}

回答by Fekete Kamosh

lets look at project http://code.google.com/p/multiindexcontainer/wiki/MainPageThis is generalized way how to use maps for JavaBean getters and perform lookups over indexed values. I think this is what you are looking for. Lets give it a try.

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

回答by npgall

Take a look at CQEngine (Collection Query Engine), it's an exact fit for this kind of requirement, being based around an IndexedCollection.

看看CQEngine（集合查询引擎），它非常适合这种需求，基于IndexedCollection.

Also see related question How do you query object collections in Java (Criteria/SQL-like)?for more background.

另请参阅相关问题How do you query object collections in Java (Criteria/SQL-like)？更多背景。