C++线性探测法
liufeng2023 人气:01、哈希表-线性探测法理论
线性探测法的理论我们在上一篇博客已经阐述了。
现在我们来看看线性探测法的增删查的代码思想:
1.1、哈希表的增加元素
注意:
往后遍历寻找空闲位置的时候,要注意是环形遍历哦!不然访问数组就越界了。
在添加元素,发生位置被占用,即发生哈希冲突后,在向后遍历寻找空闲位置的时候,我们要知道,这个空闲的位置是有两种情况的:
1、这个位置一直是空的,没放过元素。
2、这个位置是空的,以前放过元素,后来被删除了。
1.2、哈希表的查询操作
- 当用哈希函数计算得出的下标值是3,然后去访问数组,查询时,发现该值不等于要查询的元素的值val,说明当时放val的时候发生了哈希冲突,这时候就要向后遍历了;
- 访问4下标的时候发现这个位置是空的(空的有两种情况),如果这个位置一直是空的,则就不用继续向后找了,val不存在!因为是线性探测法,所以当时val如果要放的时候肯定是要放在这里的。
- 但是如果这个位置是空的,但是之前放过元素,后来被删除了,这个位置之前存放了元素,然后val插入的时候,就插到后面的空闲的位置了,所以此时我们还要继续往后遍历寻找val值。
所以我们需要定义一个Bucket节点来表示每一个元素的所有的内容。
//桶的状态 enum State { STATE_UNUSE, //从未使用过的桶 STATE_USING, //正在使用的桶 放着是一个有效的元素,没有被删过 STATE_DEL, //元素被删除了的桶,认为桶里的元素无效了 }; //我们删除桶里的元素,并不是真正把值删除掉,而是把桶的状态置为STATE_DEL就认为桶里的元素无效了 //桶的类型 struct Bucket { Bucket(int key = 0, State state = STATE_UNUSE) : key_(key) , state_(state) {} int key_; //存储的数据 State state_; //桶的当前状态 };
1.3、哈希表的删除操作
2、哈希表-线性探测法代码实现
2.1、素数表中的素数
求素数的代码:(用于素数表中的素数取值)
int main() { int data = 3; for (int i = data; i < 10000; i++) { int j = 2; for (; j < i; j++) { if (i % j == 0) break; } if (j == i) cout << i << " "; } cout << endl; return 0; }
加载全部内容