5.7 hushtable

5.7.1 hushtable概述

开链：在每一个表格元素中维护一个list；hash function为我们分配某一个list，然后我们在那个list身上执行元素的插入、搜寻、删除等操作。

5.7.3 hashtable的迭代器

template <class Value, class Key, class HashFcn,    class ExtractKey, class EqualKey, class Alloc>struct __hushtable_iterator{    typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable;    typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;    typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> const_iterator;    typedef __hashtable_node<Value> node;    typedef forward_iterator_tag iterator_category;    typedef Value value_type;    typedef ptrdiff_t difference_type;    typdef size_t size_type;    typedef Value& reference;    typedef Value* pointer;    node* cur;    hashtable* ht;  //保持对容器的连结关系（因为可能需要从bucket跳到bucket）    __hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) { }    __hashtable_iterator() { }    reference operator*() const { return cur->val; }    pointer operator->() const { return &(operator*()); }    iterator& operator++();    iterator operator++(int);    bool operator==(const iterator& it) const { return cur==it.cur; }    bool operator!=(const iterator& it) const { return cur!=it.cur; }};template <class T, class K, class HF, class ExK, class EqK, class A>__hashtable_iterator<V, K , HF,ExK, EqK, A>&__hashtable_iterator<V, K , HF,ExK, EqK, A>::operator++() {    const node* old=cur;    cur=cur->next;  //如果存在，结果就是它；否则进入以下if流程    if(!cur){        //根据元素值，定位出下一个bucket，其起头处就是我们的目的地        size_type bucket=ht->bkt_num(old->val);        while(!cur&& ++bucket<ht->buckets.size())            cut=ht->buckets[bucket];    }    return *this;}template <class T, class K, class HF, class ExK, class EqK, class A>__hashtable_iterator<V, K , HF,ExK, EqK, A>&__hashtable_iterator<V, K , HF,ExK, EqK, A>::operator++(int) {    iterator tmp=*this;    ++*this;    return tmp;}}

 

5.7.4 hashtable的数据结构

hashtable的模板参数：

• Value：节点的实值型别；
• Key：节点的键值型别；
• HashFcn：hash function的函数型别；
• ExtractKey：从节点中取出键值的方法（函数或仿函数）；
• EqualKey：判断键值相同与否的方法（函数或仿函数）；
• Alloc：空间配置器，缺省使用std::alloc。

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc=alloc>class hushtable;//...template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>class hushtable {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;    typedef simple_alloc<node, Alloc> node_allocator;    vector<node*, Alloc> buckets;    size_type num_elements;public:    //bucket的个数即buckets vector的大小    size_type bucket_count() const { return buckets.size(); }...};

 

SGI STL以质数来设计表格大小，并且先将28个质数（逐渐呈现大约两倍的关系）计算好，以备随时访问，同时提供一个函数，用来查询在这28个质数之中，“最接近某数并大于某数”的质数。

（本节源代码过多，余下部分借鉴：http://blog.csdn.net/u012062760/article/details/46400953）

5.8 hash_set

1. SGI STL的hash_set是以hashtable为底层机制的，几乎所有的hash_set操作行为，都只是调用hashtable的操作行为而已；
2. 因为RB-tree有自动排序功能而hashtable没有，所以set的元素有自动排序功能而hash_set没有；
3. hash_set的使用方式，与set完全相同。

5.9 hash_map

1. SGI STL的hash_map是以hashtable为底层机制的，几乎所有的hash_map操作行为，都只是调用hashtable的操作行为而已；
2. 因为RB-tree有自动排序功能而hashtable没有，所以map的元素有自动排序功能而hash_map没有；
3. hash_map的使用方式，与map完全相同。

5.10 hash_multiset

hash_multiset的特性及用法和hash_set完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制hashtable的insert_equal()而非insert_unique()。

5.11 hash_multimap

hash_multimap的特性及用法和hash_map完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制hashtable的insert_equal()而非insert_unique()。

Ch5 关联式容器（下）