模拟散列表(哈希表)
哈希表哈希表是把一个比较大的值域映射到一个比较小的空间
哈希表的存储结构：
1.开放寻址法：当出现冲突时，按照顺序将数据存放到数组的下一个位置。
2.拉链法：当出现冲突时，在这个位置拉一个链，链上是所有满足这一冲突的元素
哈希表的时间复杂度可以看作O( 1 ),一般只会有添加和查找操作。
字符串的哈希方式：
例题：
输入样例：
5
I 1
I 2
I 3
Q 2
Q 5期望输出：
Yes
No代码实现：
1.拉链法，需要多开两个数组用来存放数据值和下一个指向地址
#includeusing namespace std;const int N = 1e5+3; //取大于1e5的一个质数int h;//哈希表int e,ne,idx;//存放拉链void insert(int a){ int k = (a % N + N)%N;//因为负数取模还是负数，为了让数变成正数，先取模再加N再取模 e = k; //新建一个结点并赋值 ne = h;//让新节点的next指针指向原先h指向的结点 h=idx++;//让h指向新结点}bool query(int a){ int k = (a % N + N)%N; for(int i=h;i!=-1;i=ne) { if(e==a) return true; } return false;}int main(){ memset(h,-1,sizeof(h)); int n; cin>>n; for(int i=1;i
页:
[1]