Is it possible to build regex-based-map with search asymptotically faster then hashmap?
One possible approach is to store the keys in a trie, convert the regex to a DFA (remove all useless states from it and optionally minimize it), and then use that to search the trie.
In particular, you can construct a recursive algorithm for traversing the trie.  The root of the trie is associated with the start state of the DFA.  For each edge out of the root, you look at the letter on that edge, advance the DFA to the appropriate state, and associate that state with the corresponding child.  If it causes the DFA to reject, then you can prune exploration of that node in the trie.  In this way, each node in the trie gets associated with a state of the DFA, you recursively explore the trie, pruning when you hit dead ends, and if you hit a leaf in the trie, if the DFA is in an accept state at that point, you have found a match.
However the running time to convert a regex to a DFA can take exponential time.  Also this only works with language-theoretic regular expressions, not Perl- or POSIX-style regexps, which are more expressive and cannot be converted to a DFA.  So, whether this will be attractive might depend on your application.