hashmap - 八叉树的动态 HashMap

Question

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

我所做的是包含有符号距离场的八叉树(非线性/完整)。八叉树经常更新。我想做的是尝试让它成为无指针以节省一些空间。

Answer 1

我不确定是否使用 hashmap，因为动态结构往往会丢失 hashmap 从中受益的 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。我希望这对你有帮助，即使你刚才问过。