相亲网站建设关键,桂林最近发生的重大新闻,桃浦做网站,视觉vi设计系统1、介绍 哈希表#xff0c;也称为散列表#xff0c;是一种非常高效的数据结构。它通过将键#xff08;Key#xff09;映射到数组的特定位置来快速查找、插入和删除数据。这个映射过程由哈希函数#xff08;Hash Function#xff09;完成#xff0c;该函数将键转化为一个…1、介绍 哈希表也称为散列表是一种非常高效的数据结构。它通过将键Key映射到数组的特定位置来快速查找、插入和删除数据。这个映射过程由哈希函数Hash Function完成该函数将键转化为一个整数该整数用作数组的下标。 2、实现 哈希表将一个很大的集合映射成0~N
例如 将x属于-10^9 ~ 10^9映射到0~10^5里
两部操作首先 x mod 10^5;其次 解决冲突{两种办法{拉链发 和 开放寻址法}} 上述需要注意在做模运算的时候最好取比10^5第一个大的质数模这样会减少冲突冲突指的是会映射到一个地方去 2.1、拉链法
图解 注意算法题里一般只会考添加和查找几乎很少考删除操作就算考删除也不会真的删除只是跳过这个点 添加操作和查找操作类似于单链表 如图 2.2、开放寻址法 此方法只需要一个一维数组就可以实现 规则 空间开到2~3倍的N目的是可以减少冲突 这里同样要找到开的N的第一个质数 3、例题840. 模拟散列表 - AcWing题库 拉链法
#includeiostream
#includecstringusing namespace std;
//找到100000的第一个质数去mod会减少冲突
const int N 100003;
//h[]表示映射数组e[],ne[]是单链表e存数ne指向下一个节点,idx分配空间
int h[N],e[N],ne[N],idx;
//拉链法的存入操作
void insert(int x)
{//先让x%N是为了避免负数很大的情况不能先加N再mod。int k (x % N N) % N; e[idx] x;//存入xne[idx] h[k];//指针连到哈希表中h[k] idx;//让当前映射的值去记录开辟了多少空间存一下方便后面查找
}bool find(int x)
{int k (x % N N) % N;for(int ih[k];i!-1;ine[i]){if(e[i] x){return true;}}return false;
}int main()
{int n;scanf(%d, n);memset(h, -1, sizeof h);//方便单链表查找操作while (n -- ){char op[2];int x;scanf(%s%d, op,x);if(op[0] I){insert(x);}else{if(find(x)) printf(Yes\n);else printf(No\n);}}return 0;
} 开放寻址法
#includeiostream
#includecstringusing namespace std;const int N 200003,null 0x3f3f3f3f;
int h[N];
//开放寻址法
int find(int x)
{int k (x%NN)%N;//寻找映射值//去寻找k的位置如果k下有这个数返回的就是这个数的位置//如果k下没这个数返回的是这个数应该存的位置while(h[k] ! null h[k] ! x){k;if(kN) k 0;}return k;
}int main()
{int n;scanf(%d, n);//解释一下这里为啥是0x3f是因为memset是按字节去存储的一个int是4个字节//每个字节是0x3f所以4个字节就是3f3f3f3fmemset(h,0x3f,sizeof h);while (n -- ){char op[2];int x;scanf(%s %d, op, x);int k find(x);//与拉链法区别是寻址法都需要寻找k直接合并成一个就可以if(op[0] I){h[k] x;}else{if(h[k] x) printf(Yes\n);else printf(No\n);}}return 0;
}
