映射O（1）搜索键和值

Question

考虑我有一堂课：data class User(val userId: String, val roles: List<String>)另外，我有一些字符串sessionId，我需要O(1)时间通过sessionId和来检索数据userId。我认为BiMap<String, User>能解决我的问题，但通过用户的搜索是不是O(1)因为我要投User给userId第一。另一个解决方案是覆盖User仅userId考虑到哈希码/等式，但这是一个肮脏的技巧。

Answer 1

将User转换userId为O(1)。如果您要进行复杂度分析，则只需要取指数最大的术语，其余的取而代之。

如果您执行相同的操作1000次，O(1)则始终始终执行1000次操作仍然会如此。如果运算的数量是恒定的，并且不取决于输入的大小，则说明您具有O(1)复杂性，但是具有较高的恒定因子。

至于你的问题：

您可以使用任意数量的Maps来查找Users，它仍然是O(1)：

val sessionLookup = mapOf<String, User>()
val userIdLookup = mapOf<String, User>()

在这里，您有两个Map，用于将会话ID和用户ID映射到User自身。

在这里重要的是，您为s创建查找（例如，userId-User和sessionId-之间的映射User），User并通过其sessionId或userId来获取用户的操作是O(1)因为您不必搜索。您可以将空间复杂度（的大小Map）与时间复杂度（将O(n)搜索转换为O(1)查找）进行权衡。

如果您真的想进行渐进复杂性分析，建议您本书。