C++优先级队列setKey函数调试：哈希表指针异常引发段错误

1. 最核心的野指针问题（导致position乱码、段错误） #

你在heap::insert函数中存在致命的指针错误：

node element = node(id, key, pv, index);
data[index] = element;
// ... 省略上滤代码
node* ptr = &element; // 此处取的是栈上局部变量element的地址
map->insert(id, ptr);

局部变量element存储在栈内存中，insert函数执行结束后栈帧回收，这块内存会被其他数据覆盖，存入哈希表的指针直接变为悬垂野指针，后续setKey通过野指针访问position自然会得到乱码值，触发段错误是预期结果。
修复方式：存储堆内data向量中实际存储节点的地址：

// 上滤执行完成后，取data中实际节点的地址存入哈希表
map->insert(id, &data[data[index].position]);

2. 堆上滤/下滤逻辑错误 #

当前的percolateUp和percolateDown只更新了最终定位节点的position，中间移动的父节点/子节点的position完全没有修改，后续这些节点的位置信息全部错误。
以percolateUp为例，移动父节点到下一层时，需要同步更新父节点的position：

while(index > 1 and element.key < data[index / 2].key)
{
  data[index] = data[index / 2];
  data[index].position = index; // 新增这行，更新被移动节点的位置
  index = index / 2;
}

percolateDown中移动子节点时也要添加相同的位置更新逻辑。另外percolateDown没有判断子节点是否存在，操作叶子节点时会越界访问data，需要在判断子节点key之前先判断index*2 <= size，右子节点同理先判断index*2+1 <= size。 #

3. 哈希表实现的多个问题 #

3.1 哈希值可能为负 #

用int存储哈希值，字符串哈希计算过程中很容易溢出变为负数，模length之后得到负下标，直接越界访问data向量。
修复方式：将哈希值转为无符号数再取模，或者对结果加length后再取一次模保证非负。

3.2 负载因子计算错误 #

计算负载因子的代码filled/capacity > 0.5中，filled和capacity都是整数，C++整数除法会舍去小数部分，只要filled < capacity结果永远是0，永远不会触发rehash判断。
修复方式：转成浮点数计算：

if ((double)filled / length > 0.5)

另外当前完全没实现rehash逻辑，只返回了错误码2，需要补全rehash的实现。

3.3 getPointer的输出参数无效 #

当前对输出参数b的赋值完全无效：

bool con = contains(key);
b = &con; // 只是修改了指针变量b本身的指向，没有修改外部传入的变量值

修复方式：判断b不为空时解引用赋值：

if (b != nullptr) {
  *b = con;
}

4. 其他逻辑错误 #

• heap::insert中修改capacity的逻辑错误，capacity是堆的总容量，不应该随着元素插入递减，只需要递增size，满的判断条件改为size == capacity即可。
• percolateUp执行完成后，节点的位置可能已经改变，插入哈希表时必须用修改后的data[index].position作为下标取地址，不能用原来的index。

内容的提问来源于stack exchange，提问作者NaiveCoder