Java: Search in HashMap keys based on regex?

I'm building a thesaurus using a HashMap to store the synonyms.

I'm trying to search through the words based on a regular expression: the method will have to take a string as parameter and return an array of results. Here's my first stab at it:

public ArrayList<String> searchDefinition(String regex) {
    ArrayList<String> results = new ArrayList<String>();

    Pattern p = Pattern.compile(regex);

    Set<String> keys = thesaurus.keySet();
    Iterator<String> ite = keys.iterator();

    while (ite.hasNext()) {
        String candidate = ite.next();
        Matcher m = p.matcher(candidate);
        System.out.println("Attempting to match: " + candidate + " to "  + regex);
        if (m.matches()) {
            System.out.println("it matches");
            results.add(candidate);
        }
    }   

    if (results.isEmpty()) {
        return null;
    }
    else {
        return results;
    }
}

Now, this does not work as I would expect (or maybe I'm using regular expressions incorrectly). If I have the following keys in the hashmap:

cat, car, chopper

then by calling searchDefinition("c") or searchDefinition("c*") I get null.

1. How do I make this work as expected?
2. Is there a better data structure than HashMap to keep a graph like needed by a thesaurus? (curiosity only, as for this assignment we're asked to use Java Collection Map).
3. Anything else I'm doing innapropriately in the code above?

Thanks, Dan

EDIT: I've corrected the example. It doesn't work even if I use the correct case.