c++ - 哈希示例 - 多余的代码

Question

我找到了这段代码 here作为最简单的哈希类型的示例。它有点使因为..基本上使用模数运算符将数据集从 DATA_SIZE(隐含)减少到 TABLE_SIZE(定义)。

但是，如果发生冲突，即数组元素已经被占用，则移动到

hash = (hash + 1) % TABLE_SIZE

但是，如果您已经使用 TABLE SIZE 进行了取模，则此行将始终生成 (hash+1) b.c。当 x < y 时，x % y 总是等于 x。问题:这是一个错误吗……我的意思是它应该可以工作，但是 % TABLE_SIZE 是额外的，对吗？它在下面的代码中什么都不做。

const int TABLE_SIZE = 128;

class HashEntry 
  {
  private:
    int key;
    int value;
  public:
    HashEntry(int key, int value) 
      {
      this->key = key;
      this->value = value;
      }
    int getKey() 
      {
      return key;
      }
    int getValue() 
      {
      return value;
      }
  }; 

class HashMap 
  {
  private:
    HashEntry **table;
  public:
    HashMap() 
      {
      table = new HashEntry*[TABLE_SIZE];
      for (int i = 0; i < TABLE_SIZE; i++) table[i] = NULL;
      }
    int get(int key) 
      {
      int hash = (key % TABLE_SIZE);
      while (table[hash] != NULL && table[hash]->getKey() != key) hash = (hash + 1) % TABLE_SIZE;
      if (table[hash] == NULL)return -1;
      else return table[hash]->getValue();
      }
    void put(int key, int value) 
      {
      int hash = (key % TABLE_SIZE);
      while (table[hash] != NULL && table[hash]->getKey() != key) hash = (hash + 1) % TABLE_SIZE;
      if (table[hash] != NULL) delete table[hash];
      table[hash] = new HashEntry(key, value);
      }     
    ~HashMap() 
      {
      for (int i = 0; i < TABLE_SIZE; i++)
         if (table[i] != NULL) delete table[i];
      delete[] table;
      }
  };

Answer 1

该模数在溢出的情况下存在。

假设 hash == TABLE_SIZE - 1。然后 hash + 1 == TABLE_SIZE，而 hash+1 % TABLE_SIZE == 0。