String on its own is inefficient class. There is extra pointer, int field... ASCII strings are not downgraded from char[] to byte[]... You get big performance bonus just by replacing String with raw byte[].
I wrote Map<String,String> which does this transparently, and it consumes about 5x less memory compared to HashMap<String,String>.