algorithm - 字符串集实现

Question

我必须为一对字符串实现一组 ADT。我想要的界面是(在 Java 中):

public interface StringSet {
  void add(String a, String b);
  boolean contains(String a, String b);
  void remove(String a, String b);
}

数据访问模式具有以下属性:

1. contains操作比 add 频繁得多和 remove一个。
2. 更多时候不是，contains返回 true即搜索成功

我能想到的一个简单实现是使用两级哈希表，即 HashMap<String, HashMap<String, Boolean>> .但是这个数据结构没有利用访问模式的两个特性。我想知道是否有比哈希表更有效的东西，也许是通过利用访问模式的特性。

Answer 1

就个人而言，我会根据标准 Set<> 来设计它界面:

public class StringPair {
   public StringPair(String a, String b) {
     a_ = a;
     b_ = b;
     hash_ = (a_ + b_).hashCode();
   }

   public boolean equals(StringPair pair) {
      return (a_.equals(pair.a_) && b_.equals(pair.b_));
   }

   @Override
   public boolean equals(Object obj) {
      if (obj instanceof StringPair) {
        return equals((StringPair) obj);
      }
      return false;
   }

   @Override
   public int hashCode() {
     return hash_;
   }

   private String a_;
   private String b_;
   private int hash_;
}

public class StringSetImpl implements StringSet {
   public StringSetImpl(SetFactory factory) {
     pair_set_ = factory.createSet<StringPair>();
   }

   // ...

   private Set<StringPair> pair_set_ = null;
}

然后您可以让 StringSetImpl 的用户使用首选的 Set 类型。但是，如果您尝试优化访问，很难比 HashSet<> 做得更好(至少在运行时复杂性方面)，因为访问是 O(1)，而基于树的集合具有 O(log N)访问时间。

contains() 通常返回 true 可能值得考虑 Bloom filter ，尽管这需要允许 contains() 的一些误报(不知道是否是这种情况)。

编辑

为了避免额外的分配，你可以做这样的事情，这类似于你的两级方法，除了第二级使用集合而不是映射:

public class StringSetImpl implements StringSet {
   public StringSetImpl() {
     elements_ = new HashMap<String, Set<String>>();
   }

   public boolean contains(String a, String b) {
     if (!elements_.containsKey(a)) {
       return false;
     }
     Set<String> set = elements_.get(a);
     if (set == null) {
       return false;
     }
     return set.contains(b);
   }

   public void add(String a, String b) {
     if (!elements_.containsKey(a) || elements_.get(a) == null) {
       elements_.put(a, new HashSet<String>());
     }
     elements_.get(a).add(b);
   }

   public void remove(String a, String b) {
     if (!elements_.containsKey(a)) {
       return;
     }
     HashSet<String> set = elements_.get(a);
     if (set == null) {
       elements_.remove(a);
       return a;
     }
     set.remove(b);
     if (set.empty()) {
       elements_.remove(a);
     }
   }

   private Map<String, Set<String>> elements_ = null;
}

因为我所在的地方是凌晨 4:20，所以以上绝对不是我最好的作品(太累了，无法重新审视这些不同集合类型对 null 的处理)，但它概述了方法。