SELECT

Условие

/* SELECT left.K, left.V1, right.V2 FROM left JOIN right ON left.K = right.K; */ public <K extends Comparable<K>, V1, V2> List<Triple<K, V1, V2>> join(List<Pair<K, V1>> left, List<Pair<K, V2>> right) { return null; }

private static class Pair<A, B> { private A first; private B second;

Pair(A first, B second) {
    this.first = first;
    this.second = second;
}

}

private static class Triple<A, B, C> { private A first; private B second; private C third;

Triple(A first, B second, C third) {
    this.first = first;
    this.second = second;
    this.third = third;
}

}

Ответ

Ниже приведена реализация функции join, которая выполняет внутреннее соединение (inner join) двух списков пар по ключу K. Для эффективности используется Map для быстрого поиска соответствующих элементов из второго списка.

public <K extends Comparable<K>, V1, V2> List<Triple<K, V1, V2>> join(List<Pair<K, V1>> left, List<Pair<K, V2>> right) {
    Map<K, V2> rightMap = new HashMap<>();
    for (Pair<K, V2> pair : right) {
        rightMap.put(pair.first, pair.second);
    }

    List<Triple<K, V1, V2>> result = new ArrayList<>();
    for (Pair<K, V1> pairLeft : left) {
        V2 v2 = rightMap.get(pairLeft.first);
        if (v2 != null) {
            result.add(new Triple<>(pairLeft.first, pairLeft.second, v2));
        }
    }
    return result;
}

Здесь:

• Создаётся словарь из правого списка для быстрого поиска по ключу.
• Проходим по левому списку, для каждого ключа ищем соответствующее значение в правом.
• Если найдено, создаём Triple и добавляем в результат.

Это соответствует SQL-запросу с JOIN по ключу K.