【c++从菜鸡到王者】第4篇:STL非标准容器-hashtable

hashtable

  • //下面介绍一下hashtabl迭代器的主要功能函数operator++
    template<class Value, class Key, class HashFen, class ExtractKey, class EqualKey, class Alloc>
    _hashtable_iterator< Value,  Key,  HashFen,  ExtractKey, EqualKey,  Alloc>&
    _hashtable_iterator< Value,  Key,  HashFen,  ExtractKey, EqualKey,  Alloc>::operator++(){
        const node* lod=cur;//保存当前节点的指针
        cur=cur->next;//如果存在,就返回其下一节点的引用,如果不存在,也就是说该节点位于list的尾端,需要跳向下一个bucket
        if(!cur){
            size_type bucket=ht->bket_num(old->val);//获取当前bucket的位置
            while(!cur&&++bucket<buckets.size())
                cur=ht->buckets[bucket];
            //这里实现的就是bucket的跳跃
        }
        
        
        
        return *this;
    }
    
  • //hashtable部分源代码
    template<class Value, //节点的实值类别
    		 class Key,  //节点的键值类别
    		 class HashFcn,//hash funtion的函数类别
             class ExtractKey,//从节点中取出键值的方法(函数,仿函数) 
    		 class EqualKey,//判断键值相等与否的方法(函数,仿函数)
             class Alloc=alloc>
    class hashtable {
    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;	// 保存桶的vector
        size_type num_elements;
    public:
        size_type bucket_count() const { return buckets.size(); }
    };
    
    template<class Value>//节点类
    struct __hashtable_node {
        __hashtable_node *next;
        Value val;
    };
    //迭代器类
    template<class Value, class Key, class HashFen, class ExtractKey, class EqualKey, class Alloc>
    struct __hashtable_iterator {
        node *cur;
        hashtable *ht;
    };
    
    
  • //hashtable提前准备好28个质数用来设置表格大小(桶的多少),并提供函数查询
    static const unsigned long __stl_prime_list[__stl_num_primes] = {
            53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
            6291469, 12582917, 25165843, 50331653, 100663319,
            201326611, 402653189, 805306457, 1610612741,
            3221225473ul, 4294967291ul};
    
    

    【c++从菜鸡到王者】第4篇:STL非标准容器-hashtable

  • hashtable无法处理例如string,float,double这些类型的元素,如果需要处理,则需要自己定义hash funtion

  • hash_set,hash_map是以hashtable 为底层机制,所以他们的操作行为,只是调用hashtable的操作行为,他们的插入操作调用的是hashtable的insert_unique()

  • hash_multiset,hash_multimap,同样是以hashtable为底层机制,只不过他们的插入操作采用的是hashtable的insert_equal()

  • c++11中hash_set/hash_map改名为unordered_map/unordered_set其底层依旧封装了hashtable,用法与set/map一致

上一篇:Spark Shuffle原理详解


下一篇:CRUSH数据分布算法