Похоже, вам нужно обратное сопоставление, которое сопоставляет все значения с их набором ключей.
Map<Key,Value> forwardMap;
Map<Value, Set<Key> reverseMap;
Затем вы можете увидеть, все ли записи, которые вы просматриваете, находятся в наборе. Убедитесь, что вы добавили обратное сопоставление при добавлении / удалении прямого сопоставления.
Преимущество этого подхода в том, что тест будет O (n), где n - размер проверяемых ключей, а не O (m), где m - размер прямой карты.