[C++知识库]【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};
  
  

  

• 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一致