Если общее количество пар невелико, переходите к простому: карта от первого ключа до второй карты; вторая карта переходит от второго ключа к значению.
Если общее количество пар велико, производительность может иметь значение. Если это так, я бы предложил то же решение, что и выше, но в качестве первого ключа выберите тот, который имеет наименьший ожидаемый диапазон (например, если первый ключ - одно из тысяч имен, а второй - один из десяти предварительно определенных состояний , пусть второй ключ будет первым, который вы ищите).
Если производительность не имеет значения, переходите к прозрачности дизайна: используйте класс Pair в качестве ключа на одной карте. (Класс Pair достаточно полезен, так что к настоящему моменту у вас, вероятно, уже должен быть хорошо написанный.)