Hash表

当存储了大量的数据时，如果进行查找，可能耗时会很久。这时，有个叫hash表的方法。

哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。 然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。 另外，编码比较容易也是它的特点之一。 其基本原理是：使用一个下标范围比较大的数组来存储元素

各种各样的散列hash方法见 https://blog.csdn.net/weixin_43142797/article/details/99947549

这里说一下链表实现。

#pragma once
#include <iostream>
using namespace std;

class HashTable
{
public:
    HashTable() {};
    ~HashTable() {
        delete[]mRoot;
    };

    void CreateHashTable(int num);

    struct Node {
        Node* mNextNode = nullptr;
        int mValue = -1;
        ~Node()
        {
            cout << "head : " << mValue << endl;
            if (mNextNode == nullptr) {
                return;
            }
            delete mNextNode;
        }
    };

    // 输出hash表的数据
    void out()
    {
        for (int i = 0; i < mMaxSize; ++i) {
            Node* tmp = mRoot[i].mNextNode;
            if (tmp == nullptr) {
                continue;
            }
            cout << "head : " << mRoot[i].mValue << endl;
            while (tmp) {
                cout << tmp->mValue << " ";
                tmp = tmp->mNextNode;
            }
            cout << endl;
        }
    }

    void Insert(int num);
    bool Contains(int num);

private:
    bool IsPrimer(int num);
    int GetNextPrimer(int num);
    int HashIndex(int num);

    Node *mRoot = nullptr;
    int mMaxSize = 0;
};

#include "HashTable.h"
#include <cmath>

/*
* brief  创建hash表
*/
void HashTable::CreateHashTable(int num)
{
    int size = GetNextPrimer(num);
    mMaxSize = size;
    if (mRoot == nullptr) {
        mRoot = new Node[size]();
        for (int i = 0; i < size; ++i) {
            mRoot[i].mValue = i;
        }
    }
}

/*
* brief 添加数据
*/
void HashTable::Insert(int num)
{
    int index = HashIndex(num);
    Node *tmp = mRoot[index].mNextNode;
    Node* data = new Node;
    data->mValue = num;
    mRoot[index].mNextNode = data;
    data->mNextNode = tmp;
}

/*
* brief 判断是否存在
*/
bool HashTable::Contains(int num)
{
    int index = HashIndex(num);
    // 这里一定要记得引用,如果不加引用，这里会变成函数内变量，会在函数结束时，析构掉。后边再用到的时候，就崩溃了.
    Node &node = mRoot[index];
    Node* tmp = node.mNextNode;
    while (tmp) {
        if (num == tmp->mValue) {
            return true;
        }
        tmp = tmp->mNextNode;
    }
    return false;
}

/*
* brief 判断素数
*/
bool HashTable::IsPrimer(int num)
{
    // 6x - 1 or 6x + 1
    if (num == 4 || num == 1) {
        return false;
    }
    for (int i = 5; i < std::sqrt(num); i = i + 6) {
        if (num % i == 0 || (num + 2) % i == 0) {
            return false;
        }
    }
    return true;
}

/*
* brief 取得大于num的最小素数
*/
int HashTable::GetNextPrimer(int num)
{
    int tmp = num % 2 == 0 ? num + 1 : num;
    while (!IsPrimer(tmp)) {
        tmp += 2;
    }
    return tmp;
}

/*
* brief 取得num在链表中的下标
*/
int HashTable::HashIndex(int num)
{
    return num % mMaxSize;
}

#include "HashTable.h"

int main(int argc, char **argv)
{
    HashTable hash;
    int nums[10] = {11, 54, 65, 85, 75, 63, 23, 28, 29, 99};
    hash.CreateHashTable(10);
    for (int i = 0; i < 10; ++i) {
        hash.Insert(nums[i]);
    }
    hash.out();
    cout << hash.Contains(88) << endl;
    cout << hash.Contains(99) << endl;
    return 0;
}