Data structure for efficient group lookup I need a data structure, which allows efficient queries for 'give me the group of x'.
Let me give you an example:
Group 1: [a, b, c] 
Group 2: [d, e]
Group 3: [f]

getGroupOf(d) -&gt; [d, e]

There are no significant constraints on storage or construction time. I only need getGroupOf to be O(logn) or faster.
I am thinking about using a Dictionary&lt;Element, Set&lt;Element&gt;&gt; where entries for all elements in a group share the same set reference. This would make lookup effectively O(1) or O(logn) depending on the dictionary implementation, but would result in a lot of entries.
This feels fairly bloated, and I am wondering: is there is a more elegant data structure to accomplish this?
Edit: the elements in a group can be completely arbitrary and they have no ordering.
If the groups are static, your data structure is perfectly reasonable.
You can also consider the Union-Find data structure.  Find is the getGroupOf operation.  It is quite fast, and also allows you to modify the data structure by merging groups and adding a new item in its own group.