简介

哈希表在模板中有着重要的应用。它是unordered_set、unordered_map的底层容器。哈希表的实现原理比较简单，在此不进行详细描述。在C++11以前，unordered_set、unordered_map的名称是hash_set和hash_map，后来才进行改名，但是换汤不换药，都是通过哈希表实现的。哈希表的重要特点是查找方便，时间复杂度是O(1)，但是它是无序排列的，通过hash function计算得到hash值，然后放入指定的篮子(bucket)。

hash_table模板

hash_table

上图是hash_table的简单示意图，在buckets vector中存储了指向节点的指针，通过指针可以找到该篮子中的所有节点。


// hash_table code
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc = alloc>
class hash_table {
public:
    typedef HashFcn hasher;
    typedef EqualKey key_equal;
    typedef size_t size_type;
private:
    hasher hash;
    key_equal equals;
    ExtractKey get_key;
    typedef __hashtable_node<Value> node;
    vector<node*, Alloc> buckets;
    size_type num_elements;
public:
    size_type bucket_count() const { return buckets.size(); }
}
template <class Value> 
struct __hashtable_node {
    __hashtable_node *next;
    Value val;
}
// hash_table iterators
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
    node *cur;
    hashtable *ht;
}

首先看看hash_table的大小，其中有三个函数对象hash、equals和get_key，一共占用三个字节，buckets是一个vector含有三个指针占用12字节，num_elements占用4个字节。求和是19个字节，内存对齐后是20字节。然后注意下hash_table的iterator，它含有两个指针，分别是指向hash_table即bucket vector的ht和指向节点的指针cur。两个指针实现了对hash_table的遍历。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。