# A dictionary that allows multiple keys for one value

I'm trying to learn to program on my own with the help of books and the Internet and thought I'd start a project (a sub-project for a project).

I want to build a dictionary that allows multiple keys for one value:

d = mkdict()
d['what', 'ever'] = 'testing'
d['what'] is d['ever'] # True


I thought it would be good to get some advice from other programmers to better myself, and so I would like it if you were to give your honest opinion on how I've implemented it (the dos and don'ts) and possibly how you would approach things.

# -*- coding: utf-8 -*-

class mkdict(object):
""" A dictionary that allows multiple keys for one value """

class _Container(object):
""" This is used to wrap an object to avoid infinite
recursion when calling my own methods from the inside.

If a method sees this container, it assumes it has been
called from the inside and not the user.
"""

def __init__(self, _object):
self.object = _object

class dict(object):
""" Interface for mkdict.dict for dict-like behaviour """

def __init__(self, d={}, **kwargs):
""" Using an mkdict._Container to avoid infinite
recursion when allowing:

>>> d = mkdict({'what': 'ever'})
>>> d = mkdict.dict({'what': 'ever'})
"""
if isinstance(d, mkdict._Container):
self.mkdict = d.object
else:
self.mkdict = mkdict(mkdict._Container(self))
self.update(d, **kwargs)

def __str__(self):
return str(self.mkdict._dict)

def __repr__(self):
return str(self)

def __len__(self):
return len(self.mkdict._dict)

def __setitem__(self, key, value):
""" Desired behaviour:

>>> d = mkdict()
>>>
>>> d['what', 'ever'] = 'testing'
>>> d
{'what': 'testing', 'ever': 'testing'}
>>> d.dict
{('what', 'ever'): 'testing'}
>>> d['what'] is d['ever']
True
>>>
>>> d.dict['what'] = 'new value'
>>> d
{'what': 'new value', 'ever': 'testing'}
>>> d.dict
{'what': 'new value', 'ever': 'testing'}
>>> d['what'] is d['ever']
False
"""
if key not in self and key in self.mkdict:

self.mkdict[key] = value

def __getitem__(self, key):
return self.mkdict._dict[key]

def __contains__(self, key):
return key in self.mkdict._dict

def __delitem__(self, key):
if key not in self:
raise KeyError(key)

if isinstance(key, tuple):
key = key[0]

del self.mkdict[key]

def clear(self):
self.mkdict.clear()

def update(self, d, **kwargs):
if isinstance(d, mkdict.dict):
d = d.mkdict._dict
elif isinstance(d, mkdict):
d = d._dict

d.update(kwargs):
for k, v in d.items():
self[k] = v

class _FullKeyPtr(object):
""" Desired behaviour:

full_key_ptr1 = _FullKeyPtr()
mkdict._key_map -> {'key1', full_key_ptr1,
'key2', full_key_ptr1}

>>> d = mkdict()
>>> d['what', 'ever'] = 'testing'
>>> d._key_map
>>>
>>> # d._key_map:
>>> # {'what': full_key_ptr1, 'ever': full_key_ptr1}
>>> d._key_map
>>> {'what': ('what', 'ever'), 'ever': ('what', 'ever')}
>>>
>>> d['what']
>>> 'testing'
>>>
>>> # full_key = _key_map['ever'].full_key
>>> # i.e. full_key = ('what', 'ever')
>>> # _dict[full_key] = 'test'
>>> d['ever'] = 'test'
>>>
>>>
>>> d['what']
>>> 'test'
"""

def __init__(self, full_key):
self.full_key = full_key

def __str__(self):
return str(self.full_key)

def __repr__(self):
return str(self)

def __init__(self, d={}, **kwargs):
self._dict = dict()
self._key_map = dict()
self._dict_backup = None
self._key_map_backup = None

if isinstance(d, mkdict._Container):
self.dict = d.object
else:
self.dict = mkdict.dict(mkdict._Container(self))
self.update(d, **kwargs)

def __str__(self):
return str(dict(self.items()))

def __repr__(self):
return str(self)

def __len__(self):
return len(self._key_map)

def __iter__(self):
return iter(self.keys())

def __getitem__(self, key):
full_key = self.full_key(key)
return self.dict[full_key]

def __setitem__(self, key, value):
""" Desired behaviour:

>>> d = mkdict()
>>> d['what', 'ever'] = 'testing'
>>>
>>> d
{'what': 'testing', 'ever': 'testing'}
>>>
>>> d.dict
{('what', 'ever'): 'testing'}
>>> d['what'] is d['ever']
True
>>>
>>> d['what'] = 'new value'
>>> d
{'what': 'new value', 'ever': 'new value'}
>>>
>>> d.dict
{('what', 'ever'): 'new value'}
>>> d['what'] is d['ever']
True
"""
if key in self:
key = self.full_key(key)

if key not in self._dict:
if isinstance(key, tuple):
full_key_ptr = self._FullKeyPtr(key)
for k in key:
if k in self:
self._key_map[k] = full_key_ptr
else:
self._key_map[key] = self._FullKeyPtr(key)

self._dict[key] = value

def __delitem__(self, key):
full_key = self.full_key(key)

if isinstance(full_key, tuple):
for k in full_key:
del self._key_map[k]
else:
del self._key_map[full_key]

del self._dict[full_key]

def __contains__(self, key):
return key in self._key_map

def items(self):
return [(k, self[k]) for k, v in self._key_map.items()]

def iteritems(self):
return iter(self.items())

def update(self, d={}, **kwargs):
if isinstance(d, mkdict.dict):
d = d.mkdict._dict
elif isinstance(d, mkdict):
d = d._dict

d.update(kwargs)
for k, v in d.items():
self[k] = v

def clear(self):
self._dict.clear()
self._key_map.clear()

def keys(self):
return self._key_map.keys()

def full_key(self, key):
return self._key_map[key].full_key

def has_key(self, key):
return key in self

def append(self, key, otherkey):
pass

def remove(self, key):
full_key = self.full_key(key)

if not isinstance(full_key, tuple):
del self._dict[full_key]
del self._key_map[full_key]
return

new_full_key = list(full_key)
new_full_key.remove(key)

if len(new_full_key) == 1:
new_full_key = new_full_key[0]
else:
new_full_key = tuple(new_full_key)

self._dict[new_full_key] = self.dict[full_key]
del self._dict[full_key]
self._key_map[key].full_key = new_full_key
del self._key_map[key]

def aliases(self, key):
full_key = self.full_key(key)
if isinstance(full_key, tuple):
aliases = list(full_key)
aliases.remove(key)
return aliases
return list()

def backup(self):
pass

def revert(self):
pass

self.remove(key)


I've been having a lot of infinite recursion problems because of the following desired behaviour:

>>> d = mkdict()
>>> d = mkdict.dict()
>>>
>>> d = mkdict()
>>> d
{}
>>> d.dict
{}
>>>
>>> d['what', 'ever'] = 'test'
>>> d
{'what': 'test', 'ever': 'test'}
>>> d.dict
{('what', 'ever'): 'test'}
>>> d['what'] is d['ever']
True
>>>
>>> d['what'] = 'testing'
>>> d
{'what': 'testing', 'ever': 'testing'}
>>> d.dict
{('what', 'ever'): 'testing'}
>>>
>>> d.dict['what'] = 'new value'
>>> d
{'what': 'new value', 'ever': 'testing'}
>>> d.dict
{'what': 'new value', 'ever': 'testing'}
>>> d['what'] is d['ever']
False


I don't like the way I've dealt with this infinite recursion problem because, to me, the code looks messy and unmaintainable.

Could I please have some advice on where to go with this project?

if advice:
print 'Thank you!'
else:
print 'Ok, no problem'

• Your desired behaviour is not clear. Is it a sequence of steps that you have given? If yes then doing d['what', 'ever'] = 'test' is doing what? I am asking this because the comments seem to be showing no change after it is done. – Aseem Bansal Apr 4 '15 at 12:09
• Please add the code to be reviewed in the question. – Janne Karila Apr 4 '15 at 12:49
• @ratherlargeguy - Please see, and follow the help page on merging accounts – rolfl Apr 4 '15 at 14:54
• Isn't it pretty normal for a dictionary to already allow multiple keys to have the same value? Is this not how Python dictionaries work...? – nhgrif Apr 5 '15 at 15:03
• @nhgrif No, Python dictionaries don't support multiple keys for the same value. – Ethan Bierlein Jul 2 '15 at 22:12

I want to build a dictionary that allows multiple keys for one value:

# This is a very basic relational database.

So the first piece of feedback is that new programmers often start coding with poorly defined test-cases or non-normalised test-cases whereby they get lost developing their test portfolio. If you would have started with clarifying your case, I'm sure you would have cracked this problem.

# Let's start defining our operations from examples

Sometimes we will have the database maintaining links:

• from 1 key to 1 value
• from 1 key to N values
• from N keys to 1 value
• from N keys to N values

A dictionary can hold 1 key to N values, but not N keys to 1 value.

Fortunately the reverse operation of N keys to 1 value is the reverse of the dictionary, so we can trick around this by creating a class:

class Database(object):
""" A dictionary that allows multiple keys for one value """

def __init__(self):
self.keys = {}
self.values = {}


Next we need figure out how to get data into the database. This is similar to the SQL INSERT STATEMENT, where we maintain both our keys and values in single transactions:

def __setitem__(self, key, value):


Lets first insert a new key, whilst keeping in mind that the value might already exist:

    if key not in self.keys:
if value not in self.values:  # it's a new value
self.keys[key] = set()  # a new set
self.values[value] = set()  # a new set
elif value in self.values:
self.keys[key] = set()  # a new set


(1) a new key to a known value only means an update to the values.

Next we worry about if it's a new relationship with a new value:

    elif key in self.keys:  #
if value not in self.values:
self.values[value] = set()
elif value in self.values:


We have now implemented the INSERT STATEMENT in our database.

Now it's time to worry about how to delete records and relationships. For this we hack the __delitem__ function to both take a key and a value. Why? Because otherwise we won't know whether the user wants to delete a single relationship only, OR all entries associated with the key

I thereby choose that:

• if the value is None I delete every relationship associated with the key.
• if the value is a valid relationship between the key and value, then I only delete that specific relationship.

This is how it works:

def __delitem__(self, key, value=None):
if value is None:
# All the keys relations are to be deleted.
try:
value_set = self.keys[key]
for value in value_set:
self.values[value].remove(key)
if not self.values[value]:
del self.values[value]
del self.keys[key]  # then we delete the key.
except KeyError:
else:  # then only a single relationships is being removed.
try:
if value in self.keys[key]:  # this is a set.
self.keys[key].remove(value)
self.values[value].remove(key)
if not self.keys[key]:  # if the set is empty, we remove the key
del self.keys[key]
if not self.values[value]:  # if the set is empty, we remove the value
del self.values[value]
except KeyError:


Now we can add and delete. But how about bulk updates? They constitute a special case because __setitem__ can't see that you want to propagate your update onto multiple values. So we need to tell it WHAT to update. Here is a proposal that uses the relationship between the key, the old value and the new value that should be accessible to all keys that other would have a relationship with the old value:

def update(self, key, old_value, new_value):
if old_value in self.keys[key]:
affected_keys = self.values[old_value]
for key in affected_keys:
self.__setitem__(key, new_value)
self.keys[key].remove(old_value)
del self.values[old_value]
else:
raise KeyError("key: {} does not have value: {}".format(key,old_value))


So far so good. A slightly annoying thing is that we can't really read what is in the database even though we can get things in and delete them. This calls for the SELECT STATEMENT - or python's __getitem__ method. But(!) we need to be careful, as our database stores data internally as a sets that are accessible from keys. So we need to unpack them onto something useful. As I like working with lists, I have chosen to provide lists, unless its a single value, whereby I only return the value itself:

def __getitem__(self, item):
values = self.keys[item]
if len(values) > 1:
return sorted(list(values))
elif len(values) == 1:
return list(values)[0]


Now we just miss one thing to pass all your test: The bulk loading method where you map N keys to M values. This is a "cartesian" product, which is a fancy word all N's maps to all M's. In Python this is a walk in the park as we can iterate over both and reuse our __setitem__ method:

def iterload(self, key_list, value_list):
for key in key_list:
for value in value_list:
self.__setitem__(key, value)


At this point we have implemented:

• A class for our database
• A "select" method that is compatible with python d[key]
• An "insert" method that is compatible with python d[key] = value
• An "update" method that maintains the relationship to multiple keys.
• A "delete" method that can both delete a relationship and all entries associated with a key.

## Testing

Now I need to test this.

First we load a single key:value pair, where the key is a hashable structure. I chose a tuple with 3 integers:

def test01()
# hashable key - a tuple
d = Database()
k, v = (1, 2, 3), 'magic'
d[k] = v
print(d)
print(d[k])


That works fine as we can see our database object and the value

    # print(d)
<__main__.Database object at 0x7fd9c3d17048>

# print(d[k])
magic


Next we can test our bulk-load method: iterload together with the "many keys - shared value" which is focal in your problem:

def test02():
# non-hashable key - a list - becomes a many-key shared value
d = Database()
keys, value = [1, 2, 3], ['magic']
assert d[1] == d[2] == d[3]


This also works as our assertion in the last line doesn't complain: The value of d[1]...d[3] are the same: The text string magic

I add two more tests, which should look very familiar to you, though with minor exceptions:

def test03():
d = Database()
k, v = ['what', 'ever'], ['test']
assert d['what'] == d['ever']
d['what'] = 'testing'
try:
assert d['what'] == d['ever']
except AssertionError:
assert True


In test03 I need to pack the value into a list, because iterload needs two iterables. I could made my code much harder to read by accounting for many different cases, but I think the programmer should build a function for one thing and make it clear for future recall of what the function is supposed to do.

In test04 - below - I have added the usage of the update function.

def test04():
d = Database()
v = 'test'
keys, values = ['what', 'ever'], [v]
d['whatever'] = 'test'
assert v == d['whatever']
assert v == d['what']
assert d['whatever'] == d['what']
d.update('whatever', 'test', 'new test')
a, b = d['whatever'], d['what']
assert a == b


# Everything Together

Here you go:

__author__ = 'root-11'

class Database(object):
""" A dictionary that allows multiple keys for one value """

def __init__(self):
self.keys = {}
self.values = {}

def __getitem__(self, item):  # <---SQL SELECT statement
values = self.keys[item]
if len(values) > 1:
return sorted(list(values))
elif len(values) == 1:
return list(values)[0]

def __setitem__(self, key, value):
if key not in self.keys:  # it's a new key <---SQL INSERT statement
if value not in self.values:  # it's a new value
self.keys[key] = set()  # a new set
self.values[value] = set()  # a new set
elif value in self.values:
self.keys[key] = set()  # a new set
self.values[value].add(key)  # but just an update to the values
elif key in self.keys:  # it's a new relationships
if value not in self.values:
self.values[value] = set()
elif value in self.values:

def update(self, key, old_value, new_value):
"""update is a special case because __setitem__ can't see that
you want to propagate your update onto multiple values. """
if old_value in self.keys[key]:
affected_keys = self.values[old_value]
for key in affected_keys:
self.__setitem__(key, new_value)
self.keys[key].remove(old_value)
del self.values[old_value]
else:
raise KeyError("key: {} does not have value: {}".format(key,old_value))

def __delitem__(self, key, value=None):  # <---SQL DELETE statement
if value is None:
# All the keys relations are to be deleted.
try:
value_set = self.keys[key]
for value in value_set:
self.values[value].remove(key)
if not self.values[value]:
del self.values[value]
del self.keys[key]  # then we delete the key.
except KeyError:
else:  # then only a single relationships is being removed.
try:
if value in self.keys[key]:  # this is a set.
self.keys[key].remove(value)
self.values[value].remove(key)
if not self.keys[key]:  # if the set is empty, we remove the key
del self.keys[key]
if not self.values[value]:  # if the set is empty, we remove the value
del self.values[value]
except KeyError:

for key in key_list:
for value in value_list:
self.__setitem__(key, value)

def test01():
# hashable key - a tuple
d = Database()
k, v = (1, 2, 3), 'magic'
d[k] = v
print(d)
print(d[k])

def test02():
# non-hashable key - a list - becomes a many-key shared value
d = Database()
keys, value = [1, 2, 3], ['magic']
assert d[1] == d[2] == d[3]

def test03():
d = Database()
k, v = ['what', 'ever'], ['test']
assert d['what'] == d['ever']
d['what'] = 'testing'
try:
assert d['what'] == d['ever']
except AssertionError:
assert True

def test04():
d = Database()
v = 'test'
keys, values = ['what', 'ever'], [v]
d['whatever'] = 'test'
assert v == d['whatever']
assert v == d['what']
assert d['whatever'] == d['what']
d.update('whatever', 'test', 'new test')
a, b = d['whatever'], d['what']
assert a == b

def do_all():
for k, v in sorted(globals().items()):
if k.startswith("test") and callable(v):
v()

if __name__ == "__main__":
do_all()

• This method essentially uses the dictionaries (which I assume are hashtables) to index all the keys and all the values. It's pretty simple and useful! In comparison to real databases, which I think usually has many more values than they want indexed, they would prefer to store the data as simply an list of tuples (row oriented), and index into this data structure using secondary indexes like hashtables for a particular column and btrees for other columns. – CMCDragonkai Dec 13 '17 at 5:58