Все ли коллекции в Java реализуют интерфейс Collection?

Нет. В Java Collections Framework существует два основных корневых интерфейса: Collection и Map.

• Интерфейс Collection является предком для List, Set и Queue. Все классы, реализующие эти интерфейсы (например, ArrayList, HashSet, LinkedList), являются Collection.
• Интерфейс Map (HashMap, TreeMap, LinkedHashMap) представляет собой отдельную иерархию для структур "ключ-значение" и НЕ является подтипом Collection.

Почему: Map имеет принципиально другой API (методы put(), get() по ключу), который не совместим с контрактом Collection (добавление одиночных элементов add()).

Пример:

import java.util.*;

// Эти объекты реализуют Collection
Collection<String> list = new ArrayList<>();
Collection<String> set = new HashSet<>();

// Этот объект НЕ реализует Collection
Map<String, Integer> map = new HashMap<>();
// System.out.println(map instanceof Collection); // false

Однако, можно получить представление коллекций из Map через методы keySet(), values() или entrySet(), которые возвращают объекты типа Collection.