stl--hashtable

发表于

Hashtable

三种解决冲突的方法

  • 线性探测：当hash之后遇到冲突了，就在下一个位置进行寻找。问题是会遇到聚集。

  • 二次探测：原先遇到冲突，在寻找下一个空位时是按照这样的顺序：H+1,H+2...H+n;而二次探测则是：H+12,H+22...H+n^2。

  • 开链：在每个槽中维持一个链表，hash到同一个槽时就插入链表中。SGI的stl就是用这种方式。但hashtable维持的链不是stl的list，而是自行维护的__hashtable_node

hashtable的迭代器

迭代器的前进操作是从当前节点出发，前进一个位置，如果目前节点恰好是list的尾端，就进入下一个buckets内。注意，hashtable没有后退操作。

hashtable的数据结构

默认使用std::alloc。

1
2
3
template <class Value, class Key, class HashFun, 
            class ExtractKey, class EqualKey, class Alloc = alloc>
class hashtable{}

虽然使用开链法不需要指定table的大小为质数，但SGI stl还是使用了质数。做法就是提供一个函数用以查询最接近于某数n,但大于某数n的质数。

hashtable的构造与内存管理

由这一段代码可知，加入我们需要50个节点，它会返回53个节点（质数）：

1
2
3
4
5
void initialize_buckets(size_type n)
{
    const size_type n_buckets = next_size(n);
    ...
}

进行插入操作时，会判断是否需要重建（resize）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
...::resize(size_type num_elementsz_hint)
{
    //比较新老的size
    const size_type old_n = buckets.size();
    if (num_elementsz_hint > old_n) { //如果新的size比较大
        const size_type n = next_size(num_elementsz_hint);
        if (n > old_n) {
            vector<node*, A> tmp(n, (node*) 0);
            //处理每一个旧的buckets
            //首先是获取bucket的起始节点
            //迭代地将每个节点插在tmp（也就是新的buckets）的起始位置
        }
    }
}

hashfunction

在使用hashfunction时，SGI将其封装成bkt_num()，再由它来调用hash function。通常来说，stl只对char,long,int,short等进行处理。如果要处理其它类型的，必须要提供hashfunction，比如hash