I have an ArrayList<LinkedHashSet<String>> setOfStrings for example this arraylist internally is composed like:

positionX[hello,car,three,hotel,beach]
positionY[.....]
...

I want to find car inside this data-structure, so I did it

for (Iterator<LinkedHashSet<String>> iterator = setOfStrings.iterator(); iterator.hasNext();) { 
    LinkedHashSet<String> subSet = iterator.next();
    if (subSet.contains("hotel"))
        System.out.println("found");
}

The for iterate over the entire arrayList and the complexity in the worst-case is O(n), but I'm confused on the complexity of the method contains() of set. In according of javadocs this method is executed in constant time, but I've heard that in certain cases the complexity might become O(n). Saying that, I'm not sure about the complexity of this snippet algorithm.

Can someone provide me an explanation of that?