Поиск в коллекции по двум полям со сложностью O(log(n))

Question

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

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

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

Answer 1

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));

БЛОГ НА HUSL

Поиск в коллекции по двум полям со сложностью O(log(n))

Ответы (1 шт):