Java中简单的类似数据库的集合类

Question

问题:在java对象之间保持双向多对一关系.

像Google/Commons Collections bidi地图之类的东西,但我希望在前端允许重复值,并将前向键的集合作为反面值.使用这样的东西:

// maintaining disjoint areas on a gameboard. Location is a space on the
// gameboard; Regions refer to disjoint collections of Locations.

MagicalManyToOneMap<Location, Region> forward = // the game universe
Map<Region, <Set<Location>>> inverse = forward.getInverse(); // live, not a copy
Location parkplace = Game.chooseSomeLocation(...);
Region mine = forward.get(parkplace); // assume !null; should be O(log n)
Region other = Game.getSomeOtherRegion(...);
// moving a Location from one Region to another:
forward.put(parkplace, other);
// or equivalently:
inverse.get(other).add(parkplace); // should also be O(log n) or so
// expected consistency:
assert ! inverse.get(mine).contains(parkplace);
assert forward.get(parkplace) == other;
// and this should be fast, not iterate every possible location just to filter for mine:
for (Location l : mine) { /* do something clever */ }

简单的java方法是:1.仅维护关系的一侧,或者作为a Map<Location, Region>或a Map<Region, Set<Location>>,并在需要时通过迭代收集逆关系; 或者,2.制作一个保持双方"地图"的包装器,并拦截所有变异调用以保持双方同步.

1是O(n)而不是O(log n),这成为一个问题.我从2开始,直接在杂草中.(知道改变Map条目的方法有多少？)

这在sql世界中几乎是微不足道的(Location表获取索引的RegionID列).是否有一些显而易见的东西让我对普通物体无关紧要？

Answer 1

我认为您可以通过以下两门课程来实现您所需要的。虽然它确实涉及两张地图，但它们不会暴露给外界，因此不应该有办法让它们不同步。至于将相同的“事实”存储两次，我认为您不会在任何有效的实现中解决这个问题，无论事实是像这里那样显式存储两次，还是像数据库创建索引时隐式存储两次使您的 2 个表上的连接更加高效。您可以向 magicset 添加新内容，它将更新两个映射，或者您可以向 magicmapper 添加内容，然后它会自动更新逆映射。女朋友现在叫我去睡觉，所以我无法通过编译器运行它 - 这应该足以让你开始。你想解决什么难题？

public class MagicSet<L> {
   private Map<L,R> forward;
   private R r;
   private Set<L> set;

   public MagicSet<L>(Map forward, R r) {
       this.forward = map;
       this.r = r;
       this.set = new HashSet<L>();
   }

   public void add(L l) {
       set.add(l);
       forward.put(l,r);
   }

   public void remove(L l) {
       set.remove(l);
       forward.remove(l);
   }

   public int size() {
       return set.size();
   }

   public in contains(L l){
       return set.contains(l);
   }

   // caution, do not use the remove method from this iterator. if this class was going
   // to be reused often you would want to return a wrapped iterator that handled the remove method properly.  In fact, if you did that, i think you could then extend AbstractSet and MagicSet would then fully implement java.util.Set.
   public Iterator iterator() {
       return set.iterator();  
   }
}



public class MagicMapper<L,R> { // note that it doesn't implement Map, though it could with some extra work.  I don't get the impression you need that though.
 private Map<L,R> forward;
 private Map<R,MagicSet<L>> inverse;

 public MagicMapper<L,R>() {
       forward = new HashMap<L,R>;
       inverse = new HashMap<R,<MagicSet<L>>;
 }


 public R getForward(L key) {
       return forward.get(key);
 }


 public Set<L> getBackward(R key) {
       return inverse.get(key);  // this assumes you want a null if
                               // you try to use a key that has no mapping.  otherwise you'd return a blank MagicSet
 }

 public void put (L l, R r) {

       R oldVal = forward.get(l);

       // if the L had already belonged to an R, we need to undo that mapping
       MagicSet<L> oldSet = inverse.get(oldVal);

       if (oldSet != null) {oldSet.remove(l);}

       // now get the set the R belongs to, and add it.
       MagicSet<L> newSet = inverse.get(l);

       if (newSet == null) {
               newSet = new MagicSet<L>(forward, r);
               inverse.put(r,newSet);
       }
       newSet.add(l);  // magically updates the "forward" map
 }


}