Table data structure for quick searching with wildcards

Question

I am storing a relatively small amount (perhaps may be larger in the future) and then searching it but this is proving to be a bit of a bottleneck in my project.

To expand I have up to a few thousand rows and a few columns. I wish to be able search with the ability to specify a simple match with match all wildcards for any element. All the insertion can take place at construction, ideally duplicates wouldn't exist and the amount of querying outweighs table construction quite considerably. I also need to be able to compare tables to see if the contain the same elements (differences between them aren't needed). Objects that are stored can be hashed but are not ordered. This is all stored in memory.

So initially I started with a simple hashset:

   Set<ArrayWrapper> data = new HashSet<ArrayWrapper>();

where ArrayWrapper is a simple wrapper for an Object[]. This obviously is slow for searching with wildcards, e.g. {new Integer(3), null, "Test", null} where null means match anything. I added an index for the least wildcarded value which helps but I feel there may be a better solution?

Answer 1

Take a look at tries. The look-up isn't quite as fast as a hashset when you don't have any wildcards, but it allows wildcards and is still quite fast.

Answer 2

@Justin - building off you answer, I believe this could be implemented using map of maps. @Molehill - Is the number of keys used defined? or is it variable?

If it's defined (for example 3: Integer, String, String) you could do Map<Integer, Map<String, Map<String, Object>>>. When you have a wild card in your search, then you would have to poll through the entire entrySet or value collection of the map that you're at. You could get fancy and write an abstraction around that though. I recently did this for a 2 key map.