hashmap - 八叉树的动态哈希图

Question

是否有内存和速度有效的方法来在哈希图中动态存储唯一键：值对？密钥保证是唯一的，但它们的数量经常变化。插入和删除必须快速。

我所做的是包含有符号距离场的八叉树（不是线性/完整）。八叉树经常更新。我想做的是尝试使其无指针以节省一些空间。

Answer 1

我不确定是否使用哈希图，因为动态结构往往会丢失哈希图受益的 O(1) 查找，或者分配额外的内存并在内存用完时需要重新分配。但是，您可以创建一个八叉树，其中每个节点只有一个指针。

例如，在 C++ 中，可能会执行以下操作：

struct node{
    node* next;//pointer to children
    unsigned byte shape;//8bit flag indicating which children actually exist

    node():next(0),shape(0){}
};
void initChildren(node& parent,unsigned byte state=0){
    if(!parent.next){//only allocate the array if it has not yet been allocated
        parent.next=new node[8];//the children are allocated in consecutive memory
    }
    shape=state;
}

删除子节点只需要在 shape 字段中设置一点为 0。我希望这对您有所帮助，即使您之前确实问过。