STL源码阅读(八) (SGI STL v3.3)
stl_hash_fun.h (<functional> C++11)
字符串的散列与整型值的散列，C++11有个hash仿函数，支持更多的功能。
整型值的散列函数：f(x) = x
字符串的散列函数：f(s) = 5*f(s+1) + *s，当len(s)==1, 则f(s)=*s；其中s是指向字符串的指针。
// 示例
inline size_t __stl_hash_string(const char* __s)
{
unsigned long __h = 0;
for ( ; *__s; ++__s)
__h = 5*__h + *__s;
return size_t(__h);
}
template<> struct hash<int> {
size_t operator()(int __x) const { return __x; }
};
hash_table.h
SGI hash_table碰撞检测方法是链接法，散列表的每个槽都包含一个链表(见《算法导论》第11章 散列表)。
// 哈希表结点
template <class _Val>
struct _Hashtable_node
{
_Hashtable_node* _M_next;
_Val _M_val;
};
// 迭代器类型，前向迭代器
template <class _Val, class _Key, class _HashFcn,
class _ExtractKey, class _EqualKey, class _Alloc>
struct _Hashtable_iterator {
...
typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> _Hashtable;
typedef forward_iterator_tag iterator_category;
typedef _Hashtable_node<_Val> _Node;
_Node* _M_cur; // 指向当前结点
_Hashtable* _M_ht; // 指向当前槽
...
}
// 迭代器++实现
template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&
_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++() {
const _Node* __old = _M_cur;
_M_cur = _M_cur->_M_next; // 当前槽中的链表的下一个结点
if (!_M_cur) { // 如果下一个结点为NULL，寻找下一个槽
size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
_M_cur = _M_ht->_M_buckets[__bucket]; // 该槽指向的链表的第一个结点便是下一个迭代的元素
}
return *this;
}
// 散列表初始大小，全部为质数
enum { __stl_num_primes = 28 };
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
template <class _Val, class _Key, class _HashFcn,
class _ExtractKey, class _EqualKey, class _Alloc>
class hashtable {
...
public:
typedef _Key key_type;
typedef _Val value_type;
typedef _HashFcn hasher;
typedef _EqualKey key_equal;
private:
typedef _Hashtable_node<_Val> _Node;
private:
hasher _M_hash; // 散列函数对象
key_equal _M_equals; // 判断键值是否相等
_ExtractKey _M_get_key; // 提取键值
vector<_Node*,_Alloc> _M_buckets; // 散列槽，每个槽包含一个单项链表
size_type _M_num_elements; // 哈希表元素个数
// 散列对象(实际是散列键值)
size_type _M_bkt_num_key(const key_type& __key) const {
return _M_bkt_num_key(__key, _M_buckets.size());
}
size_type _M_bkt_num(const value_type& __obj) const {
return _M_bkt_num_key(_M_get_key(__obj));
}
size_type _M_bkt_num_key(const key_type& __key, size_t __n) const {
return _M_hash(__key) % __n; // 哈希表的大小取质数以减小碰撞的可能
}
size_type _M_bkt_num(const value_type& __obj, size_t __n) const {
return _M_bkt_num_key(_M_get_key(__obj), __n);
}
// 注意赋值操作先将原哈希表清空，然后再赋值
hashtable& operator= (const hashtable& __ht)
{
if (&__ht != this) {
clear();
_M_hash = __ht._M_hash;
_M_equals = __ht._M_equals;
_M_get_key = __ht._M_get_key;
_M_copy_from(__ht);
}
return *this;
}
void swap(hashtable& __ht)
{
__STD::swap(_M_hash, __ht._M_hash);
__STD::swap(_M_equals, __ht._M_equals);
__STD::swap(_M_get_key, __ht._M_get_key);
// 这里swap是交换了槽中的指针，而不是交换了哈希表中实际的元素
_M_buckets.swap(__ht._M_buckets);
__STD::swap(_M_num_elements, __ht._M_num_elements);
}
...
}
// 注意：resize时候，只有当resize的大小大于原哈希表的大小，才调整大小。而当resize的大小
// 小于原哈希表时，不采取任何操作。
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::resize(size_type __num_elements_hint) {
const size_type __old_n = _M_buckets.size();
if (__num_elements_hint > __old_n) {
const size_type __n = _M_next_size(__num_elements_hint);
if (__n > __old_n) {
vector<_Node*, _All> __tmp(__n, (_Node*)(0),
_M_buckets.get_allocator());
__STL_TRY {
for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
_Node* __first = _M_buckets[__bucket];
while (__first) {
// 哈希表的容量(槽数量)已发生改变，所以需要重新散列化
size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
_M_buckets[__bucket] = __first->_M_next;
__first->_M_next = __tmp[__new_bucket];
__tmp[__new_bucket] = __first;
__first = _M_buckets[__bucket];
}
}
_M_buckets.swap(__tmp);
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) {
while (__tmp[__bucket]) {
_Node* __next = __tmp[__bucket]->_M_next;
_M_delete_node(__tmp[__bucket]);
__tmp[__bucket] = __next;
}
}
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
}
}
}
// 一下几种插入方式
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, bool>
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::insert_unique_noresize(const value_type& __obj) {
const size_type __n = _M_bkt_num(__obj);
_Node* __first = _M_buckets[__n];
// 所要插入的元素散列到的槽指向的链表中不包含该元素(键值)，才会插入成功
for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
return pair<iterator, bool>(iterator(__cur, this), false);
_Node* __tmp = _M_new_node(__obj);
__tmp->_M_next = __first;
_M_buckets[__n] = __tmp;
++_M_num_elements;
return pair<iterator, bool>(iterator(__tmp, this), true);
}
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::insert_equal_noresize(const value_type& __obj) {
const size_type __n = _M_bkt_num(__obj);
_Node* __first = _M_buckets[__n];
// 可以插入已经重复的元素(键值)。如果有重复元素，则插入第一个相同元素的后面
for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) {
_Node* __tmp = _M_new_node(__obj);
__tmp->_M_next = __cur->_M_next;
__cur->_M_next = __tmp;
++_M_num_elements;
return iterator(__tmp, this);
}
_Node* __tmp = _M_new_node(__obj);
__tmp->_M_next = __first;
_M_buckets[__n] = __tmp;
++_M_num_elements;
return iterator(__tmp, this);
}
// 只有两个哈希表中大小相等，且所有对应槽链表中元素的都相等，这两个哈希表才相等
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1,
const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2) {
typedef typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::_Node _Node;
if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
return false;
for (int __n = 0; __n < __ht1._M_buckets.size(); ++__n) {
_Node* __cur1 = __ht1._M_buckets[__n];
_Node* __cur2 = __ht2._M_buckets[__n];
for ( ; __cur1 && __cur2 && __cur1->_M_val == __cur2->_M_val;
__cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
{}
if (__cur1 || __cur2)
return false;
}
return true;
}
// clear只是清除所有链表中的结点，并不会清除槽_M_buckets，槽是一个vector<_Node*, _Alloc>的成员变量
// 调用hashtable的析构函数时，会自动释放槽的内存
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::clear()
{
for (size_type __i = 0; __i < _M_buckets.size(); ++__i) {
_Node* __cur = _M_buckets[__i];
while (__cur != 0) {
_Node* __next = __cur->_M_next;
_M_delete_node(__cur);
__cur = __next;
}
_M_buckets[__i] = 0;
}
_M_num_elements = 0;
}
// erase只是擦除指定位置或指定键值的结点，并不会擦除槽
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::size_type
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const key_type& __key) {
const size_type __n = _M_bkt_num_key(__key);
_Node* __first = _M_buckets[__n];
size_type __erased = 0;
if (__first) {
_Node* __cur = __first;
_Node* __next = __cur->_M_next;
while (__next) {
if (_M_equals(_M_get_key(__next->_M_val), __key)) {
__cur->_M_next = __next->_M_next;
_M_delete_node(__next);
__next = __cur->_M_next;
++__erased;
--_M_num_elements;
}
else {
__cur = __next;
__next = __cur->_M_next;
}
}
if (_M_equals(_M_get_key(__first->_M_val), __key)) {
_M_buckets[__n] = __first->_M_next;
_M_delete_node(__first);
++__erased;
--_M_num_elements;
}
}
return __erased;
}
stl_hash_map.h (<unordered_map> C++11)
// 无序关联容器hash_map，由哈希表实现，相当于hashtable的包装类，对应于C++11中的unordered_map。
// hash_map中的键值是无序的，每一个键值都是唯一的。
template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc>
class hash_map {
...
private:
typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn,
_Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht;
_Ht _M_ht;
...
...
}
// 对应于C++11中的unordered_multimap，键值可以重复
template <class _Key, class _Tp, class _HashFcn, class _EqualKey,
class _Alloc> class hash_multimap {
...
private:
typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn,
_Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
_Ht;
_Ht _M_ht;
...
}stl_hash_set.h
// 对应于C++11中的unordered_set，每一个值都是唯一的
template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
class hash_set {
...
typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
_EqualKey, _Alloc> _Ht;
_Ht _M_ht;
...
}
// 对应于C++11中的unordered_multiset，可以有重复的值
template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
class hash_multiset {
...
typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
_EqualKey, _Alloc> _Ht;
_Ht _M_ht;
...
}