The best way to demonstrate this without actually using a dict anywhere is to probably implement something dead simple, very different from a dict , and not completely useless. Like a fixed size fixed size bytes to the same fixed size bytes . (You can use this for, for example, a routing table - it will be much more compact than dict matching unpacked keys with unpacked values, although, obviously, due to speed and flexibility.)
A hash table is just an array of tuples (hash, key, value) . Since the whole point of this is wrapping the data in, we squeeze it into a struct , that is, we can just use a large bytearray for storage. To mark the slot empty, we set its hash value to 0 , which means that we need to "escape" from any real 0 , turning it into 1 , which is stupid, but easier for the code. For simplicity, we will also use the dumbest possible probe algorithm.
class FixedHashTable(object): hashsize = 8 def __init__(self, elementsize, size): self.elementsize = elementsize self.size = size self.entrysize = self.hashsize + self.elementsize * 2 self.format = 'q{}s{}s'.format(self.elementsize, self.elementsize) assert struct.calcsize(self.format) == self.entrysize self.zero = b'\0' * self.elementsize self.store = bytearray(struct.pack(self.format, 0, self.zero, self.zero) ) * self.size def hash(self, k): return hash(k) or 1 def stash(self, i, h, k, v): entry = struct.pack(self.format, h, k, v) self.store[i*self.entrysize:(i+1)*self.entrysize] = entry def fetch(self, i): entry = self.store[i*self.entrysize:(i+1)*self.entrysize] return struct.unpack(self.format, entry) def probe(self, keyhash): i = keyhash % self.size while True: h, k, v = self.fetch(i) yield i, h, k, v i = (i + 1) % self.size if i == keyhash % self.size: break
As the error message says, you need to provide implementations of the abstract methods __delitem__ , __getitem__ , __iter__ , __len__ and __setitem__ . However, it is better to find documents that will tell you that if you implement these five methods (plus any other methods required by the base classes, but as you can see from the table, they are not), you will get all other methods for free. You cannot get the most effective possible implementations of all of them, but we will return to this.
First, let's talk about __len__ . Usually people expect this to be O (1), which means we need to track it independently, updating it as needed. So:
class FixedDict(collections.abc.MutableMapping): def __init__(self, elementsize, size): self.hashtable = FixedHashTable(elementsize, size) self.len = 0
Now __getitem__ just checks until it finds the right key or reaches the end:
def __getitem__(self, key): keyhash = self.hashtable.hash(key) for i, h, k, v in self.hashtable.probe(keyhash): if h and k == key: return v
And __delitem__ does the same, except that it frees the slot if it is found and updates len .
def __delitem__(self, key): keyhash = self.hashtable.hash(key) for i, h, k, v in self.hashtable.probe(keyhash): if h and k == key: self.hashtable.stash(i, 0, self.hashtable.zero, self.hashtable.zero) self.len -= 1 return raise KeyError(key)
__setitem__ little more complicated - if it is found, we must replace the value in the slot; if not, we must fill in the empty slot. And here we have to deal with the fact that the hash table can be complete. And, of course, we have to take care of len :
def __setitem__(self, key, value): keyhash = self.hashtable.hash(key) for i, h, k, v in self.hashtable.probe(keyhash): if not h or k == key: if not h: self.len += 1 self.hashtable.stash(i, keyhash, key, value) return raise ValueError('hash table full')
And that leaves __iter__ . As in the case of dict , we do not have a specific order, so we can just iterate over the hash table slots and display all non-empty ones:
def __iter__(self): return (k for (h, k, v) in self.hashtable.fetch(i) for i in range(self.hashtable.size) if h)
While we are doing this, we could write __repr__ . Note that we can use the fact that we get items for free:
def __repr__(self): return '{}({})'.format(type(self).__name__, dict(self.items()))
However, note that by default, items simply creates an ItemsView(self) , and if you track this through the source, you will have it iterate through self and look at each value. You obviously can do better if performance matters:
def items(self): pairs = ((k, v) for (h, k, v) in self.hashtable.fetch(i) for i in range(self.hashtable.size) if h) return collections.abc.ItemsView._from_iterable(pairs)
And similarly for values and possibly other methods.