1. hashtable

前置知识:【数据结构】3.跳表和散列

基本原理:

  • 将Key计算成一个数值,然后取余数得到它在表头中的位置
  • table(篮子)里每个指针都指向一个链表(桶)来存储余数相同的值
  • 如果桶内的元素个数比篮子个数还多,则将篮子的大小扩充
  • 篮子是vector,数量是质数,初始为53,53扩充后为97

  hashtable需要传入Value(Key+Data),Key,计算哈希的方法,从Value中取出Key的方法,比较Key是否相等的方法,以及分配器来实例化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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指向它在篮子中的位置,实现操作者视角的++操作

1
2
3
4
5
6
7
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 只适用于基本数据类型(包括 string 类型);第三个模板参数中,仅支持可直接用 == 运算符做比较的数据类型

1
2
3
4
5
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中相同

1
2
3
4
5
6
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)
    • - 篮子数量>元素数量,每次扩充复制的时候比较耗时