STL源码：hashtable

一时失言乱红尘 2022-08-07 10:45 265阅读 0赞

前面介绍的RB-tree红黑树中，可以看出红黑树的插入、查找、删除的平均时间复杂度为O(nlogn)。但这是 **基于一个假设：输入数据具有随机性**。 **而哈希表/散列表hash table在插入、删除、查找上具有“平均常数时间复杂度”O(1)；且不依赖输入数据的随机性**。

hash函数会带来一个问题：可能有不同的元素被映射到相同位置，这就是碰撞问题。**解决碰撞的方法很多**，hash table的实现有线性探测、二次探测、二次散列等实现，**SGI的STL是采用开链法(separate chaining)来实现的**。大概原理就是在hash table的每一项都是个指针（指向一个链表list），叫做bucket。这样的话如果多个key值散列到同一位置，那么就存储到这个位置对应的链表中。list执行元素插入、搜索、删除等操作，虽然list进行搜索时是线性操作，但是list足够短的话，速度还是很快。结构如下。

![Center][]

注意：bucket维护的**linked list不是STL的list或slist，而是自己维护的hash table node**。buckets聚合体，则以vector完成，以便于动态扩充。vector容器大小是质数（因为散列函数好多情况下是取余数）。

hash table的节点定义：

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

**hash函数**

hash函数时用于计算元素位置的函数，SGI将这项任务赋予bkt\_num()，再由它来调用hash函数，取得一个可以对hashtable进行模运算的值。对于char，int， long等整型数据，hash函数什么也没做，只是忠诚地返回原值。但对于字符串（const char \*），设计了转型函数，见下图。<stl\_hash\_fun.h>定义了数个现成的hash函数。

![Center 1][]

**SGI所定义的所有hash函数如下图，SGI hashtable无法处理其他类型的元素，例如string，double，float等，若要处理这些类别，用户必须自己定义hash函数**。

现在这个说法是不正确的，因为标准库已经增加了很多类型hash的支持，因此不限于上边说的那些了，详情看最后一幅图或参考[http://en.cppreference.com/w/cpp/utility/hash][http_en.cppreference.com_w_cpp_utility_hash]

![Center 2][]

![Center 3][]

目前C++标准库支持hash函数的元素类型：

![Center 4][]

[Center]: /images/20220805/212cd6193ce4479d90339ea6320fc9b1.png
[Center 1]: /images/20220805/8d21943b704d450ca82101d0664d335c.png
[http_en.cppreference.com_w_cpp_utility_hash]: http://en.cppreference.com/w/cpp/utility/hash
[Center 2]: /images/20220805/7b05c6aa408b4232a005e2ae76ef1126.png
[Center 3]: /images/20220805/036c96b96da840d28d8aef4656636653.png
[Center 4]: /images/20220805/57b743a3f6ab4fa589d2b6aac17e097e.png