c# - 实现简单的字符串实习

Question

问题

我收集了大量的字符串，这些字符串在某些对象中是重复的。需要的是字符串实习。这些对象使用 protobuf-net 序列化和反序列化。 .我知道它应该处理 .NET 字符串插入，但我的测试表明，我自己获取所有这些字符串并创建一个 Dictionary<string, int> (值与其唯一标识符之间的映射)，将原始字符串值替换为整数，可获得更好的结果。

不过，问题在于映射。它只能单向搜索(我的意思是 O(1) 可搜索)。但我想在 O(1) 中按键或按值搜索。不仅仅是按键。

方法

字符串集是固定的。这听起来像一个数组。按值搜索是 O(1)，快得让人眼花缭乱。甚至没有像字典中那样摊销 - 只是按索引保持不变。

数组的问题在于按键搜索。这听起来像哈希。但是，嘿，n散列并不是说均匀分布在 n 之间n 的细胞- 元素数组。使用模数，这可能会导致冲突。这很糟糕。

比方说，我可以创建一个 n * 1.1 -length 数组，并尝试随机散列函数，直到我没有冲突但是......那......只是......感觉......错误。

问题

如何解决问题并通过键(字符串)和值(整数)实现 O(1) 查找时间？

两个字典不是一个选项；)

Answer 1

答案是两本字典。我知道你说过这不是一个选择，但如果没有理由，很难看出两个字典如何不能完美地回答你的场景，并且代码易于理解、快速、内存效率高。

从这里看来，您似乎要执行两个基本操作；

myStore.getString(int); // O(1)
myStore.getIndexOf(string); // O(1)

您很高兴其中一个实现为字典，但另一个则不然。是什么让您犹豫不决？