HashMap<Integer,List<
String>> would store all the information of an employee (firstname,lastname,department,desig. etc) in a list identified by unique key SSN. I don't know whether just first name and last name needs to be stored but this approach will store values in structured way and retrieving would not be a problem.
in the choice 1 (add Employee) create a list for each SSN and then store it as
List <String>employee=new ArrayList<String>();
employee.add(firstName);
employee.add(lastName);
employee.add(...);
ssnKeys.put(SSN, employee);
This way while retrieving if you try ssnKeys.containsKey(SSN), it should return the whole list. Also maintaining methods(addEmployee(),deleteEmployee() etc.) for each of the options would be a good idea.