C++、内存和数组。创建我自己的哈希图以供练习。内存中残留有意外数据？

Question

所以我试图为一个我想学习 C++ 的小项目创建一个非常适合我的需求的哈希图。我有以下代码：

template<class T>
class HashMap
{
public:
  HashMap();
  virtual ~HashMap();
  void add(T value);
  T get(T *value);
private:
  int hash(T *data);
  T _hashes[26]; //I want a fixed size here
};

template<class T>
HashMap<T>::HashMap()
{
  for(int i = 0; i < 26; i++)
    this->_hashes[i] = T();
}

template<class T>
HashMap<T>::~HashMap()
{
  //Don't really have anything to delete here?
}

template<class T>
int HashMap<T>::hash(T *dat)
{
  //Super simple, just to try things out
  return (long int) dat % 26;
}

template<class T>
T HashMap<T>::get(T *val)
{
  int idx = this->hash(val);
  cout << idx << endl;
  //Probably somewhere here i get my problem
  if(this->_hashes[idx])
    return this->_hashes[idx];
  return T();
}

template<class T>
void HashMap<T>::add(T val)
{
  //Should probably do some check if there's already an element here.
  this->_hashes[this->hash(&val)] = val;
}

我遇到的问题是编译得很好，但是当我在 main.cpp 中执行类似操作时：

HashMap<char> a = HashMap<char>();
a.add('h');
a.add('c');
a.add('g');
char *b = new char {'c'};
cout << a.get(b) << endl;
delete b;

它通常返回 id，即：

4

和一个空行，它只是一个空字符。 （函数的输出在 get() 方法中），但有时它会显示类似这样的内容：

18
g

而不是 18 和一个空行。我的问题是为什么会发生这种情况以及如何防止它？这是否与内存在被删除时不被“清空”有关，而只是免费供其他程序使用，然后我没有正确初始化它？ 另外，如果您有时间，请指出代码中的任何错误或做得不好的事情。

如果有任何兴趣，我使用 GCC Debian 4.4.5-8 进行编译，并使用 g++ -g file.cpp -o file 进行编译

感谢您的帮助！

Answer 1

您看到的行为是正常的：如果您获取放入哈希中的值，它将由您的main显示。给您带来令人惊讶的结果的是您的哈希函数：

return (long int) dat % 26;

它对 dat 指针 进行哈希处理，而不是对 dat 的 T 进行哈希处理。指向.尝试使用：（

return *dat % 26;

或者仅使用标准 std::set。）

代码的另一个问题：

T _hashes[26]; //I want a fixed size here   (a

和

this->_hashes = new T[26];                   (b

不兼容。要么使用固定数组 (a) 并且不需要分配它 (b)，要么使用普通指针 (T *_hashes) 并执行 (b) - 我对你的编译器感到惊讶接受你所拥有的。如果您使用 (a)，则析构函数中不需要任何内容​​。如果您使用 (b)，则需要在析构函数中删除 []。

在 get 中传递 T* 而在 set 中传递 T 也有点奇怪。

Answer 2

这是一个更惯用的 C++ 实现：

#include <array>
#include <iostream>
#define MAGIC_NUMBER 26 //rename this to something else preferably

template<class T>
class HashMap
{
    public:
        HashMap();
        virtual ~HashMap(){};
        void add(T value);
        T get(T *value);//potentially confusing that add and get take different types
    private:
        int hash(T *data);
        std::array<T, MAGIC_NUMBER>  _hashes; //I want a fixed size here
};

template<class T>
HashMap<T>::HashMap()
{
    std::fill(_hashes.begin(),_hashes.end(), T());
}

template<class T>
int HashMap<T>::hash(T *dat)
{
    //Super simple, just to try things out
    return (static_cast<int>(*dat)) % MAGIC_NUMBER;//prefer using c++ casts
}

template<class T>
T HashMap<T>::get(T *val) //this is strange, you pass in a pointer and get a non-pointer
{
  int idx = this->hash(val);
  std::cout << idx << std::endl;
  if(this->_hashes[idx])
    return this->_hashes[idx];
  return T();
}

template<class T>
void HashMap<T>::add(T val)
{
  //Should probably do some check if there's already an element here.
  this->_hashes[this->hash(&val)] = val;
}

int main(void){
    HashMap<char> a = HashMap<char>();
    a.add('h');
    a.add('c');
    a.add('g');
    char *b = new char {'c'};
    std::cout << a.get(b) << std::endl;
    delete b;
}

请注意，您需要使用 c++0x 或 c++11 功能进行编译才能使用 std::array 类。数组类的主要好处之一是，与普通的 C 样式数组相比，内存分配更加安全。

现在您可能想要重新考虑设计的某些元素。特别令人困惑的是 add 和 get 具有不同的类型。而且，这并不是人们听到 hashmap 时通常想到的，这种结构更像是一个集合。

另外，作为编码标准的注释，如果您为成员变量添加前缀，那么也使用 this-> 来访问它们有点同义反复。