Хеш-стол с двумя ключами

Question

У меня большой объем данных, к которым я хочу получить доступ двумя разными способами. Я хотел бы, чтобы поиск по постоянному времени осуществлялся на основе либо ключа, либо вставки с постоянным временем одним ключом, а удаления с постоянным временем - другим. Существует ли такая структура данных, и можно ли ее построить, используя структуры данных в tr1 и, возможно, повысить?

Answer 1

Используйте две параллельные хеш-таблицы. Убедитесь, что ключи хранятся внутри значения элемента, потому что вам понадобятся все ключи во время удаления.

Answer 2

Трудно понять, зачем вам это нужно, но, как кто-то сказал, попробуйте использовать 2 разные хеш-таблицы.Просто псевдокод здесь:

Hashtable inHash;
Hashtable outHash;

//Hello myObj example!!
myObj.inKey="one";
myObj.outKey=1;
myObj.data="blahblah...";

//adding stuff
inHash.store(myObj.inKey,myObj.outKey);
outHash.store(myObj.outKey,myObj);

//deleting stuff
inHash.del(myObj.inKey,myObj.outKey);
outHash.del(myObj.outKey,myObj);

//findin stuff

//straight
myObj=outHash.get(1);

//the other way; still constant time

key=inHash.get("one");
myObj=outHash.get(key);

Не уверен, это то, что вы ищете.

Answer 3

Вы смотрели на Фильтры Блума ? Они не O (1), но я думаю, что они работают лучше, чем хеш-таблицы с точки зрения времени и пространства, необходимых для поиска.

Answer 4

Это одно из ограничений проектирования стандартных контейнеров: контейнер в некотором смысле «владеет» содержащимися данными и ожидает быть единственным владельцем ... контейнеры - это не просто «индексы».В вашем случае простое, но не на 100% эффективное решение - иметь две std :: maps с «Node *» в качестве значения и хранить оба ключа в структуре Node (так что каждый ключ хранится дважды).При таком подходе вы можете обновить свою структуру данных с разумными накладными расходами (вы будете выполнять дополнительный поиск по карте, но это должно быть достаточно быстро).

Возможно, «правильное» решение, однако IMO, будет выглядеть как

struct Node
{
    Key key1;
    Key key2;
    Payload data;
    Node *Collision1Prev, *Collision1Next;
    Node *Collision2Prev, *Collision2Next;
};

в основном каждый узел находится в двух разных хеш-таблицах одновременно.

Стандартные контейнеры не могут быть объединены таким образом.Другими примерами, которые я кодировал вручную в прошлом, являются, например, хеш-таблица, где все узлы также находятся в двусвязном списке, или дерево, где все узлы также находятся в массиве.

Для очень сложных структур данных(например, сеть структур, каждая из которых является одновременно «владельцем» нескольких цепочек и частью нескольких других цепочек). Я даже иногда прибегал к генерации кода (т. е. к сценариям, которые генерируют правильный код обработки указателей с учетом описания структуры данных)..