带你手撕哈希（hash）表【数组】

2024-07-10 13:29| 来源: 网络整理| 查看: 265

HASH 思维导图哈希哈希函数哈希冲突散列表拉链法开放寻址法字符串哈希

思维导图 hash 散列表字符串哈希拉链法开放寻址法哈希

哈希的本质是映射，把一个较大范围的数据映射到一个较小的数据里面，从而更方便的进行某些操作。在这里插入图片描述

哈希函数

通过某种函数关系，将一堆较大范围的数据映射成较小范围的数据，这样的函数关系就叫做哈希函数，比如我们设较大范围的数据为x，较小范围的数据为y，常用的函数为 y = x % mod。

哈希冲突

我们把一个很大范围的数据映射到一个较小范围的数据中，则必然存在至少两个x被映射被映射到同一个y中，这便是哈希冲突,如何尽可能的规避哈希冲突是哈希问题的一个很重要的问题。

散列表

我们先引入一个例题。在这里插入图片描述

拉链法

在这里插入图片描述所谓拉链法便是将x通过y = x % mod找到对应的y，从而在y的下面拉一条链子，注意每次拉链是在y头拉。

时间复杂度：因为通常我们这个链子也不会很长，基本是1到3个，这相对于1e5来说近似o（1）。

#include using namespace std; const int N = 100003;//取质数从数学的角度来说可以最大程度的避免哈希冲突 int h[N], ne[N], e[N], idx; void insert(int x){ int k = (x % N + N) % N;//哈希函数 e[idx] = x, ne[idx] = h[k], h[k] = idx ++;//链表 } bool find(int x){ int k = (x % N + N) % N; for(int i = h[k];i != -1;i = ne[i]){//遍历 int j = e[i]; if(j == x) return true; } return false; } int main(){ ios::sync_with_stdio(false); cin.tie(0); memset(h, -1, sizeof h); int n; cin >> n; while(n --){ char op; cin >> op; if(op == 'I'){ int x; cin >> x; insert(x); }else{ int x; cin >> x; if(find(x)) cout int k = (x % N + N) % N; for(auto i : e[k]){ if(i == x) return true; } return false; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; while(n --){ char op; cin >> op; if(op == 'I'){ int x; cin >> x; insert(x); }else{ int x; cin >> x; if(find(x)) cout //有人就找下一个 k ++; if(k == N) k = 0; } return k; } int main(){ ios::sync_with_stdio(false); cin.tie(0); memset(h, 0x3f, sizeof h); int n; cin >> n; while(n --){ char op; int x; cin >> op >> x; if(op == 'I'){ int k = find(x); h[k] = x; }else{ int k = find(x); if(h[k] != null) cout return h[r] - h[l - 1] * p[r - l + 1];//区间公式 } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s+1; p[0] = 1; for(int i = 1;i int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2; if(get(l1, r1) == get(l2, r2)){ puts("Yes"); }else{ puts("No"); } } return 0; }

首先我们先介绍这个前缀和公式：在这里插入图片描述用这种方式我们就可以完美表示前缀字符串的哈希值。接下来就是求区间（子串）了这样我们就可以求区间了。这道题的整个时间复杂度为o(n) + o(m)(每次查询时的时间复杂度是近似O（1）的时间复杂度。

【本文地址】

公司简介

联系我们