Basic toy hashtable

Question

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[0] == key:
        return pair[1]
    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[0] == key:
        pair[1] = 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[0], pair[1])
    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_function should probably have a leading underscore since it seems best as a private method. Should I also change self.mod and self.num_items and self.arr to 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.

Answer 1

• init_nested_array in idiomatic python is

  def init_nested_array(size):
      return [ [] for _ in range(size) ]
  

  Since you are concerned with its reason to exist (a desire to put a defensive comment usually indicates a problem of that sort), you may want to use it inline:

      self.arr = [ [] for _ in range(self.mod) ]
  

  It would be even more clear if you call it self.buckets instead of (pretty meaningless) self.arr.

• Initial mod and the .7 factor should be default (or named) constructor arguments:

  def __init__(self, mod = 3, threshold = 0.7):
      self.mod = mod
      self.threshold = threshold
      ....
  

• Mutual recursion of set_item and expand looks scary. I understand that it terminates, but the reviewer shudders for a moment. I would consider having a non-recursive set_item_safe() helper to be used along the lines of:

  def set_item():
      if need_to_expand:
         expand()
      set_item_safe()
  

  and

  def expand():
      ....
          rehash()
          set_item_safe()