STL源码笔记10哈希表hashtable探究

00 写在前面

平衡二叉搜索树中的RB-tree作为一种效率表现和复杂度很平衡的结构，一直被用作STL set和map的底层支持。
【STL源码剖析】总结笔记（8）：红黑树（RB-tree）探究
【STL源码剖析】总结笔记（9)：set/multiset与map/multimap

而还有一种结构，哈希表（以下称hashtable），在数据具有足够的随机性时，也能够保持在插入删除等操作上的“常数平均时间”表现。也是unordered结构的基础。

hashtable更多的是经验设计

01 概述

hashtable是非常常见的数据结构，大家在数据结构课程中也有接触。hash table是一种字典结构。

假设我们有一大堆元素要存入数组，那么可以构造一个简单的array便可以实现。

但是当数据量变大时，需要申请巨大的空间可能不太现实，这个时候就要考虑另一种存储方式了。

映射函数是一种方法，将大数映射为小数。

如果数组长度为tablesize，那么x%tablesize得到的数可以作为这个数x的索引。

解决碰撞

这种hash function会有一个问题，就是在元素增多时会不可避免地出现多个元素映射到同一个位置的情况。这种情况也叫做“碰撞”。常用的解决碰撞的方法有以下几种：

1. 线性探测

   当使用hash function计算出位置后发现该位置已经没有空间时，会继续向下一个一个地寻找可以放入元素的位置。如果到达尾部就再从头开始。

   这个方法简单易懂，但也有一个很直观的问题：在很多空位都被占用后，就会出现一个新元素疯狂撞墙最后才插入成功的现象，增加了平均插入成本。

2. 二次探测

   二次探测说的是，既然一个一个的探测会出现问题，那么就以二次方的形式探测。原来是h 1,h 2…现在就变为h （1的平方），h （2的平方）…

   很明显这样的探测法跳跃起来了，不会出现连续撞墙的现象，效果会好很多。但还是会出现在两个元素计算出的位置相同时，探测位置也相同而产生的效率浪费。

3. 开链

   开链是指在表格中单独维护一个list，让计算位置相同的元素形成一个链。这也是SGI STL中hash table的实现方法。我们单独提出说。
   
   

02 开链在hashtable中的运用

hash table的形式如图：

这种形式有很多“经验之谈”（一种大家都遵守的设计规范但是依据未知）

比如整个buckets这个vector的大小一般为质数。

还有我们可以看出来在重叠的元素变多后，这种链式结构需要维护很长的链表。那么这个时候的搜索效率就会很低。

所以有一条规则是：当元素的个数大于buckets的空间个数时，就会把buckets成2倍扩增，然后再调整为质数。这样重新计算后可以很好地把长链变短。

其实再STL中这些数是规定好的，我们可以看一下。

static const int _stl_num_primes=28;
static const unsigned long _stl_prime_list[_stl_num_primes]={
    53,97,193,389,769,1543,3079,6151,12289,24593,1572869,3145739,6291469...
}

03 hashtable的结构

hash table的结构如下：

template <class Value,class Key,class HashFcn,class ExtractKey,class EqualKey,class Alloc=alloc>
class hashtable{
public:
    typedef HashFcn hasher;
    typedef EqualKey key_equal;
    typedef size_t size_type;
private:
    hasher hash;
    key_equal equals;
    ExtratKey get_key;
    
    typedef _hashtable_node<Value>node;
    
    vector<node*,Alloc>buckets;
    size_type num_elements;
    ...
}

hashtable有很多个模板参数，来看一下。

1. Value：节点的实值
2. Key：节点的键值
3. HashFcn：hash function，用来得到元素的编号（也就是要放在哪儿）
4. ExtractKey：取出key的方法，有点类似红黑树中的getofvalue。
5. EqualKey：判断key是否相同的方法

下面的_hashtable_node是hashtable的节点结构，包含next指针和value

template <class Value>
struct _hashtable_node{
    _hashtable_node* next;
    Value val;
}

继续往下可以看到buckets就是使用vector实现的。

我们也可以计算一下hashtable的大小：

三个方法（函数或者仿函数）的大小是3。vector里有三个指针，大小是12。size_type大小是4。总大小为19，为了对齐系统会调整为20。

04 hash function

hash function的重要任务是找到元素的落脚点，也就是计算后应该放到哪里。

我们都知道计算过程与是一个取模过程，但是也会有一些不同。比如遇到字符和字符串这种类型就不能进行单纯的计算了。

在STL包装了一个函数bkt_num()，在此函数中调用hash function。

size_type bkt_num_key(const key_type& key,size_t n)const
{
    return hash(key)%n;
}

这里的hash运用了偏特化的设计方法（在traits见过的设计方法）

根据传入的值设定不同的做法。（大部分不需要改动，直接返回原值再取模即可）

//泛化版本
template <class Key> struct hash{};

//特化版本
_STL_TEMPLATE_NULL struct hash<char>{
    size_t operator()(char x)const {return x;}
}
_STL_TEMPLATE_NULL struct hash<short>{
    size_t operator()(short x)const {return x;}
}
_STL_TEMPLATE_NULL struct hash<unsigned short>{
    size_t operator()(unsigned short x)const {return x;}
}
_STL_TEMPLATE_NULL struct hash<int>{
    size_t operator()(int x)const {return x;}
}

...

上面这些都是不需要改动的，直接传回原值。

下面来看需要改动的做法（对于字符字符串）：

_STL_TEMPLATE_NULL struct hash<char*>{
    size_t operator()(const char* s)const {return _stl_hash_string(s);}
}

_STL_TEMPLATE_NULL struct hash<const char*>{
    size_t operator()(const char* s)const {return _stl_hash_string(s);}
}

再跳转到_stl_hash_string(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);
    }
}

看不懂这个做法很正常，因为这本身就是很随机的一段代码。

举个例子，我们现在有字符串abc，那么这个结果就会算出5*（5*a b） c，这里的abc是acsii码。

因为hash function就是要求出一个元素的编码以找到合适的位置，所以这个做法就是计算出一个足够乱且不容易重复的值。

05 hashtable的迭代器

最后再来说一说hashtable的迭代器。

因为节点中有next指针，所以可以很轻松地跳转到下一个位置。

node* cur;
hashtable* ht;

在iterator中有两个指针，第一个是指向当前list中节点的指针。

而第二个指针是用来在buckets之间跳转的，因为当到达list的尾部时就需要跳转到下一个bucket。这里有点像deque的控制中心。

再插一句题外话，因为hashtable只可以向前走（因为只有next），所以它的类型我们也很容易知道。

typedef forward_iterator_tag iterator_category;

06 unordered

对于unordered容器来说，其底层实现就是hashtable。原来非标准的名称为hash set/multiset和hash map/multimap。

这里我们看一下hash set/multiset和hash map/multimap的实现。和前面的set/multiset，map/multimap类似，都可以看作容器适配器。

hash set/multiset

hashset的底层是依靠hashtable实现的，但是和红黑树不一样的是hashtable不具有自动排序功能，这也是unordered的由来。

hashset的使用方法与set相同。

template <class Value,class HashFcn=hash<Value>,class EqualKey=equal_to<Value>,class Alloc=alloc>class hash_set{private:    typedef hashtable<Value,Value,HashFcn.identity<Value>,EqualKey,Alloc>ht;    ht rep;    ...}

可以看到hashset将key和value设定为同一值，然后在底层直接调用hashtable实现。

同理，hash multiset与hashset的不同在于插入函数，前者使用的是insert_equal()，而后者使用的是insert_unique()。

hash multiset与multiset的唯一区别在于hash multiset的元素不会自动排序。

hash map/multimap

map和set的区别就是键值不同，在参数方面和红黑树很类似。

template<class Key,class T,class HashFcn=hash<Key>,class EqualKey=equal_to<key>,class Alloc=alloc>class hash_map{private:    typedef hashtable<pair<const Key,T>,Key,HashFcn,select1st<pair<const Key,T>>,EqualKey,Alloc>ht;    ht rep;}

这里和我们前面在红黑树说到的const用法是一致的，最后的map保存两部分，一部分是key，另一部分是key和data组成的value。

hashmap的使用方法与map相同。

hash multimap与multimap的唯一区别在于hash multiset的元素不会自动排序。

这篇好文章是转载于：学新通技术网