hashmap - octree の動的ハッシュマップ

Question

一意のキーと値のペアをハッシュマップに動的に保存するためのメモリと速度の効率的な方法はありますか? キーは一意であることが保証されていますが、キーの量は頻繁に変化しています。挿入と削除は高速でなければなりません。

私が行ったのは、符号付き距離フィールドを含む octree (線形/完全ではない) です。Octree は頻繁に更新されます。私がやりたいのは、スペースを節約するためにポインターを持たないようにすることです。

Answer 1

動的構造は、ハッシュマップが恩恵を受けるO(1)ルックアップを失うか、余分なメモリを割り当てて、そのメモリが使い果たされたときに再割り当てを必要とする傾向があるため、ハッシュマップの使用についてはわかりません。ただし、各ノードが 1 つのポインターしか持たない octree を作成することはできます。

たとえば、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 に設定するだけで済みます。少し前に質問した場合でも、これがお役に立てば幸いです。