See SortedMap, specifically All Known Implementing Classes.
Using TreeMap is probably not bad in your case:
SortedMap<String,CustomObject> map = new TreeMap<String,CustomObject>();
map.putAll( yourUnsortedMap );
On a side note, if you know your keys to be numeric, why not have the Map be of erasure <Integer,CustomObject>
instead?
Cheers,