I wrote a minimal implementation of a hashtable in python as an exercise.
from copy import copy def init_nested_array(size): arr =  for i in range(size): arr.append() return arr class hashtable: def __init__(self): self.mod = 3 self.num_items = 0 self.arr = init_nested_array(self.mod) def __str__(self): return str(self.arr) def __repr__(self): return str(self) def __len__(self): return self.num_items def __getitem__(self, key): return self.get_item(key) def __setitem__(self, key, value): return self.set_item(key, value) def hash_function(self, key): return hash(key) % self.mod def get_item(self, key): bucket = self.arr[self.hash_function(key)] for pair in bucket: if pair == key: return pair raise KeyError("Item not found", key) def set_item(self, key, value): bucket = self.arr[self.hash_function(key)] for pair in bucket: if pair == key: pair = value return self.arr[self.hash_function(key)].append([key, value]) self.num_items += 1 if self.num_items >= .7*self.mod: self.expand() def expand(self): # Ideally we'd expand to new prime number. But at least we'll stick to odds self.mod = self.mod*2 + 1 old_arr = copy(self.arr) num_items = self.num_items self.arr = init_nested_array(self.mod) for bucket in old_arr: for pair in bucket: self.set_item(pair, pair) self.num_items = num_items
The things I've noticed for potential improvement in my code:
- it isn't immediately obvious why init_nested_array is necessary and when it should be used. A comment for that method would probably be appropriate
- I used the rule of thumb that hash tables shouldn't exceed a load of 70% but this is buried as a magic number in set_item. This should probably either be a private class variable with a comment as to why I picked that number or a global constant. It seems that if I want to allow the user to adjust this I should make it a class member and otherwise make it a global constant. Do you agree?
- I just learned that repr is meant to allow eval to be called on it. Since I currently don't allow the user to initialize the dictionary with a list of elements it doesn't seem possible for eval to recreate the original instance. I've been using repr as a way to interact a pretty print for the interactive shell. It seems like that's incorrect. Should I just leave repr unimplemented then?
hash_functionshould probably have a leading underscore since it seems best as a private method. Should I also change
self.arrto have leading underscores? Is it really necessary to have leading underscores for class variables?
Please assume that anything I didn't mention is because I don't yet know the relevant concept. Looking forward to any criticisms or observations.