。

它通过将键#xff08;Key#xff09;映射到数组的特定位置来快速查找、插入和删除数据。

这个映射过程由哈希函数#xff08;Hash

Function#xff09;完成#xff0c;该函数将键转化为一个…1、介绍

哈希表也称为散列表是一种非常高效的数据结构。

它通过将键Key映射到数组的特定位置来快速查找、插入和删除数据。

这个映射过程由哈希函数Hash

Function完成该函数将键转化为一个整数该整数用作数组的下标。

2、实现

上述需要注意在做模运算的时候最好取比10^5第一个大的质数模这样会减少冲突冲突指的是会映射到一个地方去

2.1、拉链法

注意算法题里一般只会考添加和查找几乎很少考删除操作就算考删除也不会真的删除只是跳过这个点

添加操作和查找操作类似于单链表

//h[]表示映射数组e[],ne[]是单链表e存数ne指向下一个节点,idx分配空间

int

{//先让x%N是为了避免负数很大的情况不能先加N再mod。

int

e[idx]

idx;//让当前映射的值去记录开辟了多少空间存一下方便后面查找

}bool

(x%NN)%N;//寻找映射值//去寻找k的位置如果k下有这个数返回的就是这个数的位置//如果k下没这个数返回的是这个数应该存的位置while(h[k]

null

n);//解释一下这里为啥是0x3f是因为memset是按字节去存储的一个int是4个字节//每个字节是0x3f所以4个字节就是3f3f3f3fmemset(h,0x3f,sizeof

h);while

find(x);//与拉链法区别是寻址法都需要寻找k直接合并成一个就可以if(op[0]

I){h[k]