Number of unique values in array in $\theta(n)$ average expected time

Question

My idea is to initialize a hash table (with chaining) with $n$ cells, having load factor $\alpha = 1$ hence having $\theta(1)$ expected number of values in each cell in the hash table, then go cell by cell, sort it, count the number of distinct values and add them to a global variable holding the count and return it.

The problem is I'm using the constant load factor to reason that the sorting of each hash table cell in $\theta(1)$ on average. Not sure how to explain this reasoning or if it is legal.

How to show the runtime is $\theta(n)$ in average, or if it is not actually $\theta(n)$, how can we do it in this time?

Answer 1

Going through the entire hash table contents is usually considered a bad idea.

Instead, while you insert to the hash table, you can keep a counter of the number of unique elements you have seen so far. When you want to add a new element to the hash table, check if it already exists. If it doesn't, insert it and increase the counter.

I'm sure this approach is much more intuitive to why it works in $\Theta(n)$ average :)