What's the right data structure to combine iteration of key-value pairs, and iteration of values

Question

I'm looking for a pre-existing or easy-to-build data structure available in Java, which can do these 2 things efficiently:

• Fetch all the values stored in the collection quickly.
• Iterate over the data structure to fetch each key and its value.

Right now, I'm using a Pair<List, List>.

With this, I can

• Fetch all values stored in collection using pair.getRight() which gives me the entire List. O(n) + cache locality
• Iterate using for(0 to size), pair.getLeft(), pair.getRight() which gives me the key and the value each time. O(n) + some cache locality

This works fine, but it feels ugly to be passing around a pair of 2 lists and having this key value relationship between those lists.

If I just use a regular HashMap, I would have to iterate over the map instead of the list, which is inefficient due to the random memory access.

I could treat combine the key+value into 1 object, and pass around a List instead. This seems cleaner, but at the cost of creating a temporary and unnecessary object.

Can I retain this performance and somehow use a better data structure?

Answer 1

This honestly sounds like something I would use a HashMap for. Map.values() will return a collection containing all the values, and you can use .foreach((key, value) -> {...}) on the map to iterate over key-value pairs.

When you say the HashMap is "inefficient" my first question is have you actually tried it? Have you done any benchmarking? Or have you even just tried deploying a version using a HashMap and observed that it isn't performant enough? Is your input size large enough for the random vs. contiguous memory access to truly matter?