C++中简单的哈希表实现

Question

C++中简单的哈希表实现

c++hashmaphashtable

32

我对C++比较陌生。在Java中，实例化和使用哈希表非常容易。我想知道如何以简单的方式在C++中完成它，因为我看到了许多不同的实现，但没有一个看起来很简单。

- Paulo Guedes

5个回答

16

在C++中使用哈希映射很容易！就像使用标准的C++ map一样。可以使用您的编译器/库实现的unordered_map或使用由boost提供的，或者其他供应商提供的。以下是一个快速示例。如果您遵循您得到的链接，您将找到更多相关信息。

#include <unordered_map>
#include <string>
#include <iostream>

int main()
{
    typedef std::tr1::unordered_map< std::string, int > hashmap;
    hashmap numbers;

    numbers["one"] = 1;
    numbers["two"] = 2;
    numbers["three"] = 3;

    std::tr1::hash< std::string > hashfunc = numbers.hash_function();
    for( hashmap::const_iterator i = numbers.begin(), e = numbers.end() ; i != e ; ++i ) {
        std::cout << i->first << " -> " << i->second << " (hash = " << hashfunc( i->first ) << ")" << std::endl;
    }
    return 0;
}

- Kasprzol

7

请查看boost.unordered及其数据结构。

- dalle

3

尝试使用boost的无序类（unordered classes）。请访问此链接。

- Mark Ransom

2

请查看C++中的简单哈希表（散列表）实现，其中包含通用类型键值对和分离链接策略的基本哈希表。

- aozturk

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hazzen · Accepted Answer

大多数编译器应该会为您定义std::hash_map;在即将到来的C++0x标准中，它将成为标准库的一部分，命名为std::unordered_map。关于此的STL页面非常标准。如果您使用Visual Studio，则Microsoft有一个相关页面。

如果您想将自己的类用作值，而不是键，则无需特别处理。所有基本类型（如int，char，bool甚至char *）都应该可以作为hash_map中的键来“正常工作”。但是，对于任何其他类型，您将需要定义自己的哈希和相等函数，然后编写将其包装在类中的“函数对象”。

假设您的类名为MyClass并且已经定义如下：

size_t MyClass::HashValue() const { /* something */ }
bool MyClass::Equals(const MyClass& other) const { /* something */ }

您需要定义两个函数对象来将那些方法封装到对象中。

struct MyClassHash {
  size_t operator()(const MyClass& p) const {
    return p.HashValue();
  }
};

struct MyClassEqual {
  bool operator()(const MyClass& c1, const MyClass& c2) const {
    return c1.Equals(c2);
  }
};

并将你的hash_map/hash_set实例化为：

hash_map<MyClass, DataType, MyClassHash, MyClassEqual> my_hash_map;
hash_set<MyClass, MyClassHash, MyClassEqual> my_hash_set;

之后一切都应该按预期工作。