Сложность поиска метода по ключу в TreeMap составляет O(log n), где n - количество элементов в коллекции.
Это связано с тем, что TreeMap основан на структуре данных "красно-черное дерево". В таком дереве, балансировка гарантирует, что высота дерева логарифмически зависит от количества узлов. Операции поиска, вставки и удаления требуют обхода дерева от корня до нужного узла, что занимает время, пропорциональное высоте дерева.
java