查找算法之哈希查找

  哈希也称散列，哈希表是一种与数组、链表等不同的数据结构，与他们需要不断的遍历比较来查找的办法，哈希表设计了一个映射关系f(key)= address，根据key来计算存储地址address，这样可以1次查找，f既是存储数据过程中用来指引数据存储到什么位置的函数，也是将来查找这个位置的算法，叫做哈希算法。

1、相关名词

1. 桶：哈希表中存储数据的位置，每一个位置对应唯一的一个地址，桶就好比一个记录。

2. 槽：每一个记录中可能包含很多字段，每一个字段就是槽。

3. 碰撞/冲突：若不同的数据经过哈希函数运算后对应到了相同的地址，就成为碰撞/冲突。

4. 溢出：如果数据经过哈希运算后，对应到的桶已满，则会发生溢出。

2、哈希查找算法的实现（链地址法/拉链法）

  如果遇到冲突，哈希表一般是怎么解决的呢？具体方法有很多，最常用的就是开发定址法和链地址法。链地址法的原理是把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T[0..m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。。

#include <iostream>
#include <vector>
#include <list>
#include <random>
#include <ctime>
using namespace std;

const int hashsize = 12;

//定一个节点的结构体
template <typename T, typename U>
struct HashNode 
{
    T _key;
    U _value;
};

//使用拉链法实现哈希表类
template <typename T, typename U>
class HashTable
{
public:
    HashTable() : vec(hashsize) {}//类中的容器需要通过构造函数来指定大小
    ~HashTable() {}
    bool insert_data(const T &key, const U &value);
    int hash(const T &key);
    bool hash_find(const T &key);
private:
    vector<list<HashNode<T, U>>> vec;//将节点存储到容器中
};

//哈希函数（除留取余）
template <typename T, typename U>
int HashTable<T, U>::hash(const T &key)
{
    return key % 13;
}

//哈希查找
template <typename T, typename U>
bool HashTable<T, U>::hash_find(const T &key)
{
    int index = hash(key);//计算哈希值
    for (auto it = vec[index].begin(); it != vec[index].end(); ++it)
    {
        if (key == it -> _key)//如果找到则打印其关联值
        {
            cout << it->_value << endl;//输出数据前应该确认是否包含相应类型
            return true;
        }
    }
    return false;
}

//插入数据
template <typename T, typename U>
bool HashTable<T, U>::insert_data(const T &key, const U &value)
{
    //初始化数据
    HashNode<T, U> node;
    node._key = key;
    node._value = value;
    for (int i = 0; i < hashsize; ++i)
    {
        if (i == hash(key))//如果溢出则把相应的键值添加进链表
        {
            vec[i].push_back(node);
            return true;
        }
    }
}

int main(int argc, char const *argv[])
{
    HashTable<int, int> ht;
    static default_random_engine e;
    static uniform_int_distribution<unsigned> u(0, 100);
    long long int a = 10000000;
    for (long long int i = 0; i < a; ++i)
        ht.insert_data(i, u(e));
    clock_t start_time = clock();
    ht.hash_find(114);
    clock_t end_time = clock();
    cout << "Running time is: " << static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC * 1000 <<
        "ms" << endl;//输出运行时间。
    system("pause");
    system("pause");
    return 0;
}

3、STL中的hash算法

  hash_*系列例如hash_map,hash_set 等已经被废弃了，C++11用unordered_map，unordered_set等来替代。

#include <iostream>
#include <string>
#include <random>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int main(int argc, char const *argv[])
{
    unordered_set<int> ht;
    static default_random_engine e;
    static uniform_int_distribution<unsigned> u(0, 100);
    long long int a = 1000;
    for (long long int i = 0; i < a; ++i)
        ht.insert(u(e));
    if (ht.find(1) != ht.end())
        cout << "get it!" << endl;

    unordered_map<int, string> mymap;
    mymap[1] = "A";
    mymap[2] = "B";
    mymap[3] = "C";
    if(mymap.find(1) != mymap.end())
    {
        cout << mymap[1] << endl;
    }
    system("pause");
    return 0;
}

4、算法总结

（1）哈希表的性能

  由于哈希表高效的特性，查找或者插入的情况在大多数情况下可以达到O(1)，时间主要花在计算hash上，当然也有最坏的情况就是hash值全都映射到同一个地址上，这样哈希表就会退化成链表，查找的时间复杂度变成O(n)，但是这种情况比较少，只要不要把hash计算的公式外漏出去并且有人故意攻击。

（2）拉链法的优缺点

优点：
  解决了哈希表堆聚现象，减小了平均查找长度。删除结点相对于线性探测更加易于实现，只需要找到相应结点再删除就可以了，而开放地址法中不能这样做，因为在哈希表中置空数组中的结点会导致后面的数据无法访问。

缺陷：
  当数据量比较小的时候，开放地址法不用开辟空间，如果相对于拉链法节省的结点空间用来扩大散列表则可以使装填因子（结点数与表长的比值），这样也就减少了开放地址法的冲突，提高平均查找速度。

（3） Hash的应用

1、Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。

2、查找：哈希表，又称为散列，是一种更加快捷的查找技术。我们之前的查找，都是这样一种思路：集合中拿出来一个元素，看看是否与我们要找的相等，如果不等，缩小范围，继续查找。而哈希表是完全另外一种思路：当我知道key值以后，我就可以直接计算出这个元素在集合中的位置，根本不需要一次又一次的查找！

举一个例子，假如我的数组A中，第i个元素里面装的key就是i，那么数字3肯定是在第3个位置，数字10肯定是在第10个位置。哈希表就是利用利用这种基本的思想，建立一个从key到位置的函数，然后进行直接计算查找。

3、Hash表在海量数据处理中有着广泛应用。

参考：https://www.cnblogs.com/s-b-b/p/6208565.html
https://blog.csdn.net/MBuger/article/details/62418754
https://blog.csdn.net/duan19920101/article/details/51579136