This week's book giveaway is in the OCAJP 8 forum. We're giving away four copies of OCA Java SE 8 Programmer I Study Guide and have Edward Finegan & Robert Liguori on-line! See this thread for details.
If duplicate keys are allowed, it's not a key. You're never going to be able to find anything even if you had a collection. If your true requirements provide for "keys" with multiple values, you'll have to iterate through the whole structure anyway to find all possible values.
If that's the case and you know from the start the maximum number pairs you will have, see if use can a two-dimensional array.
Another option is to incorporate your "key" and value into a new Object type. Then make that the value to a true key signature.
Another option might be to have a Collection as the value associated with a key. Then when you have another key value pair with the same key, you could add that value to the Collection associated with the key.