动态哈希映射用于八叉树

Question

有没有一种内存和速度高效的方法，可以动态地在哈希映射中存储唯一的键值对？这些键保证是唯一的，但数量经常发生变化。插入和删除需要快速操作。

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

- pks

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;
}

删除子节点只需要将形状字段中的一个位设置为0。希望这能帮到你，即使你之前问过一段时间了。

- gentlecolts