C++如何使用指针实现哈希表-C++-PHP中文网

手写指针哈希表可控制内存布局、避免分配器开销，并支持嵌入式等场景定制哈希策略；链地址法中节点需含node next，桶数组为node*，须用{}初始化防野指针，扩容需rehash而非memcpy，删除需维护前驱以防断链，析构须逐桶释放节点再delete[]桶数组。

c++如何使用指针实现哈希表

为什么不用 `std::unordered_map` 而要手写指针哈希表

因为需要控制内存布局、避免标准库分配器开销，或在嵌入式/游戏引擎等场景下做定制化哈希策略（比如用线性探测而非链地址法）。但注意：std::unordered_map 默认就是用指针管理桶和节点的，你手写只是把封装层掀开——不是“更底层”，而是“更裸露”。真正收益只在明确知道 new/delete 频次、冲突模式、key/value 生命周期时才体现。

链地址法中指针怎么连节点

每个桶是 Node*，节点结构必须含指向下一个节点的指针：

struct Node {
    int key;
    int value;
    Node* next;  // 必须是指针，不能是值类型
};

插入时常见错误是忘记更新 next 或误用 == 比较指针值：

错误写法：if (bucket == nullptr) bucket = new Node{key, value, bucket}; —— 这会让新节点的 next 指向自己
正确写法：Node* newNode = new Node{key, value, bucket}; bucket = newNode;
遍历时别写 while (p != nullptr) 写成 while (p) 更简洁，但语义一样

哈希函数和桶数组怎么用指针管理

桶数组本身是 Node** buckets，不是 Node*。分配时容易漏掉二级指针初始化：

buckets = new Node*[capacity]{};  // {} 确保每个元素初始化为 nullptr

不加 {} 会导致野指针，后续 if (buckets[i]) 判断失效。扩容时需重新哈希所有节点，不能直接 memcpy——因为 Node* 指向的是堆上分散地址，复制指针值没意义，必须逐个 rehash 后 insert。

C++

"空空如也"

下载

哈希函数返回 size_t，取模时务必转成 unsigned 再对容量取余，否则负数 key 可能导致 % 结果为负（取决于编译器），进而越界访问 buckets[index]。

删除节点时指针怎么安全释放

链地址法删节点不是简单 delete p 就完事。必须维护前驱指针，否则会断链：

头节点删除：直接 Node* old = buckets[hash]; buckets[hash] = old->next; delete old;
中间节点删除：需遍历并记录 prev，然后 prev->next = curr->next; delete curr;
千万别写 delete buckets[hash]; buckets[hash] = buckets[hash]->next; —— 这里 buckets[hash] 已被释放，再解引用是未定义行为

如果允许 key 重复插入，还得考虑是否只删第一个匹配项，还是全部——这直接影响遍历逻辑里 break 的位置。

最易被忽略的是：所有 new 出来的 Node* 和 Node**，必须有且仅有一个 delete 对应点；析构函数里先遍历每个桶，逐个 delete 链表节点，再 delete[] buckets。少一步，就是内存泄漏或 double-free。