Какие способы реализации операции join в памяти существуют и как выбрать подходящий?

Что проверяют

Умеете ли вы оценить сложность по времени и памяти и выбрать алгоритм под данные, а не по названию. Часто просят написать hash join на коллекциях Java и спрашивают, что изменится для left join или при дубликатах ключей.

Как отвечать

• nested loop: два вложенных цикла, O(n·m) по времени и никакой дополнительной памяти. Годится для маленьких списков и для условий неравенства вроде a.start < b.end, где хэш бесполезен;
• hash join: фаза построения кладёт меньшую сторону в Map<K, List<B>>, фаза проверки проходит по большей и достаёт пары. В среднем O(n + m), память пропорциональна меньшей стороне. Работает только на равенстве ключей и требует корректных equals и hashCode;
• sort-merge join: сортировка обеих сторон за O(n log n + m log m), затем слияние двумя указателями за линейное время. Выигрывает, когда данные уже отсортированы (например, из базы с ORDER BY) и когда результат нужен упорядоченным;
• index join: если по одной стороне уже есть индекс (HashMap или TreeMap), это hash join без фазы построения, а TreeMap добавляет поиск по диапазону.

Правило выбора: условие равенства и одна сторона помещается в память, значит hash join. Данные упорядочены или нужен диапазон, значит merge. Совсем маленькие объёмы или сложное условие, значит nested loop. Если в память не влезает ни одна сторона, данные партиционируют по хэшу ключа на диск и джойнят по частям, это grace hash join.

Для left join хэш строят по правой стороне и идут по левой, тогда строки без пары выводятся сразу. Карту стоит создавать с нужной ёмкостью: HashMap.newHashMap(n) с Java 19 избавляет от рехеширования.

Где спотыкаются

Строят хэш-таблицу по большей стороне. Памяти уходит в разы больше, и на больших объёмах это OutOfMemoryError.

Теряют дубликаты ключей. Collectors.toMap падает с IllegalStateException на повторе, а в merge join при совпадении сдвигают оба указателя и пропускают пары: группы с одинаковым ключом надо перемножить.

Забывают про null и изменяемые ключи. В SQL NULL не равен NULL, а HashMap спокойно сопоставит два null-ключа. Ключ, у которого поменялось поле после вставки, в карте уже не найти.