Как бы сделал быстрый поиск по условию в коллекции

# Быстрый поиск по условию в коллекции Java

Существует несколько подходов для поиска элементов в коллекции. Выбор зависит от размера данных, частоты поисков, структуры и требуемой производительности.

1. Stream API с filter() и findFirst()

Самый простой и читаемый подход для большинства случаев:

public class UserRepository {
    private List<User> users;
    
    // Однократный поиск
    public Optional<User> findUserByEmail(String email) {
        return users.stream()
            .filter(u -> u.getEmail().equals(email))
            .findFirst();  // Short-circuit: останавливается после первого
    }
    
    // Несколько результатов
    public List<User> findUsersWithAge(int minAge) {
        return users.stream()
            .filter(u -> u.getAge() > minAge)
            .collect(Collectors.toList());
    }
}

Преимущества: декларативный стиль, lazy evaluation, хорошая читаемость. Недостатки: медленнее на очень больших списках по сравнению с индексами.

2. Цикл for (классический подход)

Для критичных по производительности сценариев:

public Optional<User> findUserByIdOptimized(int userId) {
    for (User user : users) {
        if (user.getId() == userId) {
            return Optional.of(user);
        }
    }
    return Optional.empty();
}

Преимущества: максимальная скорость, full control, минимум overhead. Недостатки: более многословно, нужна явная логика остановки.

3. Использование Map/HashMap для O(1) поиска

Лучший выбор для частых поисков по одному полю:

public class UserRepository {
    private Map<Integer, User> usersById;        // id → User
    private Map<String, User> usersByEmail;      // email → User
    private Map<String, List<User>> usersByRole; // role → List<User>
    
    // Инициализация (обычно в конструкторе или методе init)
    public void buildIndexes(List<User> allUsers) {
        usersById = allUsers.stream()
            .collect(Collectors.toMap(User::getId, u -> u));
        
        usersByEmail = allUsers.stream()
            .collect(Collectors.toMap(User::getEmail, u -> u));
        
        usersByRole = allUsers.stream()
            .collect(Collectors.groupingBy(User::getRole));
    }
    
    // Поиск за O(1)
    public Optional<User> findUserById(int id) {
        return Optional.ofNullable(usersById.get(id));
    }
    
    // Поиск по email за O(1)
    public Optional<User> findUserByEmail(String email) {
        return Optional.ofNullable(usersByEmail.get(email));
    }
    
    // Поиск по role за O(1) для получения списка
    public List<User> findUsersByRole(String role) {
        return usersByRole.getOrDefault(role, Collections.emptyList());
    }
}

Преимущества: O(1) поиск, масштабируется на больших наборах данных. Недостатки: использует больше памяти, нужно поддерживать индексы в актуальном состоянии.

4. Stream с промежуточными операциями (distinct, sorted)

Для более сложных фильтраций:

public List<User> findActiveAdminsOrderedByEmail() {
    return users.stream()
        .filter(u -> u.isActive())        // фильтр 1
        .filter(u -> u.getRole().equals("ADMIN"))  // фильтр 2
        .sorted(Comparator.comparing(User::getEmail))
        .distinct()  // убрать дубликаты
        .limit(10)   // ограничить результат
        .collect(Collectors.toList());
}

5. Использование Java Collections.binarySearch()

Для отсортированных коллекций - O(log n):

List<Integer> sortedNumbers = Arrays.asList(1, 3, 5, 7, 9);
int index = Collections.binarySearch(sortedNumbers, 5);
if (index >= 0) {
    System.out.println("Найдено на позиции: " + index);
} else {
    System.out.println("Не найдено");
}

Преимущества: O(log n) для отсортированных данных. Недостатки: требует предварительной сортировки.

6. Использование parallel() для многопоточного поиска

Для очень больших коллекций:

public List<User> findLargeDatasetFiltered() {
    return users.parallelStream()  // многопоточная обработка
        .filter(u -> heavyConditionCheck(u))
        .collect(Collectors.toList());
}

Преимущества: использует несколько ядер, хорошо для 100k+ элементов. Недостатки: overhead synchronization для маленьких наборов.

7. Практический пример: комбинированный подход

public class UserService {
    private List<User> allUsers;
    private Map<Integer, User> userCache;  // индекс по id
    
    // Для частых поисков по id используем cache
    public User getUserById(int id) {
        return userCache.get(id);
    }
    
    // Для редких, сложных поисков используем Stream
    public List<User> findActiveUsersCreatedAfter(LocalDate date) {
        return allUsers.stream()
            .filter(User::isActive)
            .filter(u -> u.getCreatedDate().isAfter(date))
            .collect(Collectors.toList());
    }
    
    // Для очень больших наборов данных - параллельный поиск
    public long countExpiredUsers() {
        return allUsers.parallelStream()
            .filter(User::isExpired)
            .count();
    }
}

Когда какой подход использовать?

Бенчмарк-примеры

List<Integer> list = IntStream.range(0, 1_000_000).boxed().collect(Collectors.toList());
int target = 500_000;

// Stream: ~0.5ms
long start = System.nanoTime();
list.stream().filter(i -> i == target).findFirst();
long streamTime = System.nanoTime() - start;

// For цикл: ~0.1ms
start = System.nanoTime();
for (int i : list) {
    if (i == target) break;
}
long forTime = System.nanoTime() - start;

// HashMap: ~0.001ms
set = new HashSet<>(list);
start = System.nanoTime();
set.contains(target);
long setTime = System.nanoTime() - start;

Заключение

Для большинства случаев Stream API с filter() обеспечивает хороший баланс между производительностью и читаемостью. Если поиск часто повторяется, создайте индекс на основе Map. Для критичных по производительности участков используйте Collections.binarySearch() (если данные отсортированы) или HashMap. Помните: оптимизируйте только после профилирования!