Да, как предлагает andrew007, вы можете использовать MultiKey. Хотя, если бы я был тобой, я бы реализовал свой собственный класс, назову его чем-то вроде BiKey или даже чем-то более значимым. Одна из причин в том, что MultiKey не генерируется.
Подводя итог, почему вы не делаете что-то вроде:
ConncurrentMap<BiKey,Stuff> map = new ConcurrentHashMap<BiKey,Stuff>();
class BiKey{
Key1 k1;
Key2 k2;
//let equals return k1.equqls&&k2.equals and implement hashCode accordingly
}
ConcurrentHashMap действительно хорошо масштабируется, и в нем есть несколько полезных операций, которые могут пригодиться.