2

I have to implement a set ADT for a pair of strings. The interface I want is (in Java):

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

The data access pattern has the following properties:

  1. The contains operation is far more frequent that the add and remove ones.
  2. More often that not, contains returns true i.e. the search is successful

A simple implementation I can think of is to use a two-level hashtable, i.e. HashMap<String, HashMap<String, Boolean>>. But this datastructure makes no use of the two peculiarities of the access pattern. I am wondering if there is something more efficient than the hashtable, maybe by leveraging the access pattern peculiarities.

Improve this question
2
  • How large do you expect the data-structure to be? Commented Nov 4, 2011 at 7:28
  • It would be in the order of tens of thousand, and each string would be about 50 characters, say. Commented Nov 4, 2011 at 7:42

4 Answers 4

Reset to default
3

Personally, I would design this in terms of a standard Set<> interface:

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; }

Then you could leave it up to the user of StringSetImpl to use the preferred Set type. If you are attempting to optimize access, though, it's hard to do better than a HashSet<> (at least with respect to runtime complexity), given that access is O(1), whereas tree-based sets have O(log N) access times.

That contains() usually returns true may make it worth considering a Bloom filter, although this would require that some number of false positives for contains() are allowed (don't know if that is the case).

Edit

To avoid the extra allocation, you can do something like this, which is similar to your two-level approach, except using a set rather than a map for the second level:

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; }

Since it's 4:20 AM where I'm located, the above is definitely not my best work (too tired to refresh myself on the treatment of null by these different collections types), but it sketches the approach.

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

I would prefer to avoid allocation of a pair object in the contains method.
Bloom filters optimize for memory; in my case I am OK with storing the entire set in memory.
@BinilThomas, ok, in that case, I would go with HashSet then.
@BinilThomas, these allocations are cheaper than you may think.
Agreed that the allocation is cheap; also it might not affect the minor GC pause times. But it will definitely affect the frequency of minor GCs. In my case, contains is called so often in a background thread that the frequent minor GCs might alter the GC characteristics of the application significantly.
|
0

Do not use normal trees (most standard library data structures) for this. There is one simple assumption, which will hurt you in this case:

The normal O(log(n)) calculation of operations on trees assume that comparisons are in O(1). This is true for integers and most other keys, but not for strings. In case of strings each comparison is on O(k) where k is the length of the string. This makes all operations dependent on the length, which will most likely hurt you if you need to be fast and is easily overlooked.

Especially if you most often return true there will be k comparisons for each string at each level, so with this access pattern you will experience the full drawback of strings in trees.

Your access pattern is easily handled by a Trie. Testing if a string is contained is in O(k) worst case (not average case as in a hash map). Adding a string is is also in O(k). Since you are storing two strings I would suggest, you don't index your trie by characters, but rather by some larger type, so you can add two special index values. One value for the end of the first string, and one value for the end of both strings.

In your case using these two extra symbols would also allow for simple removal: Just delete the final node containing the end symbol and your string will not be found anymore. You will waste some memory, because you still have the strings in your structure that have been deleted. In case this is a problem you could keep track of the number of deleted strings and rebuild your trie in case this get's to bad.

P.s. A trie can be thought of as a combination of a tree and several hashtables, so this gives you the best of both data structures.

Improve this answer

3 Comments

Yes, I agree with you on the point about hashcodes. In my specific case, though, there might be an additional peculiarity - the same strings are often passed in as argument to contains. So although the hashing takes O(k) time to compute, since java.lang.Strings cache their hash codes, I might be able to think of it as amortized O(1). The strings I have to store have common prefixes, so a trie is one of the structures I am considering. This paper - goanna.cs.rmit.edu.au/~jz/fulltext/acsc02hz.pdf - suggests that hashtable might be better in practice, though.
@BinilThomas: A good read indeed. I learned a lot from that on the actual problems of these kinds of datastructure in practice, as opposed to in theoretical calculations (where you do not have a cache or pointers).
I ended up writing a chained hashtable as explained in the paper with the following peculiarities (1) the hash function is a add-shift of the individual string hashes (which I assume is cached) (2) contains operation moves a found entry to the front of the bucket linked list. I tested and found it to be the best performing implementation.
0

I'd second the approach of Michael Aaron Safyan to use a StringPair type. Perhaps with a more specific name, or as a generic tuple type: Tuple<A,B> instantiated to Tuple<String,String>. But I would strongly suggest to use one of the provided set implementations, either a HashSet or a TreeSet.

Improve this answer

6 Comments

The allocation needed to box the strings to tuple is something I am very keen to avoid.
That would have been an important information to begin with! But using two stacked hash maps will use way more memory. If you are interested in the lowest possible memory consumption try to use a pair of arrays, or a pair of ArrayList<String>. And use the invariant that corresponding strings should be at the same index. Nevertheless, I'd use the original Set interface.
Sorry, I did not explain it well. I am ok with some extra memory overhead in storage (entry objects, bucket chains etc, for example); but when contains is called, I do not want to allocate a Tuple, so that it can be searched for in the set.
So, you are more concerned about the costs of allocating and or freeing the tuple object? If so, keep in mind that in a generational/copying garbage collection setting, like in a decent JVM, allocation is pretty much for free, and deallocation becomes cheaper if you free an object earlier. A very short lived object is deallocated basically for free. Keeping an object live costs in garbage collection, not freeing it.
I agree with most of what you said about allocation; but cheap is not the same as free :) Let me try to illustrate. The code I have to write is a small component that resides alongside another bigger application. My contains calls are done in a background thread, but at a high rate. If I allocate a small object for each such call, although a single allocation is cheap, it can all soon add up to cause adverse effects.
|
-1
  1. Red-Black Tree implementation of the set would be a good option. C++ STL is implemented in Red-Black Tree
Improve this answer

1 Comment

-1: This does not make use of the conditions the OP described.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.