SGI STL 标准库 hashtable 9

hashtable

hashtable使用一段连续空间存储元素,元素的下标使用散列函数计算得出,如果不同元素通过散列函数映射到相同位置,可通过线性探测、二次探测、开链等方法解决。
负载系数:元素个数除以数组大小。
线性探测:如果通过散列函数计算的插入位置已被使用,最简单的方法就是循序往下寻找到一可用空间为止(如果到了尾部,就从头再找起)。最坏情况是遍历整个数组。由于每次都顺序加一查找可用空间,导致主集团问题。
二次探测:如果通过散列函数计算的插入位置已被使用,再查找可用位置时不再循序查找,而是按照2的幂次方尝试,即每次前进n^2。二次探测解决主集团问题,但可能导致次集团问题。
线性探测和二次探测的负载系数永远在0-1之间。
开链:在每个表格元素中维护一个list,当有元素时,将元素加入到list中,如果list足够短,其效率并不慢。可以和二次探测的效率相提并论。
SGISTL采用开链法实现hashtable。开链法的负载系数可能会大于1。

hashtable 的buckets和nodes


用开链法完成的hashtable

1
2
3
4
5
6
7
//hashtable 节点
template <class _Val>
struct _Hashtable_node
{
_Hashtable_node* _M_next;
_Val _M_val;
};

buckets以vector作为容器,以便有动态扩充能力,nodes自身实现单链表相连接。

hashtable的迭代器


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//hashtable迭代器
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 _Hashtable_iterator<_Val, _Key, _HashFcn,
_ExtractKey, _EqualKey, _Alloc>
iterator;
typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
_ExtractKey, _EqualKey, _Alloc>
const_iterator;
typedef _Hashtable_node<_Val> _Node;

typedef forward_iterator_tag iterator_category;
typedef _Val value_type;
typedef ptrdiff_t difference_type;
typedef size_t size_type;
typedef _Val& reference;
typedef _Val* pointer;

_Node* _M_cur; //迭代器目前所指之节点
_Hashtable* _M_ht; //保持对容器的联结关系(因为可能需要从bucket调到bucket)

_Hashtable_iterator(_Node* __n, _Hashtable* __tab)
: _M_cur(__n), _M_ht(__tab) {}
_Hashtable_iterator() {}
reference operator*() const { return _M_cur->_M_val; }
pointer operator->() const { return &(operator*()); }
iterator& operator++();
iterator operator++(int);
bool operator==(const iterator& __it) const
{ return _M_cur == __it._M_cur; }
bool operator!=(const iterator& __it) const
{ return _M_cur != __it._M_cur; }
};

hashtable的迭代器没有operator—,也就没有定义逆向迭代器。

hashtable数据结构


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//开链法并不要求数组数组大小必须为质数,但SGISTL仍以质数设计数组大小,并将28个质数计算好,
//以备随时访问,并提供一个函数,用来查询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
};

//找出28个质数中,最接近并大于n的那个质数
inline unsigned long __stl_next_prime(unsigned long __n)
{
const unsigned long* __first = __stl_prime_list;
const unsigned long* __last = __stl_prime_list + (int)__stl_num_primes;
const unsigned long* pos = lower_bound(__first, __last, __n);
return pos == __last ? *(__last - 1) : *pos;
}

// _Val 节点的实值型别 _Key 节点的键值类型 _HashFcn hash function的函数型别
// _ExtractKey 从节点中取出键值的方法 _EqualKey 判断键值相同的与否的方法
// _Alloc 空间配置器,缺省使用std::alloc
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;

typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;

hasher hash_funct() const { return _M_hash; }
key_equal key_eq() const { return _M_equals; }
//......

private:
hasher _M_hash;
key_equal _M_equals;
_ExtractKey _M_get_key;
vector<_Node*,_Alloc> _M_buckets; //buckets以vector作为容器
size_type _M_num_elements;
//......
};

hashtable的构造与内存管理


以下具体见源码解析

  • 插入操作和表格重整

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //插入元素,不允许重复
    pair<iterator, bool> insert_unique(const value_type& __obj)
    {
    //判断是否需要重建buckets,如果需要就扩充
    resize(_M_num_elements + 1);
    return insert_unique_noresize(__obj);
    }

    //插入元素,允许重复
    iterator insert_equal(const value_type& __obj)
    {
    //判断是否需要重建buckets,如果需要就扩充
    resize(_M_num_elements + 1);
    return insert_equal_noresize(__obj);
    }
  • 元素hash

    1
    2
    3
    4
    5
    //计算元素在buckets中的位置 包装hash function
    size_type _M_bkt_num(const value_type& __obj) const
    {
    return _M_bkt_num_key(_M_get_key(__obj));
    }
  • hashtable拷贝与清空

    1. clear()
    2. _M_copy_from()

hash function


<stl_hash_fun.h>定义数个现成的hash function全都是仿函数。