哈希表的大小据说是任意的，为什么？

Question

我正在学习抽象数据类型here。最近我读到了关于使用Map（或者像dict这样的数据结构）进行散列的文章。在

代码如下所示：

class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size

def put(self,key,data):
  hashvalue = self.hashfunction(key,len(self.slots))

  if self.slots[hashvalue] == None:
    self.slots[hashvalue] = key
    self.data[hashvalue] = data
  else:
    if self.slots[hashvalue] == key:
      self.data[hashvalue] = data  #replace
    else:
      nextslot = self.rehash(hashvalue,len(self.slots))
      while self.slots[nextslot] != None and \
                      self.slots[nextslot] != key:
        nextslot = self.rehash(nextslot,len(self.slots))

      if self.slots[nextslot] == None:
        self.slots[nextslot]=key
        self.data[nextslot]=data
      else:
        self.data[nextslot] = data #replace

def hashfunction(self,key,size):
     return key%size

def rehash(self,oldhash,size):
    return (oldhash+1)%size

def get(self,key):
  startslot = self.hashfunction(key,len(self.slots))

  data = None
  stop = False
  found = False
  position = startslot
  while self.slots[position] != None and  \
                       not found and not stop:
     if self.slots[position] == key:
       found = True
       data = self.data[position]
     else:
       position=self.rehash(position,len(self.slots))
       if position == startslot:
           stop = True
  return data

def __getitem__(self,key):
    return self.get(key)

def __setitem__(self,key,data):
    self.put(key,data)

现在在教科书中，作者声明哈希表的大小是任意的。请看这里：

Note that the initial size for the hash table has been chosen to be 11. Although this is arbitrary, it is important that the size be a prime number so that the collision resolution algorithm can be as efficient as possible.

为什么这是武断的？似乎给定的插槽数与可以存储的值的数量直接相关。我知道其他哈希表可能是灵活的，能够在一个数据槽中存储更多的数据，但是在这个特定的例子中，它不仅仅是“任意的”。它就是可以存储多少个值。在

我是不是少了点什么？在

Answer 1

Why is this arbitrary?

因为他可以选择任何其他的小素数。在

It would seem that the number of slots is directly correlated with […] how many values can be stored

是的，这无关紧要。如果需要扩大哈希表，可以调整大小（重新分配）并重新哈希表。这不是作者所说的。在

Answer 2

好吧，没人能预测未来，因为你永远不知道数据结构用户实际会在容器中放入多少值。 所以你从一些小东西开始，不要吃太多内存，然后根据需要增加和重新计算。在

Answer 3

The Paramagnetic Croiss回答了你的主要问题。数字11当然意味着，如果不重新分配表并重新刷新所有元素，就不能容纳超过11个元素，因此很明显，这并不是武断的。但这是任意的，只要这个数字是素数（是的，比你要做的插入数还要大），作者想要演示的所有内容都会得到相同的结果。*

_{*尤其是，如果元素是自然数，并且表大小是素数，并且与最大整数相比足够小，% size是一个很好的哈希函数。}

但对于你的后续问题：

It would seem though, that making a table with a bigger prime number would allow for you to have more available slots and require less need for you to rehash, and have less items to search through in each slot (if you extended the data slots to hold more than one value). The items would be spread thinner in general. Is this not correct?

如果我对你的理解是对的，你用的词不对，这就是为什么你会得到令人困惑的答案。您的示例代码使用了一个名为rehash的函数，但这会误导您。重新散列是进行探测的一种方法，但这不是你的方法；你只是在做线性探测和双重散列的组合。*更常见的是，当人们谈论重新散列时，他们谈论的是你在扩展散列表之后要做什么，并且必须将旧表中的每个值重新哈希到新表中。在

_{*当您的哈希函数像key%size一样简单时，区别是不明确的…}

总之，是的，更多的负载（如果M个bucket中有N个元素，那么就有N/M的负载）意味着更多的探测，这是不好的。以最极端的元素为例，在load1.0时，平均操作必须遍历表的一半以找到正确的bucket，这使得hash表的效率与暴力搜索数组一样低效。在

但是，随着负载的减少，返回值下降得很快。您可以为任何特定的散列实现绘制精确的曲线，但是您通常使用的经验法则（对于这样的封闭散列）是，使负载低于2/3通常是不值得的。请记住，一个更大的哈希表既有成本，也有好处。假设您在一台32位机器上，有一个64字节的缓存线。因此，11个指针适合一条缓存线；在任何哈希操作之后，下一个指针肯定是缓存命中。但是17个指针被分割在两条缓存线上；在任何哈希操作之后，下一个指针只有50%的机会被缓存命中。*

_{*当然，实际上，在你的循环中有足够的空间来为一个哈希表使用2条缓存线；这就是为什么当N是个位数时，人们通常根本不担心性能……但是你可以看到，在更大的哈希表中，保留太多的空空间意味着更多的一级缓存未命中，更多的二级缓存未命中万一更多的虚拟机页面丢失。}