-3

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?

4
  • 1
    Why not combine both lists into one object, providing specialized methods for iteration and key-lookup? Make the two lists an implementation detail. So you new-up an additional object. If you aren't doing this 1,000 times in a loop you should be fine. Nov 2 at 1:03
  • 1
    I'm not that familiar with Java but in C# I'd probably just use a Dictionary<T1,T2> which is Java is I believe a Hashmap<T1,T2>.
    – Turksarama
    Nov 2 at 1:13
  • Do you need the O(1) lookup of a Hashmap? An ordered list can have a O(log(n)) speed.
    – Pieter B
    Nov 2 at 8:23
  • 3
    Are you are telling us the complete story? When one speaks of key-values, I usually think of O(1) lookup for values by their keys, uniqueness of the keys, and maybe certain expectations for insert, replacement and deletion. Or do you just have arbitrary pairs in mind? Please clarify.
    – Doc Brown
    Nov 2 at 8:36

1 Answer 1

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?

1
  • 2
    +1 for the last paragraph. In fact, you could remove the first paragraph, because the second one stands on its own. As soon as you think a framework-level class is "inefficient", measure. Nov 2 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.