2015-10-24

C++ STL 之哈希表 | unordered_map

C++ STL中，哈希表对应的容器是 unordered_map（since C++ 11）。根据 C++ 11 标准的推荐，用 unordered_map 代替 hash_map。

Prologue

先来回顾一下数据结构中哈希表相关的知识。

哈希表是根据关键码值(key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数。

哈希表的一个重要问题就是如何解决映射冲突的问题。常用的有两种：开放地址法 和 链地址法。

与 map 的区别

STL中，map 对应的数据结构是 红黑树。红黑树是一种近似于平衡的二叉查找树，里面的数据是有序的。在红黑树上做查找操作的时间复杂度为 O(logN)。而 unordered_map 对应 哈希表，哈希表的特点就是查找效率高，时间复杂度为常数级别 O(1)，而额外空间复杂度则要高出许多。所以对于需要高效率查询的情况，使用 unordered_map 容器。而如果对内存大小比较敏感或者数据存储要求有序的话，则可以用 map 容器。

基本使用

unordered_map 的用法和 map 大同小异，一个简单示例：

#include <iostream>
#include <unordered_map>
#include <string>
int main(int argc, char **argv) {
    std::unordered_map<int, std::string> map;
    map.insert(std::make_pair(1, "Scala"));
    map.insert(std::make_pair(2, "Haskell"));
    map.insert(std::make_pair(3, "C++"));
    map.insert(std::make_pair(6, "Java"));
    map.insert(std::make_pair(14, "Erlang"));
    std::unordered_map<int, std::string>::iterator it;
    if ((it = map.find(6)) != map.end()) {
        std::cout << it->second << std::endl;
    }
    return 0;
}

使用自定义类

要使用哈希表，必须要有对应的计算散列值的算法以及判断两个值（或对象）是否相等的方法。
在 Java 中，Object 类里有两个重要方法：hashCode 和 equals 方法。其中 hashCode 方法便是为散列存储结构服务的，用来计算散列值；而 equals 方法则是用来判断两对象是否等价。由于所有的类都继承自 java.lang.Object 类，因此所有类相当于都拥有了这两个方法。

而在 C++ 中没有自动声明这类函数，STL 只为 C++ 常用类提供了散列函数，因此如果想在 unordered_map 中使用自定义的类，则必须为此类提供一个哈希函数和一个判断对象是否相等的函数（e.g. 重载 == 运算符）。下面是一个简单示例（扒自数据结构上机作业的部分代码）：

using std::string;
using std::cin;
using std::cout;
using std::endl;
using std::unordered_map;
class Person {
public:
    string phone;
    string name;
    string address;
    explicit Person() {}
    explicit Person(string name, string phone, string address): name(name), phone(phone), address(address) {}
    // overload operator==
    bool operator==(const Person& p) {
        return this->phone == p.phone && this->name == p.name
            && this->address == p.address;
    }
    inline friend std::ostream& operator<<(std::ostream& os, Person& p) {
        os << "[Person] -> (" << p.name << ", " << p.phone << ", "
           << p.address << ")";
        return os;
    }
};
// declare hash<Person>
namespace std {
 template <>
 struct hash<Person> {
     std::size_t operator()(const Person& p) const {
      using std::size_t;
      using std::hash;
      using std::string;
      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:
      return ((hash<string>()(p.phone)
        ^ (hash<string>()(p.name) << 1)) >> 1)
        ^ (hash<string>()(p.address) << 1);
     }
 };
}
unordered_map<string, Person> phoneMap;
void selectByPhone() {
    string phone;
    cout << "Input the phone number: "; cin >> phone;
    unordered_map<string, Person>::iterator it;
    int size = phoneMap.size();
    for(int pc = 0; pc < size; pc++) {
        if((it = phoneMap.find(phone)) != phoneMap.end()) {
            cout << "Query result: " << it->second << endl;
            return;
        }
    }
    cout << "Query result : target_not_found" << endl;
}

关于哈希值如何计算，前面我写过一篇文章专门介绍这个：hashCode 方法及 equals 方法的规范。

本文标题:C++ STL 之哈希表 | unordered_map

文章作者:sczyh30

发布时间:2015年10月24日

原始链接:http://www.sczyh30.com/posts/C-C/cpp-stl-hashmap/

许可协议: "知识共享-保持署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。