c++ - 在 C++ 中实现哈希表

Question

下面是使用C++实现hashtable。你能帮我理解什么是 HashEntry **table 吗？为什么它被声明为双指针？是不是一个数组，数组的每个值都是HashEntry？

  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;
          }
    };

    const int TABLE_SIZE = 128;






    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

在这段代码中，table是一个指向HashEntry的指针

HashEntry **table;

一般规则是从变量名和基本类型开始，尽可能向右，然后向左，参见这个优秀的描述

http://unixwiz.net/techtips/reading-cdecl.html

因此，您从变量 table 和最左边的基本类型 HashEntry 开始。请注意，本文描述了“C”的规则，其中基本类型可以是 struct，将您的 C++ 类 HashEntry 视为“C”结构。

表是...HashEntry

在声明中 table 的右边没有其他东西，所以向左走，你有“*”代表指向的指针:

表是指向 ... HashEntry 的指针

同样，您必须在声明中向左移动并使用下一个“*”，您现在有

table 是指向 HashEntry 的指针

... 大功告成。

table 以这种方式声明可能很不幸，因为 table 隐含数组，并且它没有声明为数组。事实证明，在 C++ 中，与在 C 中一样，数组在传递给函数时会“退化”为指针。这里的“衰减”意味着你丢失了信息，即数组的大小。

我认为会给读者更多洞察力的等效声明是:

HashEntry * table[];

使用关于如何解释变量声明的规则，这应该被理解为

表是指向 HashEntry 的指针的无维数组

从编译器的角度来看，这与前面的声明是等价的，因为一个无维数组作为指向数组元素类型的指针传递(值是数组元素的地址)第一个元素，偏移量为 0)。 “维度数组”也会随着维度信息的丢失而衰减为指针。有关将数组衰减为指针的更多信息，请参阅此 SO 答案。

What is array decaying?