在C++中实现hash-table

Question

以下是使用C++实现哈希表.你能帮我理解一下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"的规则,其中基本类型可以是a 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[];

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

table is undimensioned array of pointer to HashEntry

从编译器的观点到前一个声明,这是等效的,因为未扩展的数组作为指向数组元素类型的指针传递(该值是第一个元素的地址,偏移量为0)."尺寸数组"也会衰减到指针,同时丢失尺寸信息.有关将数组衰减到指针的更多信息,请参阅此SO答案.

什么是阵列衰减？