Java Collection的多个索引 – 最基本的解决scheme？
我正在寻找最基本的解决scheme来在Java集合上创build多个索引。
所需的function：
- 当一个值被删除时，与该值关联的所有索引条目都必须被删除。
- 索引查找必须比线性search更快（至less与TreeMap一样快）。
侧面条件：
- 对大型（如Lucene）库没有依赖性。 没有不寻常的或没有经过良好testing的库。 没有数据库。
- 一个像Apache Commons Collections等库是可以的。
- 更好的是，如果它只与JavaSE（6.0）一起工作。
- 编辑：没有自我实现的解决scheme（感谢提供这个答案 – 这是完美的，他们在这里是很好的，但我已经有一个解决scheme非常类似于周杰伦） 每当有人发现，他们执行相同的事情，这应该成为一些共同图书馆的一部分。
当然，我可以自己写一个pipe理多个Maps的类（这并不困难，但感觉就像重新发明了轮子） 。 所以我想知道，如果它可以没有 – 而仍然得到一个简单的用法类似于使用一个索引的java.util.Map。
谢谢，克里斯
更新
看起来好像我们还没有find任何东西。 我喜欢所有的答案 – 自我开发的版本，链接到类似数据库的库。
以下是我真正想要的：在（a）Apache Commons Collections或（b）在Google Collections / Guava中具有这些function。 或者，也许是一个很好的select。
其他人也会错过这些库中的这个function吗？ 他们确实提供了诸如MultiMaps，MulitKeyMaps，BidiMaps等各种各样的东西，我觉得它很适合那些库，可以称之为MultiIndexMap 。 你怎么看？
每个索引将基本上是一个单独的Map 。 你可以（也可能应该）在一个为你pipe理search，索引，更新和删除的类后面抽象出来。 相当一般地做这件事并不困难。 但是，不，没有标准的开箱即用的类，虽然它可以很容易地从Java Collections类构build。
看看CQEngine（集合查询引擎） ，它完全适合这种需求，基于IndexedCollection 。
另请参见相关问题如何查询Java中的对象集合（Criteria / SQL-like）？ 为更多的背景。
我的第一个想法是为被索引的东西创build一个类，然后创build多个HashMap来存放索引，并将相同的对象添加到每个HashMap中。 对于添加，您只需将相同的对象添加到每个HashMap。 删除将需要search每个HashMap以引用到目标对象。 如果需要快速删除，则可能需要为每个索引创build两个HashMap：一个用于索引到值，另一个用于索引值。 当然，我会用一个明确定义的界面来包装你在课堂上所做的任何事情。
看起来这不会很难。 如果您事先知道索引的数量和types，以及该部件的类，那将是非常简单的，例如：
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 ... } }
如果你想使它通用并接受任何对象，具有可变数量和types的索引等等，那么它稍微复杂一点，但不多。
你有很多真正的紧缩要求似乎是非常特别的你的需求。 你说的大部分东西都是不可行的，因为很多人都有相同的确切需求，基本上定义了一个基本的数据库引擎。 这就是为什么他们是“大型”图书馆。 你说“没有数据库”，但是其核心的每一个索引系统都是条款和文件的“数据库”。 我会争辩说，一个集合是一个“数据库”。 我会说看看Space4J 。
我会说，如果你没有find你要找的东西，在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
Googlecollections是
- 轻量级
- 由Joshua Block（Effective Java）提供支持
- 不错的function如ImmutableList，ImmutableMap等等
你需要看看恩。 🙂
http://rick-hightower.blogspot.com/2013/11/what-if-java-collections-and-java.html
您可以添加n个search索引和查找索引。 它也允许你高效地查询原始属性。
这里是一个来自wiki的例子（我是作者）。
repoBuilder.primaryKey("ssn") .searchIndex("firstName").searchIndex("lastName") .searchIndex("salary").searchIndex("empNum", true) .usePropertyForAccess(true);
您可以通过提供一个真正的标志作为searchIndex的第二个参数来覆盖它。
注意empNum是一个可search的唯一索引。
如果在运行时很容易查询一组复杂的Java对象呢？ 如果有一个API保持你的对象索引（实际上只是TreeMaps和HashMaps）是同步的。 那么你会有Boon的数据回购。 本文介绍如何使用Boon的数据仓库实用程序来查询Java对象。 这是第一部分。 可以有很多很多的部分。 🙂 Boon的数据回购使得基于索引的查询更容易。 为什么Boon数据回购
Boon的数据仓库允许您至less在查询集合时更像处理数据库一样处理Java集合。 Boon的数据回购不是内存数据库，不能替代你的对象安排到为你的应用程序优化的数据结构中。 如果您想花时间提供客户价值并构build对象和类，并使用Collections API来实现数据结构，那么DataRepo就是为您而devise的。 这并不排除克努特的书，并提出了一个优化的数据结构。 它只是帮助保持世俗的事情容易，所以你可以花费你的时间，使艰难的事情成为可能。 出生于需要
这个项目出于需要。 我正在研究一个项目，计划在内存中存储大量域对象以提高速度，有人问我所忽视的一个重要问题。 我们将如何查询这些数据。 我的答案是我们将使用Collections API和Streaming API。 然后我试图做到这一点…嗯…我也厌倦了在一个大型数据集上使用JDK 8streamAPI，而且速度很慢。 （Boon的数据回购适用于JDK7和JDK8）。 这是一个线性search/filter。 这是devise的，但是对于我在做的事情来说，这是行不通的。 我需要索引来支持任意查询。 Boon的数据仓库增加了stream媒体API。
Boon的数据仓库不会尽力取代JDK 8的streamAPI，事实上它可以很好地工作。 Boon的数据仓库允许您创build索引集合。 索引可以是任何东西（可插入）。 在这个时候，Boon的数据回购索引是基于ConcurrentHashMap和ConcurrentSkipListMap的。 通过devise，Boon的数据回购与标准收集库一起工作。 没有计划创build一组自定义集合。 一个人应该能够插入番石榴，并发树木或特雷夫如果愿意这样做。 它为此提供了一个简化的API。 它允许线性search的完成感，但我build议主要用于使用索引，然后使用streamAPI（其他types的安全性和速度）。
一步一步的偷偷摸摸的高峰
假设你有一个方法可以创build20万个这样的员工对象：
List<Employee> employees = TestHelper.createMetricTonOfEmployees(200_000);
所以现在我们有20万名员工。 我们来search一下…
在可search的查询中首先包装员工：
employees = query(employees);
现在search：
List<Employee> results = query(employees, eq("firstName", firstName));
那么上面和streamAPI的主要区别是什么？
employees.stream().filter(emp -> emp.getFirstName().equals(firstName)
使用Boon's DataRepo的速度要快2万倍！ 啊HashMaps和TreeMaps的力量。 :)有一个API，看起来就像你的内置集合。 还有一个更像DAO对象或回购对象的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 8streamAPI，则不会违反它：
int sum = repo.query(eq("lastName", "Smith")).stream().filter(emp -> emp.getSalary()>50_000) .mapToInt(b -> b.getSalary()) .sum();
如果员工人数相当多，以上情况就会快得多。 这将缩小以史密斯的名字开始并且薪水高于5万美元的员工。 假设你有10万名员工，只有50名Smith，所以现在你可以通过使用可以有效抽取10万名员工中的50名员工的指数，迅速缩小到50名，那么我们只需要50名而不是10万名。
这里是一个从纳米秒的线性search与索引search的数据回购的基准运行：
Name index Time 218 Name linear Time 3709120 Name index Time 213 Name linear Time 3606171 Name index Time 219 Name linear Time 3528839
最近有人对我说：“但是使用stream媒体API，你可以在parralel中运行这个filter。
让我们看看math如何成立：
3,528,839 / 16 threads vs. 219 201,802 vs. 219 (nano-seconds).
索引赢了，但这是一个照片完成。 不！ 🙂
只比速度提高了9,500％，而不是提高了40,000％。 很近…..
我添加了一些更多的function。 他们正在大量使用索引。 🙂
repo.updateByFilter（value（“firstName”，“Di”））和（eq（“firstName”，“Diana”），eq（“lastName”，“Smith”），eq（“ssn”，“21785999 “）））;
以上将相当于
UPDATE Employee e SET e.firstName ='Di'WHERE e.firstName ='Diana'and e.lastName ='Smith'and e.ssn ='21785999'
这使您可以在多个logging中一次设置多个字段，以便进行批量更新。
对于所有基本types都有重载的方法，所以如果你有一个值来更新每个从filter返回的项目：
repo.updateByFilter("firstName", "Di", and( eq("firstName", "Diana"), eq("lastName", "Smith"), eq("ssn", "21785999") ) );
以下是一些基本的selectfunction：
List <Map<String, Object>> list = repo.query(selects(select("firstName")), eq("lastName", "Hightower"));
你可以有尽可能多的select，只要你喜欢。 您还可以将列表重新sorting：
List <Map<String, Object>> list = repo.sortedQuery("firstName",selects(select("firstName")), eq("lastName", "Hightower"));
您可以select相关属性的属性（即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”）快得多，这可能会在严格的循环中起作用。
默认情况下，所有search索引和查找索引都允许重复（主键索引除外）。
repoBuilder.primaryKey("ssn") .searchIndex("firstName").searchIndex("lastName") .searchIndex("salary").searchIndex("empNum", true) .usePropertyForAccess(true);
您可以通过提供一个真正的标志作为searchIndex的第二个参数来覆盖它。
注意empNum是一个可search的唯一索引。
如果你喜欢或者需要，你甚至可以简单地search回地图：
List<Map<String, Object>> employees = repo.queryAsMaps(eq("firstName", "Diana"));
我不确定这是一个特征还是一个错误。 我的想法是，一旦你处理数据，你需要以一种不会将数据消费者与实际API关联起来的方式呈现数据。 有一个string/基本types的地图似乎是一种方法来实现这一点。 请注意，对象映射转换深入如下：
System.out.println(employees.get(0).get("department"));
产量：
{class=Department, name=engineering}
这对debugging和临时查询工具非常有用。 我正在考虑添加支持轻松转换为JSONstring。
增加了查询集合属性的function。 这应该适用于深度嵌套的集合和数组。 再读一遍，因为这是一个真正的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]}, ...
我创build了几个关系类来testing这个：
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 { ...
您也可以按typessearch：
List<Employee> results = sortedQuery(queryableList, "firstName", typeOf("SalesEmployee")); assertEquals(1, results.size()); assertEquals("SalesEmployee", results.get(0).getClass().getSimpleName());
上面find了所有员工的简单类名SalesEmployee。 它也适用于完整的类名称，如：
List<Employee> results = sortedQuery(queryableList, "firstName", typeOf("SalesEmployee")); assertEquals(1, results.size()); assertEquals("SalesEmployee", results.get(0).getClass().getSimpleName());
你也可以通过实际的课程search：
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进行search。
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（…）方法中具有类似的function。 这允许您在相同的回购或可search集合中使用无形的查询字段形成子类和类。
我写了一个表格界面，其中包括像
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()
我们希望在未来的番石榴版本中join它，但是我不知道什么时候会发生。 http://code.google.com/p/guava-libraries/issues/detail?id=173
你的主要目标似乎是，当你从一个索引中删除对象时，你会删除这个对象。
最简单的方法是添加另一个间接层：将实际对象存储在Map<Long,Value> ，并使用一个双向地图（您可以在Jakarta Commons中find，也可能是Google Code） Map<Key,Long> 。 从特定索引中删除条目时，将从该索引获取Long值，并使用该值从主映射和其他索引中删除相应的条目。
BIDIMap的一个替代方法是将“索引”映射定义为Map<Key,WeakReference<Long>> ; 但是，这将需要您执行一个ReferenceQueue进行清理。
另一种方法是创build一个可以取任意元组的关键对象，定义它的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 表 。 它们支持尽可能多的索引，快速（索引是TreeMaps），并有很好的过滤选项（布尔filter？没问题！）。 无需数据库，在许多信息可视化应用程序中使用大型数据集进行testing。
在他们的原始forms，他们不像标准容器（你需要处理行和列）方便，但你可以写一个小包装周围。 另外，它们很好地插入到诸如Swing的JTable之类的UI组件中。
我不确定我是否理解这个问题，但是我认为你所要求的是用多种方法从不同的唯一键映射到值，并在价值消失时进行适当的清理。
我看到你不想自己推出，但是有足够简单的map和multimap组合（我使用了下面的Guava multimap，但是Apache应该也可以），来做你想做的事情。 我有一个快速和肮脏的解决scheme下面（跳过构造函数，因为这取决于你想使用什么样的基础地图/多图）：
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()和键的区别） – 但你也可以有一个更具体的键types。
让我们看看项目http://code.google.com/p/multiindexcontainer/wiki/MainPage这是一般化的方式如何使用JavaBean getter的地图，并执行查询索引值。 我想这就是你要找的。 试一试吧。
基本上，基于多个哈希映射的解决scheme将是可能的，但在这种情况下，所有这些都必须手动更新。 一个非常简单的集成解决scheme可以在这里find： http : //insidecoffe.blogspot.de/2013/04/indexable-hashmap-implementation.html
这里是我如何实现这一点，现在只放，删除和获取方法正在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
MultiKeyMap.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> { } }
