什么是哈希？

从原理到应用分析什么是哈希？

一、什么是哈希？

哈希（hash）：将任意长度的输入（关键字），通过Hash算法变成固定长度的输出。这个映射的规则就是对应的Hash算法，而原始数据映射后的二进制串就是哈希值，通常哈希值代表了关键字的存储位置。

但是为什么要这样做呢？或者说，哈希是怎样来的呢？

哈希的出现解决了两个问题：存储和搜索。

1. 存储（数据结构）：如果在容器中保存对象及其关联的键，并且不用键来决定 （键/对象） 对的顺序，那就必须对键值釆用其他方式来确定元素在内存中的位置。

如果使用像 string 这样的对象作为键，就会遇到一些问题，可能的变量的数目是巨大的。具有 10 个字符的字母字符串可能的个数是 26^10。这个索引范围没有多大用处。我们需要一种机制来将它变为可接受的范围；而且理想情况下，这个机制可以为每个键生成唯一的值，根据这个值所在的位置来找到对应的字符串。这正是哈希需要做的事情之一。

2. 搜索（算法/思想）：当我们处理数据的时候，不外乎使用顺序结构、链表和树结构。但是使用这些结构时，元素的关键字与其存储位置之间通常没有对应的逻辑关系，这时候想要查找一个元素，我们根本不知道它在结构中的存储位置，甚至不知道它在不在结构中，这要求我们必须要不断地比较关键字进行查找，如顺序结构查找的时间是O(N)，树结构是O(logN)，通常这带来的结果是不断for循环遍历，极大地增加了代码时间复杂度。

那么可不可以有更好的搜索方法呢？哈希函数应运而生：由上面的定义可知，hash完美解决了这一问题，可以不经过任何比较，直接从哈希表/集中得到要搜索的元素或判断是否存在。

二、哈希会出现的问题

哈希有两种缺点：实际缺点和根本缺点。

1. 根本缺点：

哈希表的缺点它是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重，所以程序虽必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

而且，也没有一种简便的方法可以以任何一种顺序〔例如从小到大〕遍历表中数据项。如果需要这种能力，就只能选择其他数据结构。

然而如果不需要有序遍历数据，井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

2. 实际缺点：

哈希冲突：由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突，即不同的关键字得到的值相同。

这样的话我们前面所有的理想情况就成了笑谈，所以处理问题时要解决哈希冲突。

三、构造哈希算法

基本原则：便于计算（函数计算时间<=查找时间）；（散列地址）分布均匀

（1）直接定址法

直接定值法是取关键字的某个线性函数值为散列地址，即 f(key) = a*key + b。其优点是简单、均匀，不会产生冲突；但缺点是需要知道关键字的分布情况，希望数值是连续的。

（2）数字分析法

数字分析法通常适合处理关键字位数比较大的情况，例如我们现在要存储外卖信息登记表，如果用手机号作为关键字，那么抽取后面的四位数字作为散列地址是不错的选择。

（3）平方取中法

平方取中法是将关键字平方之后取中间若干位数字作为散列地址。这种方法适用于不知道关键字的分布，且数值的位数又不是很大的情况。

（4）折叠法

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

（5）除留余数法

此方法最常用：f(key) = key mod p(p <= n)  n：散列表的长度。

p的选择非常非常非常重要。

（6）随机数法

f(key) = random(key)

当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

四、处理哈希冲突

（1）开放定址法

当发生哈希冲突时，寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，处理冲突的过程结束，记录填入的位置：

fi(key) = (f(key)+di) MOD n       

di为增量序列，可以有下列三种取法：

1. di = 1,2,...,n-1：线性探测再散列；

2. di = 1^2,-1^2,...,k^2,-k^2(k<=n/2) 二次探测再散列

3. di = 伪随机数序列：伪随机探测再散列

（2）链地址法

（3）公共溢出区法

没有冲突的元素放在基本表，有冲突的元素，将多余的元素放在冲突表。

五、C++ STL 容器：哈希表和哈希集

（1）无序哈希表unordered_map

1. 以键值对（pair类型）的形式存储数据

2. 存储的各个键值对的键互不相同且不允许被修改

3. 不会自行对存储的键值对进行排序

代码如下：

#include <iostream>
#include <unordered_map> //哈希表头文件
using namespace std;
 
int main(){
    //建立哈希表
    unordered_map<Type,Type> hashsmap
    //第一个Type是键的变量类型，第二个是值得变量类型，hashmap是该哈希表的名称
    
    //插入键值对的两种方法
    hashmap.insert(make_pair(key，value));
    hashmap[key] = value;
    
    //删除键值对
    hashset.erase(key)
    
    //查询键值
    cout<<hashmap[key]<<endl;
     
    //搜索键值对
    if(hashmap.count(key)>0) cout<<"exist"<<endl;
 
    //遍历哈希表
    for (auto i = hashmap.begin(); i != hashmap.end(); i++) 
    {
        cout << "(" << i->first << "," << i->second << ") "<<endl;
    }
    
    /* 其他常用方法
     * empty() 若容器为空，返回true；
     * size() 返回当前容器存有键值对的个数
     * at(key) 返回容器中存储的键key对应的值，如果key不存在，则会抛出out_of_range异常
     * clear() 清空容器
     * find(key) 查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，                
     * 则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器)     
     */
 
}

（2）无序哈希集unordered_set

无序哈希集是一种功能简单的哈希结构：

1. 不再以键值对的形式存储数据，而是直接存储数据的值(存储的键值对 键和值相同 所以只存value即可)；

2. 容器内部存储的各个元素的值都互不相等，且不能被修改；

3. 不会自行对内部存储的数据进行排序。

代码如下：

#include <iostream>
#include <unordered_set> //哈希集头文件
using namespace std;
 
int main(){
    //建立哈希集
    unordered_set<Type> hashset
    //Type是哈希集中键的变量类型，hashset是该哈希集的名称
    
    //插入键
    hashset.insert(key)
    
    //删除键
    hashset.erase(key)
    
    //搜索键
    if(hashset.count(key) > 0) cout<<"exist"<<endl;
    
    //遍历哈希集
    for (auto i = hashset.begin(); i != hashset.end(); i++) 
    {
        cout << (*i) << endl;
    }
    
    /* 其他常用方法
     * empty() 若容器为空，返回true；
     * size() 返回当前容器存有元素的个数
     * clear() 清空容器
     * find(key)查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一            
     * 个指向容器中最后一个元素之后位置的迭代器（如果 end() 方法返回的迭代器）
     */
 
}