C++/JAVA: Efficiently find a set in the collection containing given value

Question

Suppose that we have a collection of mutually exclusive sets
    {A,B,C,D} where A = {1,2,3}, B = {4,5,6}, C = {7,8,9}, D = {10,11,12}
And given a value Z, for example of 3, I expect it to return the index of set A, because A has 3 as its member.

The question is that how could I do it efficiently using C++ or JAVA.

My current solution: Store the A,B,C,D as a HashSet (or unordered_set in C++) in the container and loop through each set until a set containing Z is found.
    The problem is that the complexity is O(n) for the amount of sets stored in the container.

Is there any way (or any data structure to store those sets) to do that faster than O(n)?

Answer 1

You can create a map that maps a value to set id(for example it should map 1, 2, 3 to A, 4, 5 and 6 to B and so on). With a hash map, it can work in O(1) on average.