我计划在某种语言中保存大量的句子，这样每个元素都有一个指向该句子到不同语言翻译的指针。
通过对句子进行排序，我可以创建一个平衡二叉树，并在O(logn)内添加/删除/搜索。
是否有一种方法来保存哈希表中的元素?在这种情况下哈希函数是什么样的呢?
我希望能够搜索任何语言的句子，并返回任何其他语言的翻译。
如果我有K种语言，使用平衡树，我对K棵树的搜索时间为O(klogn)。有没有更好的办法?
是的，trie更适合字符串搜索。此外，我将所有语言的所有句子存储在单个trie中，value是所有可用翻译的列表。
在这种情况下，搜索将是O(k)，其中k是搜索句子的长度。
乌利希期刊指南如果您只搜索已知的语言并将其翻译成另一种已知的预先语言，则:
使每一个为三个的值Map<(Source Language) → Map<(Target language) → Translation>>
您将有以下工作流程:查找值，对应于树中的给定句子。在找到的Map中搜索源语言。如果找到，这意味着句子是目标语言(假设语言之间可能存在冲突)。此时，找到的Map(内部)表示目标语言的所有可用翻译。搜索您想要的
实现这两个map的最高效的方式将是plain array。其中i-th元素表示i-th翻译的值(假设您有有限数量的翻译，并且可以为每个翻译分配不同的索引)。搜索已知的翻译将是O(1) -仅仅访问数组中的已知索引。但是这种方法也会消耗大部分内存，因为如果您在Map中有稀疏的值，您的后台数组仍然会消耗固定数量的内存(与所有可能的翻译数量成正比)。
但是这种方法将适用于内部Map(据我所知，其中存储了所有可能语言的翻译)。
对于外部映射，我可以预期它是稀疏的，您有几个选项:
- 如果不同语言句子之间的平均冲突次数很小(1-2次)，则可以直接将Key→Value对存储在列表中。平均搜索时间为常数。
- 如果冲突的平均数量是显著的，但仍然不够大到可以使用数组(内部Map的方法)，那么通过哈希表返回这个Map，其大小将是Map中预期值的数量-冲突的平均数量。然后你将得到O(1)的平摊搜索时间。
- Map似乎是密集的-使用数组方法，就像内部Map。
UPD2 例子:
假设下面的句子可以相互翻译:你好(en)你好[es]喂(nl)喂[de]
你应该把它们全部加到trie中，值如下:
Hello -> Map([en] -> Map([en]->Hello, [es]->Hola, [nl]->Hallo, [de]->Hallo))
Hola -> Map([es] -> Map([en]->Hello, [es]->Hola, [nl]->Hallo, [de]->Hallo))
Hallo -> Map([nl] -> Map([en]->Hello, [es]->Hola, [nl]->Hallo, [de]->Hallo),
[de] -> Map([en]->Hello, [es]->Hola, [nl]->Hallo, [de]->Hallo))
这里的方括号与数组无关，它们用于在视觉上区分语言。
所以，当你在你的树中执行搜索时，你不知道你的句子是用哪种语言写的。当你从树(Map of Maps)中得到一个值时，你可以将句子的原始语言"映射"为所需语言的翻译。
回到例子，如果你有一个句子"hello"，你知道它在[de]中，你想把它翻译成[en]。在树中搜索"hello"，得到:
Map([nl] -> Map([en]->Hello, [es]->Hola, [nl]->Hallo, [de]->Hallo),
[de] -> Map([en]->Hello, [es]->Hola, [nl]->Hallo, [de]->Hallo))
现在你从这个地图中得到[de]的值(当你在[de]中思考你的句子时)。你会得到:
Map([en]->Hello, [es]->Hola, [nl]->Hallo, [de]->Hallo)
现在获取搜索目标语言在这个地图([英文])。你会收到"Hello"。
当然，除了Trie->Map->Map结构，您可以使用Map->Trie->Map，其中第一个Map将源语言映射到相应的字典，由Trie表示。但我认为这是较低的内存效率，因为不同语言中的单词似乎经常共享相同的前缀，因此将它们放在一个trie中可以节省内存。但是在性能效率方面是一样的，所以这取决于你。