基本玩具哈希表

Question

作为练习，我在python中编写了一个哈希表的最小实现。

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

我注意到了代码中潜在的改进之处：

• 现在还不清楚为什么init_nested_array是必要的，何时应该使用它。该方法的注释可能是合适的。
• 我使用的经验法则是，哈希表不应该超过70%的负载，但在set_item中这是一个神奇的数字。这可能是一个私有类变量，并说明我为什么选择这个数字，或者是一个全局常量。看来，如果我想让用户调整这个值，我应该让它成为类成员，否则就会成为一个全局常量。你同意吗？
• 我刚刚了解到，瑞尔是指允许在其上调用eval。由于我目前不允许用户使用元素列表初始化字典，所以eval似乎不可能重新创建原始实例。我一直在使用repr作为交互shell的一个漂亮打印的交互方式。这似乎是不正确的。那么，我应该让repr没有实现吗？
• hash_function可能应该有一个领先的下划线，因为作为一种私有方法，它似乎是最好的。我是否也应该更改self.mod、self.num_items和self.arr，使其具有领先的下划线？是否真的有必要为类变量设置前导下划线？

请假设我没有提到的任何事情都是因为我还不知道相关的概念。期待任何批评或观察。

Answer 1

• init_nested_array在惯用python中是def init_nested_array(size)：因为您关注它存在的原因(想要给出一个防御的注释通常表示这类问题)：self.arr =[ [] for _ in范围(self.mod)])，如果您称它为self.buckets而不是(非常无意义的) self.arr，则会更加清楚。
• 初始mod和.7因子应该是默认(或命名)构造函数参数: def __init__(self，mod = 3，阈值= 0.7)：self.mod = mod self.threshold =阈值.
• set_item和expand的相互递归看起来很可怕。我知道它结束了，但是评审员不寒而栗。我会考虑使用一个非递归的set_item_safe()助手，类似于: def set_item()：if need_to_expand: need_to_expand() set_item_safe()和def need_to_expand()：.重散列() set_item_safe()