大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。
容器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没有。以下是測试代码：
但红黑树有自己主动排序功能而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.
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118071.html原文链接：https://javaforall.net
