在C++中实现哈希表

Question

以下是使用C++实现哈希表的代码。您能否帮助我理解HashEntry **table 是什么？为什么它声明为双指针？它是一个数组，数组的每个值都是 HashEntry 吗？ HashEntry **table 是一个指向指针的指针，也可以称作二级指针。它用于创建一个动态的哈希表，其中每个条目（entry）都是一个指针。所以 `table` 本身是一个指向指针数组的指针。每个元素是一个 `HashEntry` 类型的指针，指向哈希表的一个具体的 entry。这样设计可以方便在哈希表的动态调整大小过程中，直接修改 table 数组的大小即可。

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

- Anni_housie

---

just for interview question. - Anni_housie

@πάνταῥεῖ 你是不是指的是 std::unordered_map？ - druckermanly

@Anni_housie HashEntry** 是一个动态的二维数组。 - Omid CompSCI

@OmidCompSCI，这是TABLE_SIZE * TABLE_SIZE的尺寸吗？ - Anni_housie

@Anni_housie 看看这个链接，非常有用：https://dev59.com/53NA5IYBdhLWcg3wgeAd - Omid CompSCI

Answer 1

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

HashEntry **table;

一般规则是从变量名和基本类型开始，向右尽可能地延伸，然后向左移动，可以参考这个优秀的描述。

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

所以，你从变量table和基本类型HashEntry开始，它在最左边。请注意，本文描述的是'C'的规则，在'C'中，基本类型可以是struct，将你的C++类HashEntry视为'C'结构体。

table is ... HashEntry

声明中没有其他内容位于table右侧，因此向左移动，你会看到"*"，表示指针：

table is pointer to ... HashEntry

再次向左移动声明并消耗下一个"*"，现在你有：

table is pointer to pointer to HashEntry

...然后你就完成了。

或许不幸的是，table被声明为这种方式，因为table意味着数组，但它没有被声明为数组。事实证明，在C++和C中，当数组传递给函数时，数组会“衰减”成指针。这里的“衰减”表示你已经失去了信息，即数组的大小。

我认为更能让读者理解的等效声明应该是：

HashEntry * table[];

使用关于如何解释变量声明的规则，应该理解为： 是指向指针的未定义数组 从编译器的角度来看，这与先前的声明相同，因为一个“未定义的数组”被传递为指向数组元素类型的指针（值为第一个元素的地址，在偏移量0处）。 “定义的数组”也会衰减为指针，丢失维度信息。 有关数组衰减的更多信息，请参阅此SO答案。 什么是数组衰减？

- amdn