java - Fast contains および LIFO データ構造

Question

高速なcontains()メソッドを持つJavaのデータ構造を探していますが、追加して取得できるようにする必要があるため、おそらく何らかの順序付けが必要ですが、スタックのようにしたいですLIFO機能付き。これは可能ですか？私は、高速な contains() を持つ HashSet を考えましたが、順序は保証されていません。また、順序は保証されていますが、contains() は低速で​​す。

Answer 1

LinkedHashSet()部分的にそこに到達しますが、残念ながらLIFOを削除する良い方法を公開していません.

LinkedList<T>あなたが望むのは、 （LIFOの削除用）とHashMap<T, Integer>（カーディナリティの追跡用）をラップするものだと思います。次に、これらのメソッドがあります（非常に大まかに）：

public class QuickCheckStack<T> {

   private final Map<T, Integer> elementCardinality = new HashMap<T, Integer>;
   private final Deque<T> stack = new LinkedList<T>();

   public void push(T element) {
      Integer count = elementCardinality.get(element);
      if (count == null) {
          count = 0;
      }
      elementCardinality.put(element, count + 1);
      stack.push(element);
   }

   public T pop() {
      T element = stack.pop();
      elementCardinality.put(element, elementCardinality.get(element) - 1);
      return element;
   }

   public boolean contains(T element) {
      Integer count = elementCardinality.get(element);
      return count != null && !count.equals(0);
   }
}