Well, when you talk about peformance of TreeSet and HashSet you should clearly understand how these structures are organized what consequences of its organization.
Typically TreeSet is a structure where all elements are organized in a binary tree. Thus adding a member or accessing it is ~O(log(N))
.
In other hand HashSet is a structure similar to an array. The difference is that in an array index is an unique number, while in a HashSet each key needs to be translated into index with the help of a hash function. A hash function may produce the same results for different input data, the situation is called hash collision
. A good hash function (yes, they could be bad and good) produces as many unique results on a given set of input data as possible.
So accessing data in a hash set costs calculations of a hash function (in Java usually this is .hashCode()
) and possible conflict resolution. That is its estimated as O(1) i.e. a constant number of operations.
You should understand that O(1) is not always less than O(log(n)), it's less asymptotically and on big enough n
. Also a proper choice of a hash function does matter.