数据正确放入数组但打印数组时不存在
Data placed into array correctly but is not there when array is printed
我正在实现我自己的散列 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/////////////
您的 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;
现在您正在将返回的引用分配给引用。
此外,我强烈建议您使用调试器,因为如果您逐步查看代码以查看正在执行的操作,则可以很容易地诊断出此错误。
在HashTable::insert
这一行:
auto location = hashTable.at(hashValue);
复制Node
。然后你操作并存储在副本中,而不是 hashTable
中的节点。引用节点
auto & location = hashTable.at(hashValue);
应该修复它。
我正在实现我自己的散列 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/////////////
您的 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;
现在您正在将返回的引用分配给引用。
此外,我强烈建议您使用调试器,因为如果您逐步查看代码以查看正在执行的操作,则可以很容易地诊断出此错误。
在HashTable::insert
这一行:
auto location = hashTable.at(hashValue);
复制Node
。然后你操作并存储在副本中,而不是 hashTable
中的节点。引用节点
auto & location = hashTable.at(hashValue);
应该修复它。