HashMap<String, Integer> Search for part of an key?

Iterate is your only option unless you create a custom data structure:

for (Entry<String, Integer> e : map.entrySet()) {
    if (e.getKey().startsWith("xxxx")) {
        //add to my result list
    }
}

If you need something more time efficient then you'd need an implementation of map where you are tracking these partial keys.

It seems like a use case for TreeMap rather than HashMap. The difference is that TreeMap preserves order. So you can find your partial match much quicker. You don't have to go through the whole map.

Check this question Partial search in HashMap

You cannot do this via HashMap, you should write your own implementation for Map for implementing string length based searching in a map.