STL源码剖析：Hashtable

hashtable 概述

哈希表是一种数据结构，它提供了快速的数据插入、删除和查找功能。它通过使用哈希函数将键（key）映射到表中的一个位置来实现这一点，这个位置称为哈希值或索引。哈希表使得这些操作的平均时间复杂度为常数时间，即O(1)。

哈希表使用哈希函数将键映射到一个固定大小的数组上。

碰撞

两个不同的键通过哈希函数得到了相同的索引。由于哈希表的大小是有限的，而键的数量可能非常多，所以碰撞是不可避免的。

（1）线性探测：当发生碰撞时，线性探测会在哈希表中按线性顺序搜索下一个空闲位置。

（2）二次探测：与线性探测类似，但是搜索下一个空闲位置时，使用的是二次函数而不是线性函数。

（3）开链：每个哈希表的槽位不直接存储元素，而是存储一个链表。当发生碰撞时，新元素会被添加到对应槽位的链表中。

hashtable实现

hash_table node

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

hashtable 的迭代器

// 定义哈希表迭代器模板结构体
template <class Value, class Key,  class HashFcn,  class ExtractKey, class EqualKey, class Alloc
>
struct hashtable_iterator {// 使用typedef定义相关类型别名，以简化代码typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable_type;typedef hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator_type;typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> const_iterator_type;typedef __hashtable_node<Value> node_type;typedef std::forward_iterator_tag iterator_category;typedef Value value_type;typedef ptrdiff_t difference_type;typedef std::size_t size_type;typedef Value& reference;typedef Value* pointer;// 成员变量node_type* cur; // 当前节点指针hashtable_type* ht; // 指向哈希表的指针// 构造函数hashtable_iterator(node_type* n = nullptr, hashtable_type* tab = nullptr) : cur(n), ht(tab) {}// 解引用操作符，返回当前节点的值reference operator*() const { return cur->val; }// 成员访问操作符，返回当前节点值的指针pointer operator->() const { return &(operator*()); }// 前置++iterator_type& operator++() {// 此处应有逻辑来移动迭代器到下一个节点// ...return *this;}// 后置++iterator_type operator++(int) {iterator_type temp = *this;++(*this); // 使用前置++来实现return temp;}// 相等比较操作符bool operator==(const iterator_type& it) const { return cur == it.cur; }// 不等比较操作符bool operator!=(const iterator_type& it) const { return !(*this == it); }
};

hashtable的数据结构

#include <vector> // For std::vector
#include <cstddef> // For size_t// 定义哈希表类模板
template <class Value,class Key,class HashFcn,class ExtractKey,class EqualKey,class Alloc = Alloc // 注意：这里应该是具体的分配器类名，例如 std::allocator
>
class hashtable {
public:// 为模板型别参数重新定义一个名称typedef HashFcn hasher;typedef EqualKey key_equal;typedef size_t size_type;
private:// 以下三者都是 function objectshasher hash; // 哈希函数对象key_equal equalg; // 键值比较函数对象ExtractKey get_key; // 键提取函数对象typedef hashtable_node<Value> node; // 节点类型定义typedef simple_alloc<node, Alloc> node_allocator; // 节点分配器定义std::vector<node*, Alloc> buckets; // 桶数组，使用 vector 完成size_type num_elements; // 元素数量
public:// 构造函数hashtable():num_elements(0){}// bucket 个数即 buckets vector 的大小size_type bucket_count() const { return buckets.size(); }// 其他成员函数声明...
};// 注意：hashtable_node, simple_alloc 需要被定义
// 注意：Alloc 应该是一个具体的分配器类，例如 std::allocator

虽然开链法(separate chaining)并不要求表格大小必须为质数，但 SGI STL 仍然以质数来设计表格大小，并且先将28 个质数(逐渐呈现大约两倍的关系)计算好，以备随时访问，同时提供一个函数，用来查询在这 28 个质数之中,"最接近某数并大于某数"的质数。

hashtable 的构造,插入，内存分配，拷贝和回收

hashtable类中定义了一个node_allocator类型

typedef simple_alloc<node, Alloc> node_allocator;
node* new_node(const value_type& obj) {node* n = node_allocator::allocate();n->next = 0;STL_TRY{construct(&n->val, obj); return n;}STL_UNWIND(node_allocator::deallocate(n));
}
void delete_node(node* n) {destroy(&n->val);node_allocator::deallocate(n);
}

new_node函数分配内存并构造一个新节点，若构造失败则释放内存。

delete_node函数销毁节点的值并释放内存。

哈希表构造

hashtable<int, int, hash<int>, identity<int>, equal_to<int>, alloc>
iht(50, hash<int>(), equal_to<int>());

创建一个哈希表iht，初始容量为50，使用默认的哈希函数和比较函数。

初始化桶

void initialize_buckets(size_type n) {const size_type n_buckets = next_size(n);buckets.reserve(n_buckets);buckets.insert(buckets.end(), n_buckets, (node*)0);num_elements = 0;
}

initialize_buckets函数根据给定的大小n计算下一个质数作为桶的数量，并初始化桶为null指针。

插入元素 和 重建 hash table

pair<iterator, bool> insert_unique(const value_type& obj) {resize(num_elements + 1);return insert_unique_noresize(obj);
}

insert_unique调用resize检查是否需要扩展哈希表的容量。

void resize(size_type num_elements_hi) {const size_type old_n = buckets.size();if (num_elements_hint > old_n) {const size_type n = next_size(num_elements_hint);if (n > old_n) {vector<node*, A> tmp(n, (node*)0);STL_TRY {for (size_type bucket = 0; bucket < old_n; ++bucket) {node* first = buckets[bucket];while (first) {size_type new_bucket = bkt_num(first->val, n);buckets[bucket] = first->next;first->next = tmp[new_bucket];tmp[new_bucket] = first;first = buckets[bucket];}}}buckets.swap(tmp);}}
}

resize函数决定是否需要扩展哈希表，如果当前元素数量超过桶的数量，则重新配置桶并将现有节点转移到新桶中。

插入不重建

template<class V, class K, class HF, class Ex, class Eq, class A>
typename hashtable<V, K, HF, Ex, Eq, A>::iterator
hashtable<V, K, HF, Ex, Eq, A>::insert_equal_noresize(const value_type& obj) {const size_type n = bkt_num(obj); // 确定 obj 应位于 #n 桶node* first = buckets[n]; // 指向桶对应的链表头部
//遍历链表，查找重复的键值for(node* cur = first;cur;cur=cur->next) {if (equals(get_key(cur->val), get_key(obj))) {// 如果找到重复键值，插入新节点node* tmp = new_node(obj); // 产生新节点tmp->next = cur->next; // 新节点指向当前节点的下一个节点cur->next = tmp; // 将新节点插入到当前节点后面++num_elements; // 节点个数累加1return iterator(tmp, this); // 返回指向新节点的迭代器}}
//若没有找到重复的键值，插入到链表头部node* tmp = new_node(obj); // 产生新节点tmp->next = first; // 新节点指向当前链表的头部buckets[n] = tmp; // 更新桶指向新节点++num_elements; // 节点个数累加1return iterator(tmp, this); // 返回指向新节点的迭代器
}

bkt_num函数的功能

bkt_num系列函数负责将元素映射到哈希表的桶中，确保即使是无法直接对哈希表大小进行模运算的类型（如const char*），也能正确处理。

版本 1：接受实值和桶的数量

size_type bkt_num(const value_type& obj, size_t n) const {return bkt_num_key(get_key(obj), n); // 调用版本 4
}

接收一个元素值和桶的数量，首先提取键值（get_key），然后调用bkt_num_key来计算桶的位置。

版本 2：只接受实值

size_type bkt_num(const value_type& obj) const {return bkt_num_key(get_key(obj)); // 调用版本 3
}

只接受元素值，调用bkt_num_key，不需要提供桶的数量，默认为当前桶的大小。

版本 3: 只接受键值

size_type bkt_num_key(const key_type& key) const {return bkt_num_key(key, buckets.size()); // 调用版本 4
}

版本 4: 接受键值和桶的数量

size_type bkt_num_key(const key_type& key,size_t n) const {return hash(key)%n;//调用哈希函数并取模
}

最基础的版本，接受键值和桶的数量，通过哈希函数计算出键值的哈希值，并对桶的数量进行取模运算，得出最终的桶索引。

哈希表的复制(copy_from)和整体删除(clear)

由于哈希表由向量和链表组成，这两个操作都涉及内存管理。

整体删除 clear

遍历每个桶，逐个删除桶中的所有节点，确保调用delete_node来释放内存。最后将桶的内容设置为null指针，并将节点总数设置为0。注意向量buckets本身并没有释放空间，只是清空了其内容。

template <class V, class K, class HF, class Ex, class Eq, class A>
void hashtable<V, K, HF, Ex, Eq, A>::clear() {// 针对每一个 bucketfor (size_type i = 0; i < buckets.size(); ++i) {node* cur = buckets[i];// 删除 bucket list 中的每一个节点while (cur != 0) {node* next = cur->next;delete_node(cur); // 删除当前节点cur = next; // 移动到下一个节点}// 令 bucket 内容为 null 指针buckets[i] = 0;}num_elements = 0; // 令总节点个数为0// 注意，buckets vector 并未释放掉空间，仍保有原来大小
}

复制 copy_from

复制另一个哈希表的内容。首先清空当前哈希表的buckets向量。预留空间以匹配目标哈希表ht的桶数量。向buckets中插入null指针，初始化每个桶。使用STL_TRY块来处理复制过程，确保在发生异常时能够安全清理。遍历目标哈希表的每个桶，将节点的值复制到新创建的节点中，保持链表结构。最后，更新当前哈希表的节点总数为目标哈希表的节点数量。

template <class V, class K, class HF, class Ex, class Eq, class A>
void hashtable<V, K, HF, Ex, Eq, A>::copy_from(const hashtable& ht) {// 先清除己方的 buckets vectorbuckets.clear(); // 清空当前哈希表的内容// 为己方的 buckets vector 保留空间，使与对方相同buckets.reserve(ht.buckets.size());// 插入 n 个 null 指针buckets.insert(buckets.end(), ht.buckets.size(), (node*)0);STL_TRY {// 针对 buckets vectorfor (size_type i = 0; i < ht.buckets.size(); ++i) {if (const node* cur = ht.buckets[i]) {node* copy = new_node(cur->val); // 复制第一个节点buckets[i] = copy; // 设置当前桶的头节点// 针对同一个 bucket list 复制每一个节点for (node* next = cur->next; next; cur = next, next = cur->next) {copy->next = new_node(next->val); // 复制后续节点copy = copy->next; // 移动到新节点}}}}num_elements = ht.num_elements; // 重新登录节点个数STL_UNWIND(clear()); // 异常时清理资源
}

hashtable 运用实例

// file: hashtable-test.cpp
// 注意：客户端程序不能直接包含 <stl_hashtable.h>，
// 应该包含有用到 hashtable 的容器头文件，例如 <hash_set.h> 或 <hash_map.h>
#include <hash_set> // for hashtable
#include <iostream>
using namespace std;
int main() {// 创建哈希表// <value, key, hash-func, extract-key, equal-key, allocator>// 注意：哈希表没有默认构造函数hashtable<int, int, hash<int>, identity<int>, equal_to<int>, alloc> iht(50, hash<int>(), equal_to<int>());// 输出哈希表的信息cout << iht.size() << endl; // 输出当前元素数量，初始为0cout << iht.bucket_count() << endl; // 输出桶数量，应该是53（第一个质数）cout << iht.max_bucket_count() << endl; // 输出最大桶数量，4294967291// 插入元素iht.insert_unique(59);iht.insert_unique(63);iht.insert_unique(108);iht.insert_unique(2);iht.insert_unique(53);iht.insert_unique(55);// 输出当前元素数量cout << iht.size() << endl; // 应为6// 声明一个哈希表迭代器hashtable<int, int, hash<int>, identity<int>, equal_to<int>, alloc>::iterator ite = iht.begin();// 以迭代器遍历哈希表，输出所有节点的值for (int i = 0; i < iht.size(); ++i, ++ite) {cout << *ite << ' '; // 输出所有节点的值}cout << endl;// 遍历所有桶，输出每个桶的节点个数for (int i = 0; i < iht.bucket_count(); ++i) {int n = iht.elems_in_bucket(i);if (n != 0) {cout << "bucket [" << i << "] has " << n << " elems." << endl;}}// 测试表格重建（rehashing）for (int i = 0; i <= 47; i++) {iht.insert_equal(i); // 插入54个元素}// 输出节点数量和新的桶数量cout << iht.size() << endl; // 应为54cout << iht.bucket_count() << endl; // 应为97// 再次遍历所有桶，输出节点个数for (int i = 0; i < iht.bucket_count(); ++i) {int n = iht.elems_in_bucket(i);if (n != 0) {cout << "bucket [" << i << "] has " << n << " elems." << endl;}}// 再次以迭代器遍历哈希表，输出所有节点的值ite = iht.begin();for (int i = 0; i < iht.size(); ++i, ++ite) {cout << *ite << ';'; // 输出所有节点的值}cout << endl;// 查找元素cout << *(iht.find(2)) << endl; // 查找并输出值为2的节点cout << iht.count(2) << endl; // 输出值为2的节点个数return 0;
}

find函数 和 count函数

find函数

函数用于查找具有特定键值的元素，并返回一个迭代器指向该元素。首先，通过bkt_num_key(key)确定该元素应位于哪个桶(bucket)。接着从该桶的头节点开始循环遍历链表，使用equals函数比较每个节点的键值与目标键值。一旦找到匹配的键值，循环结束，返回一个指向该节点的迭代器。如果未找到匹配，返回的迭代器将指向空。

count函数:

函数用于计算特定键值在哈希表中的出现次数。同样地，首先通过bkt_num_key(key)确定该元素应位于哪个桶。然后，从该桶的头节点开始，循环遍历链表。对于每个节点，使用equals函数判断键值是否与目标键值相同。如果匹配，result计数器加1。最后返回result，即该键值的总出现次数。

//查找元素的迭代器
iterator find(const key_type& key) {size_type n = bkt_num_key(key); // 首先找到元素应该落在哪一个桶内node* first;// 从桶的头部开始，依次比较每个元素的键值for (first = buckets[n]; first && !equals(get_key(first->val), key); first = first->next) {// 循环直到找到匹配的键值，或到达链表末尾}return iterator(first, this); // 返回迭代器，指向找到的节点或为空
}
//计算特定键值的出现次数
size_type count(const key_type& key) const {const size_type n = bkt_num_key(key); // 首先找到元素应该落在哪一个桶内size_type result = 0;// 从桶的头部开始，依次比较每个元素的键值for (const node* cur = buckets[n]; cur; cur = cur->next) {if (equals(get_key(cur->val), key)) {++result; // 如果找到匹配，累加计数}}return result; // 返回特定键值的出现次数
}

hash functions

//hash function 基础定义
template <class Key> struct hash { };
//字符串的哈希计算函数
inline size_t stl_hash_string(const char* s) {unsigned long h = 0;for (; *s; ++s) {h = 5 * h + *s; // 计算哈希值}return size_t(h);
}
//针对不同类型的哈希函数实现,对于char*类型的哈希函数
STL_TEMPLATE_NULL struct hash<char*> {size_t operator()(const char* s) const { return stl_hash_string(s); }
};
//对于 const char* 类型的哈希函数
STL_TEMPLATE_NULL struct hash<const char*> {size_t operator()(const char* s) const { return stl_hash_string(s); }
};
//对于单字符类型的哈希函数
STL_TEMPLATE_NULL struct hash<char> {size_t operator()(char x) const { return x; }
};
//对于无符号字符类型的哈希函数
STL_TEMPLATE_NULL struct hash<unsigned char> {size_t operator()(unsigned char x) const { return x; }
};
//对于有符号字符类型的哈希函数
STL_TEMPLATE_NULL struct hash<signed char> {size_t operator()(signed 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<unsigned int> {size_t operator()(unsigned int x) const { return x; }
};
//对于长整型的哈希函数
STL_TEMPLATE_NULL struct hash<long> {size_t operator()(long x) const { return x; }
};
//对于无符号长整型的哈希函数
STL_TEMPLATE_NULL struct hash<unsigned long> {size_t operator()(unsigned long x) const { return x; }
};

对于整型和字符型数据，哈希函数通常直接返回原值。

对于字符串，调用 stl_hash_string 函数以计算哈希值（每位的ascii码值然后乘以5）。

SGI hashtable 无法处理上述所列各项型别以外的元素，例如string,double,float。欲处理这些型别，用户必须自行为它们定义 hash function。