1. hashtable
前置知识：【数据结构】3.跳表和散列
基本原理：
- 将Key计算成一个数值，然后取余数得到它在表头中的位置
- table（篮子）里每个指针都指向一个链表（桶）来存储余数相同的值
- 如果桶内的元素个数比篮子个数还多，则将篮子的大小扩充
- 篮子是vector，数量是质数，初始为53，53扩充后为97
hashtable需要传入Value(Key+Data)，Key，计算哈希的方法，从Value中取出Key的方法，比较Key是否相等的方法，以及分配器来实例化
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;
ExtractKey get_key;
typedef __hashtable_node<Value> node;
vector<node*, Alloc> bucket;
size_type num_element;
public:
size_type bucket_count() const {return bucket.size(); }
};
template <class Value>
struct __hashtable_node {
__hashtable_node* next;
Value val;
};
hashtable的篮子使用vector数组实现，迭代器中有两个指针，*cur指向当前元素位置，*ht指向它在篮子中的位置，实现操作者视角的++操作
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
//...
node* cur;
hashtable* ht;
// ...
};
2. unordered_set / multi
第二个模板参数中，C++底层提供的哈希函数 hash<Key> 只适用于基本数据类型（包括 string 类型）；第三个模板参数中，仅支持可直接用 == 运算符做比较的数据类型
template < class Key, //容器中存储元素的类型
class Hash = hash<Key>, //确定元素存储位置所用的哈希函数
class Pred = equal_to<Key>, //判断各个元素是否相等所用的函数
class Alloc = allocator<Key> //指定分配器对象的类型
> class unordered_set;
3. unordered_map / multi
Key是键值对中的键、T是键值对中的data，<Key, T>组成hashtable中的Value。接下来的模板参数与unordered_set中相同
template < class Key, //键值对中键的类型
class T, //键值对中值的类型
class Hash = hash<Key>, //容器内部存储键值对所用的哈希函数
class Pred = equal_to<Key>, //判断各个键值对键相同的规则
class Alloc = allocator< pair<const Key,T> > // 指定分配器对象的类型
> class unordered_map;
4. unordered_map 和 map 对比
- map / set ，底层实现是红黑树
- + 自带排序的性质
- + 查找的时间复杂度是O(logn)
- - 每个节点都需要存储额外的信息
- unordered_map / unordered_set，底层是哈希表
- + 哈希表通过Key计算查找非常快 理想情况下是O(1)
- - 篮子数量>元素数量，每次扩充复制的时候比较耗时