特化hash

特化hash

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
using namespace std;

// 堆上放的是 Node 类型的实例
class Node
{
public:
    string str;
    int times;
    Node(string s, int t) : str(s), times(t) {}
    Node() : str(""), times(0) {}
    bool operator==(const Node &n) const
    {
        return this->str == n.str && this->times == n.times;
    }
};

template <typename T>
void hashCombine(size_t &seed, const T &arg) // 真正的hash在这里完成
{
    // 这里虽然也用到了标准库提供的hash函数，但是后面可以添加自己的一些数据（甚至hash<T>()(arg)操作也可以有我们自己来做）
    // 不同用户在这里可以有不同的数，只要能够将原始数据尽可能打乱即可
    // 0x9e3779b9涉及到数学中的黄金比例，实际上并不需要一定是这个数
    seed ^= hash<T>()(arg) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template <typename T>
void hashValue(size_t &seed, const T &arg) // ③递归出口
{
    hashCombine(seed, arg);
}
template <typename T1, typename... T2>
void hashValue(size_t &seed, const T1 &arg, const T2 &...args) // ②在这里通过递归逐步拿到所有参数,当args...的大小为1时跳出该递归，接着进入③
{
    hashCombine(seed, arg);
    hashValue(seed, args...); // 递归
}
template <typename... T>           // T为模板参数包，可以代表任意多个类型；args为函数参数包，可以代表任意多个函数参数
size_t hashValue(const T &...args) // ①在这里完成参数的第一次拆分，接着进入②
{
    size_t seed = 0;          // 种子，以引用方式传递
    hashValue(seed, args...); // args...中为T类型对象中的所有用于hash的数据成员
    return seed;
}
class Hasher
{ // hash函数
public:
    size_t operator()(const Node &n) const
    {
        return hashValue(n.str, n.times);
    }
};

class TopKRecord
{
public:
    TopKRecord(int size)
    {
        heap.resize(size);
        index = 0;
    } 

private:
    vector<Node> heap;
    // index 表示目前为止堆有多少个元素
    int index;
    // 词频表
    unordered_map<string, Node> strNodeMap;
    // node 在堆上的下标；如果不在堆上，下标为 index
    unordered_map<Node, int, Hasher> nodeIndexMap;
};

int main()
{
    return 0;
}