Карта для 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) сложность, но у вас есть высокие постоянные коэффициенты .

Что касается вашей проблемы:

Вы можете иметь любое число Map s, которое будет использоваться для поиска ваших User s, оно все равно будет O(1):

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

Здесь у вас есть два Map, которые сопоставляют идентификаторы сеансов и идентификаторы пользователей с самим User.

Здесь важно то, что вы создаете поиски (например, отображение между userId - User и sessionId - User) для ваших User с и операция , чтобы получить пользователя с помощью его sessionId или userId равен O(1), потому что вам не нужно искать. Вы изменяете сложность пространства (размер Map с) на сложность времени (преобразовывая поиск O(n) в поиск O(1).

Если вы действительно хотите приступить к анализу асимптотической сложности, я бы предложил эту книгу .