unordered_map和unordered_set的模拟实现

unordered_map和unordered_set的模拟实现

（一）哈希表的特性及概念

定义：
哈希表（Hash table，也叫散列表），是根据关键字值（key,value）直接进行访问的数据结构。也就是说，它通过把关键字映射到表中一个位置来访问的纪录，以加快查找的速度。这个映射函数叫做散列函数，存放纪录的数组叫散列表。

基本原理：
使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。

常见哈希函数

1.直接定制法
取关键字或关键字的某个线性函数值为哈希地址。

H(key) = key 或  H(key) = a*key+b 
1

2.除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函 数：

H(key) = key% p(p<=m)
1

将关键码转换成哈希地址

3.平方取中法
取关键字平方后的中间几位为哈希地址。

4.折叠法
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加 求和，并按散列表表长，取后几位作为散列地址。

5.随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为 随机数函数。 通常应用于关键字长度不等时采用此法 。

6.数学分析法
找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

冲突解决
1.闭散列
也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那 么可以把key存放到冲突位置中的“下一个” 空位置中去。
（1）当要插入一个元素时，连续地检查散列表的个各项，直到找到一个空位置来放置这个元素为止。
（2）当查找一个元素时，要检查所有的表项，直到找到所需的元素，或元素不在表中。
（3）当我们从位置中删除关键字时，不能将此位置元素置空。否则会导致在无法判断此位置是否有元素。应该用个特殊值表示该元素已经删除。

2.开散列
又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码 归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结 点存储在哈希表中。

（二）unordered_map与unordered_set的实现

unordered_set
(1) 哈希函数，需要实现一个class重载operator()，将自定义class变量映射到一个size_t类型的数。一般常用std::hash模板来实现。
(2) 判断两个自定义class类型的变量是否相等的函数，一般在自定义class里重载operator==。
unordered_map
(1) 哈希函数，需要实现一个class重载operator()，将自定义class变量映射到一个size_t类型的数。一般常用std::hash模板来实现。
(2) 判断两个自定义class类型的变量是否相等的函数，一般在自定义class里重载operator==。

template<class K,class V>
class UnorderedMap
{
struct UMapKeyOfValue
{
const K& operator()(const pair<K, V>& data)
{
   return data.first;
    }
 };
public:
 typedef typename HashTable<K, pair<K, V>, UMapKeyOfValue>::iterator iterator;
 iterator begin(){return _mht.begin();
 }
 iterator end(){return _mht.end();
 }
 bool Insert(const pair<K,V>& data){
  return _mht.Insert(data);
 }
private:
 HashTable<K, pair<K, V>, UMapKeyOfValue> _mht;
};

template<class K>
class UnorderedSet
{
struct USetKeyOfValue
{
const K& operator()(const K& data)
{
   return data;
  }
 };
public:
 typedef typename HashTable<K, K, USetKeyOfValue>::iterator iterator;
 iterator begin(){ return _sht.begin();
 }
 iterator end(){ return _sht.end();
 }
bool Insert(const K& key)
{
  return _sht.Insert(key);
 }
private:
 HashTable<K, K, USetKeyOfValue> _sht;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

对哈希表的改造

哈希表的结点定义是只需要一个模板用来表示数据类型, 因为是 K 还是 pair<K,V>后面的仿函数会进行判断。
不同容器V的类型不同，如果是unordered_map，V代表一个键值对，如果是unordered_set,V 为 K // KeyOfValue: 因为V的类型不同，通过value取key的方式就不同 。

表中的几个接口再计算索引的时候需要对节点中的数据进行操控, 所以需要给出仿函数对象,在用重载的 () 进行计算。
哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模 。