哈希表笔记

哈希表什么是哈希表?哈希表就是一个带编号的储物柜(哈希表中的下标)你要存放的物品(数据),通过一个规则(哈希函数),计算出ta该放的储物柜编号找东西时,先用同一个规则算出对应的编号,再去对应柜子拿哈希表的模拟实现有两种方式:一个是线性探测法,一个是链地址法.线性探测处理哈希冲突的方式—冲突往后找空位线性探测处理哈希冲突的方式—冲突往后找空位线性探测法模拟实现哈希表// 线性探测模拟实现哈希表#includeiostream#includecstring// memset函数包含头文件constintN23;// N的选取---样本空间*2,找附近的质数inth[N],id;// 哈希表可以理解为一个数组,里面的每个元素一开始都是无穷大的数intIFN0x3f3f3f3f;voidinit(){memset(h,0x3f,sizeofh);// 将哈希表里面的每一个元素都初始化为无穷大的数}intf(intx)// 将关键字映射成对应地址{id(x%NN)%N;while(h[id]!IFNh[id]!x)// 第一个式子确定id处是否已经存了其他元素,第二个式子确定id处是否存了目标元素// 处理哈希冲突{id;if(idN)id0;// 当id走到队尾时,如果还不符合,就让ta返回对头(实现id的闭环)}returnid;}// 查找元素boolfind(intx){intidxf(x);// 调用哈希函数返回对应坐标returnh[idx]x;}// 添加元素voidadd(intx){intidxf(x);h[idx]x;}intmain(){init();// 初始化哈希表f();// 哈希函数,将关键字映射成对应地址find();add();return0;}链地址法实现哈希表// 链地址法实现哈希表#includeiostreamusingnamespacestd;constintN23;inth[N],e[N],ne[N],id;intf(intx)// 哈希函数,返回映射地址{return(x%NN)%N;}voidinsert(intx)// 插入函数{intidxf(x);// 获得目标元素的映射地址,哈希表h[N]的下标// 头插操作id;e[id]x;ne[id]h[idx];h[idx]id;}boolfind(intx)// 查找函数{intidxf(x);// 获得目标元素的映射地址,哈希表h[N]的下标for(intih[idx];i;ine[i]){if(e[i]x)returntrue;}returnfalse;}intmain(){return0;}