I wonder how one would go about efficiently implementing such an associative array.

I suppose a trie + glue logic (regexp -> NFA -> DFA) could work, for classic (read: actually regular expressions) regexps at least.