Counting unique elements of a finite set usually requires linear time/space; this means the bigger the set of unique elements the more time/space it will take us to keep an exact count of unique elements.
A good example of this is the usage of an HashSet - we add an element to a Set (to ensure uniqueness), it gets hashed and stored:
-
In case it's the first one, it is added and that's it;
-
In case it isn't (in case of an hash collision, duplicate value, etc) various things can happen; most common implementations use [Linear Probing][1]