2

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

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

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

1
  • Сделайте HashMap<String, Person>, где ключи, например, login + name, а значения — ваши объекты. 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.
    27 июл 2021 в 1:53
  • Из HashMap, в среднем, вытащить элемент быстрее, так как O(1). 27 июл 2021 в 2:04
  • Вот я и думаю, странно что в задании требуется именно за log(n), когда можно было бы быстрее)
    – Sergey Zh.
    27 июл 2021 в 2:09
  • 1
    Поэтому на практике обычно используют HashMap. А TreeMap только для ответов на вопросы :D 27 июл 2021 в 2:17
  • @Vadik а можно попросить показать реализацию на HashMap? 27 июл 2021 в 7:39

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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