数据正确放入数组但打印数组时不存在

Question

我正在实现我自己的散列 table，我运行遇到了以下问题：当我将我的节点插入 table 时，它们没有被打印出来当我循环遍历数组时。我使用的是数组的数组作为底层数据结构，逻辑如下：

我将节点传递给插入函数。该函数基于我节点中的数据类型，调用提供的适当哈希函数通过 C++ STL。
然后，我mod返回hash值的大小我的哈希 table 并使用它来确定放置哪个数组节点。
我还有一个布尔数组数组（与我的大小相同 hash table)，我用它来检查我的哈希中的特定位置 table里面已经有数据了。
如果是这样，我就一直循环直到找到一个空位。

就像我之前说的，问题是数据被正确输入到数组中（我已经用打印语句检查过了），但是当我打印数组时，没有任何输出。我还检查了我的对象是否被正确构造（再次使用 print 语句），但一切看起来都很好。我在下面包含了完整的代码。任何帮助将不胜感激！

        ///////START OF NODE.H///////////
        #ifndef NODE_H
        #define NODE_H
        #include <iostream>
        template <typename T>
        class HashTable;

        template <typename T>
        class Node
        {
            friend class HashTable<T>;

            private:
                T data;

            public:
                Node(T Data): data(Data)
                {
                    std::cout << "In the node constructor" << std::endl;
                }

                Node() 
                {
                    decltype(data) {};
                }

                T getData() const
                {
                    return data;
                }
        };
        #endif
        //////////////////////END OF NODE.H////////////////////




        /////START OF HASHTABLE.H///////
        #ifndef HASHTABLE_H
        #define HASHTABLE_H
        #include "Node.h"
        #include <iostream>
        #include <array>
        #include <functional>
        #include <typeinfo>
        #include <string>
        const int TABLE_SIZE=5;
        template <typename T>
        class HashTable
        {
            private:
                std::array<std::array<Node<T>, TABLE_SIZE>, TABLE_SIZE> hashTable;
                std::array<std::array<bool, TABLE_SIZE>, TABLE_SIZE> spots;

            public:
                HashTable()
                {
                    for(int index=0;index<spots.size();++index)
                    {
                        for(int position=0;position<spots.at(index).size();++position)
                        {
                            spots.at(index).at(position)=false;
                        }
                    }
                }

                int hashFunction(Node<T> Node)
                {
                    auto key=Node.getData();

                    std::hash<decltype(Node.getData())> hash_function {};

                    int hash=hash_function(key);

                    if(hash < 0)
                    {
                        hash*=-1;
                    }

                    //std::cout << "The hash value return by the STL hash function for the key " << key << " is " << hash << std::endl;

                    if(hash > TABLE_SIZE)
                    {
                        hash%=TABLE_SIZE;
                    }

                    std::cout << "The hash value for the key " << key << " is " << hash << std::endl;

                    return hash;
                }

                void insert(Node<T> Node)
                {
                    int hashValue=hashFunction(Node);

                    auto location=hashTable.at(hashValue);

                    std::cout << "Going to insert " << Node.getData() << std::endl;

                    for(int index=0;index<location.size();++index)
                    {
                        if(spots.at(hashValue).at(index)==false)
                        {
                            std::cout << "Found a spot that is not taken!" << std::endl;

                            std::cout << "The size of the data at the spot in the array before we insert is: " << location.at(index).getData().size() << std::endl;

                            location.at(index)=Node;

                            std::cout << "The size of the data at the spot in the array after we insert is: " << location.at(index).getData().size() << std::endl;

                            std::cout << "The data that is in the spot in the array: " << location.at(index).getData() << std::endl;

                            std::cout << std::endl;

                            spots.at(hashValue).at(index)=true;

                            break;
                        }
                    }
                }

                bool contains(Node<T> Node)
                {
                    int hashValue=hashFunction(Node);

                    auto location=hashTable.at(hashValue);

                    auto result=find_if(begin(location), end(location), [Node] (const auto & element) {return element.getData()==Node.getData();});

                    if(result!=end(location))
                    {
                        return true;
                    }

                    return false;
                }

                int getSize() const
                {
                    int size {};

                    for(int index=0;index<hashTable.size();++index)
                    {
                        size+=hashTable.at(index).size();
                    }

                    return size;
                }

                void print()
                {
                    std::cout << "In the print function" << std::endl;

                    for(int index=0;index<hashTable.size();++index)
                    {
                        //std::cout << hashTable.at(index).size() << std::endl;

                        for(int position=0;position<hashTable.at(index).size();++position)
                        {                   
                            std::cout << hashTable.at(index).at(position).getData().size() << std::endl;
                        }
                    }

                    /*
                    for(int index=0;index<spots.size();++index)
                    {
                        for(int position=0;position<spots.at(index).size();++position)
                        {
                            if(spots.at(index).at(position)==true)
                            {
                                std::cout << "There should be some data here" << std::endl;
                            }
                        }
                    }
                    */
                }
        };
        #endif
        ////////////END OF HASHTABLE.H//////////



       ////////////START OF MAIN.CPP///////////
             #include "HashTable.h"
             #include <cstdlib>
             #include <random>
             #include <algorithm>
             using namespace std;                 
             int main()
             {
                HashTable<string> hash_table;

                hash_table.insert(Node<string>("Java"));

                hash_table.insert(Node<string>("C++"));

                hash_table.insert(Node<string>("C#"));

                hash_table.insert(Node<string>("Latex"));

                hash_table.insert(Node<string>("Python"));

             }
        /////////////END OF MAIN.CPP/////////////

Answer 1

您的 insert(Node<T> Node) 函数在这些行中有一个错误：

    auto location=hashTable.at(hashValue);
    //...
    location.at(index) = Node;

location 应该是参考而非副本。发生的情况是您正在更改本地 location，而不是哈希 table 使用的实际 location。因此 none 的更改 "stick".

上面这行应该是这样的：

    auto& location=hashTable.at(hashValue);  // <-- note that auto is a reference
    //...
    location.at(index) = Node;

现在您正在将返回的引用分配给引用。

此外，我强烈建议您使用调试器，因为如果您逐步查看代码以查看正在执行的操作，则可以很容易地诊断出此错误。

Answer 2

在HashTable::insert这一行：

auto location = hashTable.at(hashValue);

复制Node。然后你操作并存储在副本中，而不是 hashTable 中的节点。引用节点

auto & location = hashTable.at(hashValue);

应该修复它。

数据正确放入数组但打印数组时不存在

Data placed into array correctly but is not there when array is printed

c++

arrays

c++11

hashtable