2

Всех приветствую, хотел бы узнать по поводу алгоритма со сложностью O(log(n)).

Есть класс, в нём атрибуты login, name, age, pass и т. д. Коллекция для них может быть любой, но желательно хотелось бы увидеть реализацию на TreeSet и т. д.

Как найти экземпляр класса в коллекции по атрибутам login и name? Коллекция может содержать от 5 000 до 50 000 объектов.

1
  • Сделайте HashMap<String, Person>, где ключи, например, login + name, а значения — ваши объекты. Commented 26 июл. 2021 в 21:36

1 ответ 1

2

Cоздайте составной ключ PersonKey, в котором будут содержаться login и name. Будем использовать TreeMap, поэтому реализуйте интерфейс Comparable:

public class PersonKey implements Comparable<PersonKey> {

    private final String login;
    private final String name;

    ...

    @Override
    public int compareTo(PersonKey other) {
        return Comparator.comparing(PersonKey::getLogin)
                .thenComparing(PersonKey::getName)
                .compare(this, other);
    }
}

Теперь можно складывать объекты в TreeMap:

Map<PersonKey, Person> people = new TreeMap<>();
people.put(new PersonKey(login, name), new Person(login, name, age))

И доставать за O(log(n)):

people.get(new PersonKey(login, name));
7
  • Вот интересно, а если бы через HashMap реализовать, по сложности бы также O(log(n)) было? Если не ошибаюсь, то с 8 версии джавы там под капотом красно-чёрные деревья для каждого бакета, а это значит что при хорошей хэш-функции может даже быстрее получится?
    – Sergey Zh.
    Commented 27 июл. 2021 в 1:53
  • Из HashMap, в среднем, вытащить элемент быстрее, так как O(1). Commented 27 июл. 2021 в 2:04
  • Вот я и думаю, странно что в задании требуется именно за log(n), когда можно было бы быстрее)
    – Sergey Zh.
    Commented 27 июл. 2021 в 2:09
  • 1
    Поэтому на практике обычно используют HashMap. А TreeMap только для ответов на вопросы :D Commented 27 июл. 2021 в 2:17
  • @Vadik а можно попросить показать реализацию на HashMap? Commented 27 июл. 2021 в 7:39

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.