假设我有一个类:
data class User(val userId: String, val roles: List<String>)
另外，我有一些字符串 sessionId我需要 O(1)两个 sessionId 检索数据的时间和 userId .
我认为 BiMap<String, User>将解决我的问题，但用户搜索不是 O(1)因为我需要投 User至 userId第一的。
另一种解决方案是覆盖 User 的哈希码/等于只需要 userId考虑在内，但这是一个肮脏的黑客。
最佳答案
将 User 转换为 userId 是 O(1)。如果您正在进行复杂性分析，则只需取指数最大的项并舍弃其余项。
如果您执行相同的操作 1000 次，如果您始终恰好执行 1000 次操作，它仍然是 O(1)。如果操作数是常数并且不依赖于输入的大小，则您的复杂度为 O(1)，但您有高常数因子。
关于你的问题:
您可以使用任意数量的 Map 来查找您的 User，它仍然是 O(1):
val sessionLookup = mapOf<String, User>()
val userIdLookup = mapOf<String, User>()
这里有两个 Map，它们将 session ID 和用户 ID 映射到 User 本身。
这里重要的是您创建查找(例如:userId - User 和 sessionId - User 之间的映射code>) 为您的 User 和通过其 sessionId 或 userId 获取用户 的操作是 O(1) 因为您不这样做必须搜索。您将空间复杂度(Map 的大小)与时间复杂度(将 O(n) 搜索转换为 O(1)查找。
如果你真的想进入渐近复杂性分析，我建议 this book .
关于java - O(1) 的映射同时搜索键和值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51038315/