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?
Best Answer
LinkedHashSet
, for the intents and purposes of being accessed usingcontains
is simply a hash set. It uses the return fromhashCode
of the objects inserted in it to determine the position to place it in in the hash set. If you have a collision, then it will then check the next element. If that is occupied, it will then check the one after that, and so forth. Therefore, for hash sets with relatively small capacity or types which do not return distinguishablehashCode
values, you will see up toO(n)
complexity for insertion or checking the esistence of an item in the hash set. However most times you don't see collisions and so in most cases it will beO(1)
.Combine this with a
O(n)
operation on all entires in yourArrayList
, and you end up withO(n)*O(1)
complexity on average orO(n)
. However if thehashCode()
does not properly distinguish values or if the capacity is small for theLinkedHashSet
, you may see up toO(n*m)
complexity (O(n)*O(m)
) where n is the number of elements in yourArrayList
and m being the number of elements on average in eachLinkedHashSet
.Hope that answers your question!