Match wildcard key parameter

Question

I have a large number of Key-Value parameters that appear in the file path. Most of them are as follows

filepath : /some/path param_name_1 => 1234 param_name_2 => qwerty 

But others may contain wildcards

 filepath : /other/path param_name_1 => 123*4 param_name_2 => ab?12 

Where ? is a wildcard that matches any one character, and * is a wildcard that matches 0 + characters.

My users can provide their own set of KV parameters that I need to map and return the displayed path.

Example: User provides

 param_name_1 => 1234 param_name_2 => qwerty Application returns /some/path 

User provides

 param_name_1 => 123asdqweqweqdqweq1231asdcase4 param_name_2 => abW12 Application returns /other/path 

For all mappings that do not contain wildcards, I can calculate hashCode() for my saved mappings and for the one provided by the user and search for a HashMap that is extremely fast (3-4 options for matching, 100000 mappings, in 0 milliseconds, this is a hash eventually).

For mappings containing patterns, I’m kind of stuck in doing linear searches through a list of all mappings containing wildcards. There are about 2000-5000 such comparisons, and each search takes a little less than 200 milliseconds, and I need to speed it up.

Is there a way I can do a general search to match wildcards or other match methods that combine all the mappings?

Answer 1

If you use TreeMap instead of HashMap , you can do a prefix search to reduce the number of elements you need to iterate over. Just take the characters that appear before * or ? , and repeat all keys starting with these characters. This will not work, of course, if your search query starts with a template.

Another common approach to this problem is to use the ngrams symbol or some trie based structure, but it is much more complicated.