Stack and Hash joint

Question

I'm trying to write a data structure which is a combination of Stack and HashSet with fast push/pop/membership (I'm looking for constant time operations). Think of Python's OrderedDict.

I tried a few things and I came up with the following code: HashInt and SetInt. I need to add some documentation to the source, but basically I use a hash with linear probing to store indices in a vector of the keys. Since linear probing always puts the last element at the end of a continuous range of already filled cells, pop() can be implemented very easy without a sophisticated remove operation.

I have the following problems:

• the data structure consumes a lot of memory (some improvement is obvious: stackKeys is larger than needed).
• some operations are slower than if I have used fastutil (eg: pop(), even push() in some scenarios). I tried rewriting the classes using fastutil and trove4j, but the overall speed of my application halved.

What performance improvements would you suggest for my code? What open-source library/code do you know that I can try?

Answer 1

I think that what you want is (almost) already available in the libraries: LinkedHashSet is a hash-set with an underlying doubly linked list (which makes it iterable). LinkedHashMap even has a removeEldestEntry which sounds very similar to a pop-method.

How is the performance of a naive solution like:

class HashStack<T> {

    private HashMap<T, Integer> counts = new HashMap<T, Integer>();
    private Stack<T> stack = new Stack<T>();

    public void push(T t) {
        stack.push(t);
        counts.put(t, 1 + getCount(t));
    }

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

    private int getCount(T t) {
        return counts.containsKey(t) ? counts.get(t) : 0;
    }

    public boolean contains(T t) {
        return getCount(t) > 0;
    }

    public String toString() {
        return stack.toString();
    }
}

Answer 2

I would suggest using TreeSet<T> as it provides guaranteed O(log n) cost for add, remove, and contains.

Answer 3

You've already got a pretty good implementation. The only improvement obvious to me is that you do more work than you need to by searching when popping. You should store in the stack not the key itself but the index into the key array. This gives you trivially fast pops at the expense of only one more pointer indirection when you want to peek the last item.

Just size your stack to LOAD_FACTOR*(heap array size), in addition to that, and you should have about as fast an implementation as you could expect with as little memory as you can manage given your speed requirements.