C语言 有没有一种方法可以优化在具有多个键的哈希表中搜索特定键

abithluo  于 2023-06-05  发布在  其他
关注(0)|答案(2)|浏览(429)

多关键字搜索哈希表
我有一个哈希表,有3个键:源地址、目的地地址和应用ID。每当接收到的分组将在哈希表中生成该元组和serach时,它给出适当的条目,它完美地工作。如果我只想用1个键或2个键搜索,比如想得到所有带有应用程序ID号的条目,我必须遍历所有条目。或者我必须根据每个键创建另一个表。
我的问题是,有没有什么方法可以增强哈希表以获得具有多个键的条目,比如为每个桶或任何其他选项维护多个哈希。有没有图书馆可以让搜索更容易。
代码是在c语言和我们正在使用fdio vpp为我们的发展。任何帮助都是非常感谢的。

gblwokeq

gblwokeq1#

如果你不能使用内存数据库或类似sqlite的东西。
4个哈希表。
第一个表将一个条目id(整数)Map到一个条目(不管它是什么)

unordered_map<int, shared_ptr<Entry>> entries;

然后是三个哈希表,用于将不同的键Map到不同的集合:

unordered_map<Address, unordered_set<int>> sourceAddressMap;
 unordered_map<Address, unordered_set<int>> destAddressMap;
 unordered_map<AppId,   unordered_set<int>> appIdMap;

可能还有第五个表,用于通过所有三个键搜索精确的数据包:

unordered_map<Key, unordered_set<int>> entryTable

这里的“Key”是你今天使用的东西,它可以从所有三个字段中创建一个密钥。
插入很简单,仍然是O(1)。每当你得到一个新的数据包(条目),给它分配一个唯一的id整数,然后插入到你所有的表中:

shared_ptr<Entry> entry = makeNewEntryFromPacket(packet);
 int id = nextId++;
 sourceAddressMap[entry.sourceAddress].insert(id);
 destAddressMap[entry.destAddres].insert(id);
 appIdMap[entry.appId].insert(id);

 entryTable[makeKey(entry.sourceAddress, entry.destAddress, entry.appId)].insert(id);

从单个键查找所有条目(例如时间复杂度O(1)

const auto& lookup = sourceAddressMap[appId];
 for (int id: lookup) {
     auto entry = entries[id];
     // do something interesting with entry...
 }

多关键字查找(来自特定源地址和应用ID的所有条目):

const auto& lookup1 = sourceAddressMap[address];
const auto& lookup2 = appIdMap[appId];
std::vector<int> v;
std::set_interection(lookup1.begin, lookup1.end(), lookup2.begin, lookup2.end(), std::back_inserter(v));    

 for (int id : v) {
     auto entry = entries[id];
     // do something interesting with entry...
 }

还有std::set_union,如果你想在任何一个键上进行“或”操作。
这种设计的挑战在于,保持多个表同步本身就很脆弱。这就是为什么我建议在需要扩展时使用数据库作为更强大的解决方案。

xmakbtuz

xmakbtuz2#

在您的情况下,显然您可以为关键组件(源地址,目的地地址和/或应用程序ID)的各种组合使用不同的表,但如果您想探索将这些多个功能强制到单个表中,那么您可以...你必须仔细考虑哈希表的基本属性:密钥的散列、密钥比较、冲突管理以及在密钥数据旁边存储一些值的选项。处理键中的变化的最简单方法是查看每个键组件是否有一个sentinel值,该值可以充当通配符的角色。例如,如果源地址、目标地址和应用程序ID通常是正整数,则可以将0存储为通配符标记。或者,您可以使用-1或数据类型的最大值。在最坏的情况下,您可以向键添加3位来跟踪哪些组件是通配符。然后,如果你的哈希函数和密钥比较函数被调整(如果必要的话),以科普哨兵值或有效值旁边的额外位。这是散列的“前端”方面-它会让你得到理想的桶。但是,在该桶处/从该桶(即,使用开放或封闭寻址),您可能需要具有非哨兵键组件的条目,或者携带哨兵的“通配符”条目之一-棘手的事情是它们需要链接到通配符匹配条目的容器。
在C++中,这可以表示为:

struct key {
    optional<SrcAddr> src;
    optional<DstAddr> dst;
    optional<AppId> appid;
};

unordered_map<key, std::list<key>>

当然,您需要在哈希表中添加许多额外的条目,以维护额外的键链接和列表。

相关问题