oi wiki 哈希表

参考链接：https://oi-wiki.org/ds/hash/

模版代码：

struct hash_map {  // 哈希表模板

  struct data {
    long long u;
    int v, nex;
  };  // 前向星结构

  data e[SZ << 1];  // SZ 是 const int 表示大小
  int h[SZ], cnt;

  int hash(long long u) { return (u % SZ + SZ) % SZ; }

  // 这里使用 (u % SZ + SZ) % SZ 而非 u % SZ 的原因是
  // C++ 中的 % 运算无法将负数转为正数

  int& operator[](long long u) {
    int hu = hash(u);  // 获取头指针
    for (int i = h[hu]; i; i = e[i].nex)
      if (e[i].u == u) return e[i].v;
    return e[++cnt] = (data){u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;
  }

  hash_map() {
    cnt = 0;
    memset(h, 0, sizeof(h));
  }
};

代码说明：

当时学的最简单的拉链式哈希表应该是基于链表的。

假设哈希表的大小为n。

那么首先初始化一个长度为n的数据数组。

一个数据应该包含数据，下一个相同hash值的地址。类似于下面这种

class Node {
public:
    KEYTYPE key;
    DATATYPE data;
    Node* next;
};

Node nodes[hashSize];

这种格式方便理解。

上边oi wiki给出的模版则是固定了存储位置，为一个固定大小的数据数组,大小为hash值个数的两倍。

然后再设一个hash地址到实际存储的index之间的映射。即代码中的数组h。

例如一个数值v的hash地址是hashv。

那么就用h数组找到该值在data数组中，即e数组中实际的存储位置。

存储的时候如果hash地址的位置已经有值了即，h[hashv]!=-1，那么就要用拉链法解决一下冲突了，方法是将h[hashv]的地址指向新的数据位置，新数据存的下一个位置设为之前的h[hashv]。相当于头插法。

由于避免了每次冲突时malloc内存，速度可能会好一些。但是降低了可读性。

如果我自己写的话感觉还是老老实实用指针的方式比较舒服。

class Node {
public:
    K key;
    D data;
    Node* next;
};

const int hashSize = 999997;

Node nodes[hashSize];

int hash(K key) {};

D* get(K key) {
    int hashAddr = hash(key);
    Node* head = nodes[hashAddr];
    while(head!=nullptr&&head->key!=key) {
        head = head->next;
    }
    if(head==nullptr)return nullptr;
    return &head->data;
}

void add(K key, D data) {
    int hashAddr = hash(key);
    Node* head = nodes[hashAddr];
    while(head->key!=key&&head->next!=nullptr) {
        head=head->next;
    }
    if(head->key==key)return;
    head->next=(Node*)malloc(sizeof(Node));
    head->next->key=key;
    head->next->data=data;
    head->next->next=nullptr;
}