If you declare your instance variable of type 'Map', you'll be using it in the rest of the code in a manner consistent with the Map interface. Therefore, if you wish at some later date to swap out the use of the HashMap implementation of Map for a more appropriate one, this can be done by simply changing your 'Map map = new HashMap();' line. Perhaps a TreeMap would be better for your code? Simple; change that line to be 'Map map = new TreeMap();'. Job done!
If you had used 'HashMap map = ..' instead, you'd be in danger of using any unique methods HashMap offers, so locking your code to this implementation.
Tim