This depends entirely on your app's requirements. What, exactly, are
your regexes doing? Can it be done more simply?

Some things to think about:

-- Jakarta ORO instead of the JDK 1.4 regex library. I have no idea if
it's any faster, but you could try it.

-- You may be better off using arrays of char, or one giant array of
char containing all strings, than the String class. String creates a lot
of garbage.

-- Make sure you compile your regexes in advance. Don't recompile before
each comparison.

-- Depending on your app, you might be able to use a lexer instead. See
http://www.jflex.de/. There's a learning curve, but it's *really* fast.

If you know the 100000 strings in advance, a simple
Map<String, String> with the strings as key and the function
value as value will probably fastest, and you only have to compute
the function values once.

If you are afraid of memory consumption, use a cache instead of a
simple map.

Just as a side-note, if you are comparing 100 strings a second using regexps,
and are seeing significant CPU load as a result, then (unless the strings are
very long) there must be something wrong with either the regexp implementation,
or the way you are using it (or perhaps both if the implementation is such that
it's forcing you to use it in the "wrong" way).

It should be possible to transform a task like this into a single DFA
(deterministic finite state machine) which will run in time proportional to the
length of the input string (not the complexity of the regexps).  The constants
of proportionality depend on the DFA implementation, but should not be /huge/
even for a naive implementation.  I would /hope/ that the Java regexp
implementation builds and uses such a DFA, but if not then the thing to do is
to do so yourself.  Probably the easiest way to do that is to use a
pre-existing scanner-generator, such as the jflex generator which has already
been mentioned.

   -- chris