Есть ли эффективный способ памяти и скорости для динамического хранения уникальных пар ключ: значение в хэш-карте? Ключи гарантированно уникальны, но их количество часто меняется. Вставка и удаление должны быть быстрыми.
То, что я сделал, это октодерево (не линейное/полное), содержащее поле расстояния со знаком. Octree часто обновляется. Что я хотел бы сделать, так это попытаться сделать его бессмысленным, чтобы сэкономить место.
Я не уверен в использовании хэш-карты, поскольку динамические структуры, как правило, либо теряют поиск O (1), от которого выигрывает хэш-карта, либо выделяют дополнительную память и требуют перераспределения, когда эта память израсходована. Однако вы можете создать октодерево, в котором каждый узел имеет только один указатель.
например, в С++ можно сделать что-то вроде:
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. Я надеюсь, что это поможет вам, даже если вы спрашивали некоторое время назад.
