数据结构——Hash表

1、哈希函数

哈希函数是一个映射，将关键字key映射到某一地址，可以直接确定查找值所在位置，addr = H(key)；

比较直观的一个运用是知道数值范围时的桶排序，给定n个输入0<= a₁，a₂，...，a_n<m，定义一个长度为m的数组，a_i的值就对应其在数组中的位置，可以在O(n+m)的时间内对元素进行排序。

2、哈希冲突

哈希函数是非单设函数，不同的key可能得到相同的addr值，这就发生了冲突，解决冲突有一以下几种常用方法：

开放地址法：若H₀=H(key)冲突，则取H_i=(H(key) + d_i) % M，直至不冲突，M一般为不超过过表大小的最大素数，d_i的取法一般有：
- 线性探测：d_i=i*c
- 平方探测：d_i=1²，-1²，2²，-2²,...，在初始地址周围来回摆动
- 随机探测：di为一组伪随机数序列
链地址法：对于相同地址的key值，用一个链表把它们链接起来
公共溢出区法：建立专门的空间用于存储冲突的key值
再散列法：实现多个hash函数，若H₁(key)冲突，则计算H₂(key)，直至不冲突

装填因子α：当表中元素个数>α*M时，需要增加表的大小，同时需要为表中元素重新定址，是相对耗时的操作；

各方法优缺点：

链地址法处理冲突简单，非同义词决不会发生冲突，因此平均查找长度较短；
由于链地址法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
开放地址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间；
而链地址法中可取α>=1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
用链地址法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可;
开放地址法在删除节点时不能直接删除，因为会切断后续元素的查找通路，只能打标记（如cpython dict实现中的Dummy标记）

3、哈希表效率

一般情况下hash表的查找效率能够达到O(1)。

4、编程语言中hash表的一些应用

Python：cpython的dict采用哈希表实现，采用开放地址法解决哈希冲突；
Java：HashMap采用哈希表实现，采用链地址法解决冲突，在JDK1.8版本中做了进一步的优化，引入了红黑树，而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能；
C++：unordered_map采用哈希表实现，采用链地址法解决冲突；

5、其他应用

实现LRU（Least Recently Used）算法：LRU空间为K，可以增加键值和访问键值，当每增加或访问时该键变为最常使用的，当新增键值时若空间不够，则先删除一个最不常使用的键；要求增加和访问操作的时间复杂度均为O(1)。

分析：

用unordered_map来存储键值，插入、删除、访问效率为O(1)；
重点是如何更新最近最常使用的键，使得其效率为O(1)？采用unoredered_map+双向链表的方式

设N为操作个数，K为LRU大小，操作有两种，用1表示set操作，2表示get操作，输入格式为：

N, K           # N次操作，LRU大小为K，以下N行为N个操作
1 key value    # set 操作，若key存在，则重置值为value，否则插入（key，value）
2 key          # get 操作，若key存在，返回对应的value，否则返回-1
...

基于C++的代码示例如下：

  1 # include<iostream>
  2 # include<vector>
  3 # include<unordered_map>
  4 using namespace std;
  5 
  6 struct Node{
  7     int val;
  8     Node* last;
  9     Node* next;
 10     Node(int x): val(x), next(NULL), last(NULL){}
 11 };
 12 
 13 class LRU{
 14     private:
 15         int K;                                 // LRU大小 
 16         Node* head = NULL;                     // 头指针，最不常使用 
 17         Node* tail = NULL;                     // 尾指针，最常使用 
 18         unordered_map<int, int> maps;          // 存储键值对 
 19         unordered_map<int, Node*> visit_nodes; // 存储每个键对应的节点地址 
 20     
 21     public:
 22         LRU(int k){ K = k;}
 23         
 24         void print_lru(){
 25             Node * p = head;
 26             while(p){
 27                 if(p->last) cout << "(" << p->last->val << ")";
 28                 else cout << "(-)";
 29                 cout << "[" << p->val << "," << maps[p->val] << "]";
 30                 if(p->next) cout << "(" << p->next->val << ")";
 31                 else cout << "(-)";
 32                 if(p->next) cout << " -> ";
 33                 p = p->next;
 34             }
 35             cout << endl;
 36         }
 37         
 38         void add_visit(int key, int val){
 39             // 第一个加入的键 
 40             if(!head){
 41                 head = new Node(key);
 42                 tail = head;
 43                 visit_nodes[key] = tail; 
 44             }
 45             else{
 46                 Node* cur = new Node(key);
 47                 cur->last = tail;
 48                 tail->next = cur;
 49                 tail = cur;
 50                 visit_nodes[key] = tail;
 51             }
 52         }
 53         
 54         // 大小不够时，删除链表头的最不常使用键 
 55         void remove_visit(){
 56             if(!head) return;
 57             Node* p = head->next;
 58             visit_nodes.erase(head->val);
 59             free(head);
 60             
 61             // 链头更新 
 62             head = p;
 63             if(!head) return;
 64             head->last = NULL;
 65         }
 66         
 67         // 更新或者访问key时，将其放置在链表最后，成为最常访问键 
 68         void update_visit(int key){
 69             Node* cur = visit_nodes[key];
 70             // 当前key本来就是最常使用的 
 71             if(cur->next == NULL) return;
 72             
 73             // 删除当前节点 
 74             cur->next->last = cur->last;
 75             if(cur->last) cur->last->next = cur->next;
 76             else head = cur->next;
 77             
 78             // 将当前节点放在最后
 79             cur->last = tail;
 80             cur->next = NULL;
 81             tail->next = cur;
 82             tail = cur; 
 83         }
 84         
 85         int get(int key){
 86             if(maps.count(key) <= 0) return -1;
 87             update_visit(key);
 88             return maps[key]; 
 89         }
 90         
 91         void set(int key, int val){
 92             // 当前键已经在map中了 
 93             if(maps.count(key) > 0){
 94                 maps[key] = val;
 95                 update_visit(key);
 96             }
 97             // 新键值 
 98             else{
 99                 // 空间不够，需先移除最不常使用元素 
100                 if(maps.size() >= K){
101                     maps.erase(head->val);
102                     remove_visit();
103                 }
104                 maps[key] = val;
105                 add_visit(key, val);
106             }    
107         }
108 };
109 
110 int main(){
111     int N, K, opt, key, val;
112     cin >> N >> K;
113     LRU lrus(K);
114     
115     for(int i = 0; i < N; i++){
116         cin >> opt;
117         if(opt == 1){
118             cin >> key >> val;
119             lrus.set(key, val);
120         }
121         else{
122             cin >> key;
123             lrus.get(key);
124         }
125         lrus.print_lru();    
126     }
127     return 0;
128 }

测试输出：