创建哈希表，其中每个值都是许多值的向量

Question

我有以下输入.txt文件，实际上大约有150k ids。

id    element
0    1
0    3
1    0
1    1
1    3
2    2
2    4
3    4
4    1

我想将 id 存储为键，并将值存储在保存每个 id 值的向量中。例如，最后我想要一个看起来像这样的哈希表。

0 -> 1, 3
1 -> 0, 1, 3
2 -> 2, 4
3 -> 4
4 -> 1

这是我到目前为止的代码：

#include<iostream>
#include<cstdlib>
#include<vector>
using namespace std;
const int TABLE_SIZE = 128;
class HashEntry
{
public:
int key;
vector< int > values;
HashEntry(int key, int value)
{
this->key = key;
values.push_back(value);
}
};
class HashMap
{
private:
HashEntry **table;
public:
HashMap()
{
table = new HashEntry * [TABLE_SIZE];
for (int i = 0; i< TABLE_SIZE; i++)
{
table[i] = NULL;
}
}
/*
* Hash Function
*/
int HashFunc(int key)
{
return key % TABLE_SIZE;
}
void Insert(int key, int value)
{
int hash = HashFunc(key);
table[hash] = new HashEntry(key, value);
}
void Show(){
for (int i=0;i<TABLE_SIZE;i++){
if (table[i]!=NULL){
cout << table[i]->key << " : ";
for(int y = 0; y < table[i]->values.size(); y++) {
cout << table[i]->values[y];
}
cout << endl;
}
}
}
};
int main()
{
HashMap hash;
int key, value;
while (1)
{
cout<<"Enter element to be inserted: ";
cin>>value;
cout<<"Enter key at which element to be inserted: ";
cin>>key;
hash.Insert(key, value);
hash.Show();
}
return 0;
}

在控制台中，它仅显示我输入的最后一个元素，而不是所有值。我认为问题是 HashEntry 对象每次都初始化，并且它的成员每次都从头开始初始化。如何保持哈希条目"静态"？

编辑： 这是我遵循Davide Spataro建议后的新代码。不幸的是，我不能使用 C++11，所以我稍微改变了它。现在出了什么问题？

void Insert(int key, int value)
{
int hash = HashFunc(key);
//check if we already have an `HashEntry` for key
HashEntry *p = find(key, table[hash]);
// if yes simply push the value in that `HashEntry`
if( p->key == -1 ){
p->values.push_back(value);
return;
}
else{
//otherwise add an `HashEntry` to the hashtable for key and push a value in it.
HashEntry *p = new HashEntry(key, value);
p->values.push_back(value);
table[hash] = p;
}
}
HashEntry* find(int key, HashEntry *table)
{
for (int i=0;i<TABLE_SIZE;i++)
{
if (key == table[i].key)
return &table[i];
else return new HashEntry(-1,-1);
}
}

Answer 1

问题主要出在您的Insert.每当您找到一个散列到特定值的键时，您就会覆盖可能已经创建一个新值的HashEntry！这是错误的，也会导致内存泄漏。

您还需要处理碰撞。哈希表中只有128个存储桶和 150k 个可能的键值。对于鸽子原则，对于相同的哈希值，您最终将拥有多个HashEntry。你的代码需要处理这个问题。

像下面这样的东西应该足以作为起点。

void Insert(int key, int value)
{
int hash = HashFunc(key);
//check if we already have an `HashEntry` for key 
auto p = find(key, table[hash]);
// if yes simply push the value in that `HashEntry` 
if( p != nullptr){
p->values.push_back(value);
return;
}else{
//otherwise add an `HashEntry` to the hashtable for key and push a value in it.
auto p = new HashEntry(key, value);
p->values.push_back(value);
table[hash] = p;
}
}

还有其他问题，例如评论中提到的规则 3/5/0，因为您管理原始指针。(你需要在某个时候释放内存，不是吗？