Get a value from hashtable by a part of its key

Question

Hi. Say I have a Hashtable<String, Object> with such keys and values:

apple => 1
orange => 2
mossberg => 3

I can use the standard get method to get 1 by "apple", but what I want is getting the same value (or a list of values) by a part of the key, for example "ppl". Of course it may yield several results, in this case I want to be able to process each key-value pair. So basically similar to the LIKE '%ppl%' SQL statement, but I don't want to use a (in-memory) database just because I don't want to add unnecessary complexity. What would you recommend?

Update: Storing data in a Hashtable isn't a requirement. I'm seeking for a kind of a general approach to solve this.

Answer 1

Not without iterating through explicitly. Hashtable is designed to go (exact) key->value in O(1), nothing more, nothing less. If you will be doing query operations with large amounts of data, I recommend you do consider a database. You can use an embedded system like SQLite (see SQLiteJDBC) so no separate process or installation is required. You then have the option of database indexes.

I know of no standard Java collection that can do this type of operation efficiently.

Answer 2

Can't be done in a single operation

You may want to try to iterate the keys and use the ones that contain your desired string.

Answer 3

The obvious brute-force approach would be to iterate through the keys in the map and match them against the char sequence. That could be fine for a small map, but of course it does not scale.

This could be improved by using a second map to cache search results. Whenever you collect a list of keys matching a given char sequence, you can store these in the second map so that next time the lookup is fast. Of course, if the original map is changed often, it may get complicated to update the cache. As always with caches, it works best if the map is read much more often than changed.

Alternatively, if you know the possible char sequences in advance, you could pre-generate the lists of matching strings and pre-fill your cache map.

Update: Hashtable is not recommended anyway - it is synchronized, thus much slower than it should be. You are better off using HashMap if no concurrency is involved, or ConcurrentHashMap otherwise. Latter outperforms a Hashtable by far.

Apart from that, out of the top of my head I can't think of a better collection to this task than maps. Of course, you may experiment with different map implementations, to find the one which suits best your specific circumstances and usage patterns. In general, it would thus be

Map<String, Object> fruits;
Map<String, List<String>> matchingKeys;

Answer 4

The only solution I can see (I'm not Java expert) is to iterate over the keys and check for matching against a regular expression. If it matches, you put the matched key-value pair in the hashtable that will be returned.

Answer 5

Sounds like you need a trie with references to your data. A trie stores strings and lets you search for strings by prefix. I don't know the Java standard library too well and I have no idea whether it provides an implementation, but one is available here:

http://www.cs.duke.edu/~ola/courses/cps108/fall96/joggle/trie/Trie.java

Unfortunately, a trie only lets you search by prefixes. You can work around this by storing every possible suffix of each of your keys:

For 'apple', you'd store the strings

'apple' 'pple' 'ple' 'le' 'e'

Which would allow you to search for every prefix of every suffix of your keys.

Admittedly, this is the kind of "solution" that would prompt me to continue looking for other options.

Answer 6

first of all, use hashmap, not hashtable.

Then, you can filter the map using a predicate by using utilities in google guava

public Collection<Object> getValues(){
    Map<String,Object> filtered = Maps.filterKeys(map,new Predicate<String>(){
        //predicate methods
    });
    return filtered.values();
}

Answer 7

If you can somehow reduce the problem to searching by prefix, you might find a NavigableMap helpful.

Answer 8

it will be interesting to you to look throw these question: http://stackoverflow.com/questions/327513/fuzzy-string-search-in-java

Also take a look on Lucene (answer number two)