首页 > 代码库 > 【STL】关联容器 — hash_set

【STL】关联容器 — hash_set

容器hash_set是以hash table为底层机制的,差点儿所有的操作都是转调用hash table提供的接口。因为插入无法存储同样的键值,所以hash_set的插入操作所有都使用hash table的insert_unique接口,代码例如以下:
pair<iterator, bool> insert(const value_type& obj)
{
    pair<typename ht::iterator, bool> p = rep.insert_unique(obj);
    return pair<iterator, bool>(p.first, p.second);
}

再看一下一个构造函数:
private:
  typedef hashtable<Value, Value, HashFcn, identity<Value>, 
                    EqualKey, Alloc> ht;
  ht rep;   // 底层机制——hash table
 
public:
  hash_set() : rep(100, hasher(), key_equal()) {}   // 默认大小为100

这里把hash table的表格大小,也就是vector大小设置为了100,那么在初始化hash table时,会自己主动选择最接近的质数为197。也就是说一開始hash_set便拥有了197个“桶”。

以下来比較一下set和hash_set的异同:
set的底层机制为红黑树,hash_set的底层机制为hash table,两者都能进行高效率的搜索。红黑树利用了二叉搜索树的特性,而hash table则利用散列技术。但红黑树有自己主动排序功能而hash table没有,反映出来的结果就是,set的元素有自己主动排序功能而hash_set没有。以下是測试代码:
#include <iostream>
#include <hash_set>
 
using namespace std;
using namespace __gnu_cxx;
 
int main()
{
    hash_set<int> set;
 
    set.insert(3);
    set.insert(196);
    set.insert(1);
    set.insert(389);
    set.insert(194);
    set.insert(387);
 
    hash_set<int>::iterator iter = set.begin();
 
    for ( ; iter != set.end(); ++iter)
        cout << *iter << ' ';
 
    return 0;
}

执行结果:


因为有197个桶,所以元素1、194、387被散列到1号桶;3、196、389被散列到3号桶。但新元素是插入到每一个桶指向的链表的前端,所以就有了这种输出顺序。

參考:
《STL源代码剖析》 P270.

【STL】关联容器 — hash_set