2D Dictionary or other data structure where order of keys doesn't matter

Question

I want to create a data structure that can take in a pair of keys (strings) and return a value (string as well). I would like to return the same value regardless of the order in which the 2 keys are entered (e.g. data[key1][key2] returns the same value as data[key2][key1]). Is there a term/concept for this description?

My current implementation is to create a 2D dictionary like this:

my_dict = {'key1': {'key1': None,
                    'key2': 'foo',
                    ...
                    'keyn': 'bar'},
           'key2': {'key1': 'foo',
                    'key2': None,
                    ...
                    'keyn': 'baz'},
           ...
           'keyn': {'key1': 'bar',
                    'key2': 'baz',
                    ...
                    'keyn': None}}

# Calling my_dict['key1']['key2'] and my_dict['key2']['key1'] both return 'foo', which is what I want and expect.

This doesn't seem right to me. I am duplicating data, and I am creating n * n entries when I only need (n * (n - 1))/2.

So, I tried creating a 1D Dictionary where the key is a tuple:

my_dict = {('key1', 'key2'): 'foo'}

But this doesn't work as calling my_dict[('key2', 'key1')] gives me a KeyError

One work-around for the 1D tuple Dictionary is to create a try/except.

def get_value(my_dict, key1, key2):
    try:
        return my_dict[key1][key2]
    except KeyError:
        return my_dict[key2][key1]

This doesn't seem intuitive and feels more like a 'band-aid' to the problem.

One method I haven't tested is a 1D Dictionary where the key uses an instance of a custom-defined class that holds key1 and key2 as attributes. In order to do this, the object would have to be nonmutable and hashable, where the hash function would use the object's attributes and produce the same "hash key" regardless of the order of attributes. I've never done this before and don't know how to do this. Is this the right way to go about it? I feel very stupid that I haven't been able to figure this out, as it seems like there is an easy answer to this.

Answer 1

If you want the keys to compare equal regardless of order, you could use frozensets as keys which fits in with your idea of a custom class:

my_dict = {frozenset(['key1', 'key2']): 'foo'}

Does not matter what order you add the keys:

In [44]: my_dict = {frozenset(['key1', 'key2']): 'foo'}

In [45]: k = frozenset(["key1","key2"])

In [46]: k2 = frozenset(["key2","key1"])

In [47]: my_dict[k]
Out[47]: 'foo'

In [48]: my_dict[k2]
Out[48]: 'foo'

You can have as many values in the frozenset as you want they will still compare equal, using a frozen set is also efficient for lookups:

In [55]: timeit my_dict[k]
10000000 loops, best of 3: 103 ns per loop

In [56]: timeit get_value(my_dict, 'key1', 'key2')
1000000 loops, best of 3: 455 ns per loop

In [57]: timeit get_value(my_dict, 'key2', 'key1')
1000000 loops, best of 3: 455 ns per loop

Even timing the frozenet creation and the lookup for two elements is faster:

In [5]: my_dict = {frozenset(['key1', 'key2']): 'foo'}

In [6]: timeit my_dict[frozenset(["key1","key2"])]
1000000 loops, best of 3: 380 ns per loop

For just 3 strings you have 3! perms to check, for 6 you have 720 so for anything more than a couple checking every possible permutation is not realistic or remotely efficient.