A Regular Expression HashMap Implementation in Java

Since your are extending hashmap; list of regExPatterns  and regExValues  are not needed. why don't you call superior put with the compiled key and value. this would also simplify the matching get.

in fact this is a must. currently you are discarding map interface with this implemantation. what if i call remove method...

This is a terrible implementation of a map.

1. You call it RegExHashMap but there is no hashing involved. Using the word hash should mean it has performance of O(1) but your's has performance of O(N).

2. Your put method does not call super.put() so all of the other methods on map (remove, size, putAll, values, entrySet etc) don't work. You would be better to implement java.util.Map and throw UnsupportedOperationException() for all other methods than what you are doing here.

3. Why not RegExHashMap<V> extends HashMap<CharSequence, V>?

4. new String(key.toString()). Please explain what new String achieves (string is immutable)

5. Your two lists are not needed if extending HashMap

6. Your implementation allows multiple entries with the same key

7. Your implementation throws NPE for null keys

I could go on and on... 

Given that we're commenting regex maps, I've been using another home-made since a few time. It works for my specific projects that needs it, but I never validated it against the Map contract. I'd like to get some feedback just while you're still hot about the topic ;-). It is not optimized with pattern compilation, but it does super.put() and has a shortcut for gets whose arg is not a regexp (which in my use cases happens 80% of the time). My impression is that designing an implementation that is optimized for a lot of generic cases *and* it complies with Map contract is a hard task. 

public class RegexTreeMap<Type> extends TreeMap<String, Type>
  {
    @Nonnull
    public static String escape (final @Nonnull String string)
      {
        final StringBuilder builder = new StringBuilder();

        for (int i = 0; i < string.length(); i++)
          {
            final char c = string.charAt(i);

            if ("[\\^$.|?*+()".contains("" + c))
              {
                builder.append('\\');
              }

            builder.append(c);
          }

        return builder.toString();
      }

    @Override
    public Type put (final @Nonnull String string, final Type value)
      {
        return super.put(Pattern.quote(string), value);
      }

    public Type putRegex (final @Nonnull String regex, final Type value)
      {
        return super.put(regex, value);
      }

    @Override
    public Type get (final @Nonnull Object value)
      {
        final String stringValue = (String)value;
        Type result = super.get(Pattern.quote(stringValue)); // first try a direct match that is fast
        int matchLength = 0;

        if (result == null) // otherwise returns the longest match
          {
            for (final Entry<String, Type> entry : super.entrySet())
              {
                final String regex = entry.getKey();

                if (stringValue.matches(regex) && (regex.length() > matchLength))
                  {
                    result = entry.getValue();
                    matchLength = regex.length();
                  }
              }
          }

        return result;
      }
  }

Andrew Gilmartin: I think that combining all of the regexes into a single regex (or'red together) will just end up with the same O(N) performance but in a single regex rather than looping muiltiple regexes.

It's pretty hard to get rid of the O(N) performance for this very general RegexMap. To improve performance, I think you would need to think about your incoming data and then try to group your regexes in buckets. You could then use a hash lookup for the bucket.

For example, you might use the first three characters to lookup the bucket.

Another example is for a URL, you might choose to split the input URL's on "/" and have a tree hierarchy of regexes that only apply to a single level at a time (instead of multiple regexes that work on the entire URL). I'm sure that SpringMVC has a solution to this, I wonder how they have done it?