Такой вопрос недавно задали на интервью - а я растерялся и не смог дать ответ (видимо правильного не смог дать)

В чем существенное отличие HashMap и HashSet?

Единственное что я назвал это то что HashMap имплементит интерфейс Map, который не имплементит Collection; в то же время когда HashSet имплементит Set, который (вместе с List) имплементит Collection интерфейс.
Таким ответом остались недовольны. Мне в голову ничего не приходит абсолютно.
Что еще это может быть? Оба хранят данный по key-value, оба не гарантируют соблюдения порядка элементов, оба не syncronized, оба не дают иметь duplicate keys, оба разрешают лишь один null элемент как key.

Что ж еще?
Честно и сам путаюсь когда использовать тот, когда тот.

Никто не подскажет из знающих тут?