c++ - 多向哈希表

Question

如果之前有人问过这个问题，我提前道歉。如果有，我不知道这个数据结构会被称为什么。

我有 N 个（约 300 或更少）小部件的集合。每个小部件都有 M（大约 10 个）不同的名称。该集合将被填充一次，然后多次查找。我将在 C++ 中实现它。

这方面的一个例子可能是 200 人的集合，并以 7 种不同的语言存储他们的姓名。

查找函数基本上如下所示：lookup("name", A, B)，它将返回名称“name”从语言 A 到语言 B 的翻译（仅当 name 在集合中时）。

文献中是否有任何已知的数据结构可以有效地完成这类事情？最明显的解决方案是为查找创建一堆哈希表，但是为所有可能的对创建 MxM 哈希表很快就会变得笨拙且内存效率低下。我也愿意考虑排序数组（二进制搜索）甚至树。由于集合并不大，因此 log(N) 查找就可以了。

谢谢大家！

Answer 1

根据您对所需查找函数的描述，听起来您可以使用单个哈希表，其中键tuple<string, Language, Language>和值是翻译的结果。键中的两种语言分别标识字符串的源语言和所需翻译的语言。

Answer 2

创建一个 N×M 数组 D，这D[u,v]就是小部件 u 的语言 v 中的单词。

还要创建 M 个哈希表，H₀...Hₘ（其中 m 是 M-1），Hᵥ(w).data如果 w 是语言 v 中小部件 u 的词，则为 u。

要执行lookup(w, r, s)，
(1) 设置 u = Hᵣ(w).data
(2) 如果D[u,r]等于 w，则返回D[u,s]，否则返回未找到。