Normally, when working with dictionaries, we expect around O(1) complexity when we go to retrieve a value given the key (and when we insert). I work in Python, but this might apply to any dynamic typed language. I have been working with dictionaries where the keys are frozensets, which are just sets that are hashable and thus can be used as keys for your dictionary. I have a problem which would be magically solved if I could do "lookups" which are actually not key based, but set based. That is to say, it would be great if I had a data structure like a dictionary where I can pass in a set as a key and the data structure returns all values where the keys have a non-zero intersection with the key I passed in. I am quickly coming to the conclusion that this is never going to be O(1), but who knows. So, the question is, can we create a data structure that is basically a dictionary, but the keys are sets and it has a magic lookup ability where you can pass in a set and get all values back who's keys have non-zero intersection with the key (set) I passed in?
I imagined something to do with loading the values in. Firstly, you need keys that are sets of tuples (hashable). Then, when you load in a new value, you update the key to have a pointer to one other key and then these form long chains that do the job of getting you your sets of keys that meet the intersection criteria. This means that you push the complexity of insert way up, but lookup is fast. Apart from this, I have no idea, and I think a simple argument could be made that any such data structure will have either a bad O(N) insert or bad O(N) lookup, or both, where N is the number of keys.