Avoiding O(n^2)

I'm working with some objects given to me by the API for an architectural modeling program. When navigating the model, I get a set of Component objects. One of the data members of these Component objects is a set of Interface objects.

I'm looking to search for a specific Interface object within these, but am constrained by the fact that I have to search on the Interface object's name, not on the object itself. I'm trying to figure a good way to do this not in O(n^2). This is an example snippet.

for each(Component comp in componentSet)
{
interfaceSet = comp.getInterfaces();
for each(Interface inter in interfaceSet)
{
if (inter.getName().compare("FOO") == 0)
... do something
}
}
I keep trying different methods like throwing things into maps, etc, but keep coming back to the fact that I always need to keep interfaces coupled with their respective components, and for every component in the set, I need to search every interface in their respective sets.