I am still fighting with hashing and I am ask myself: what is the most efficient way to count the number of different words in a text using a hash table?
My intuition says that applying the hashcode function to every word in the text, as result we will have words with different hash values in different buckets and the same words will have the same bucket and therefore we will have a collision problem which we can resolve using the chaining method.
Does it work like that?
If you really just want to count the number of distinct words in the document, you don't need to save each instance of the word to the hash table.
So, if you find a words that's already in the table, just don't add it there. This means you don't have to deal with chaining as often, which will speed things up.
But you still have to deal with collisions, because two different words can have the same hash code.
This way, the expected time complexity is $\mathcal{O}(n)$, where $n$ is the total count of characters in the text, assuming a good hash function.
Hash table is very good if you have few words that are repeated many times.
Let's suppose that your hash function is very good, that means that the distribution of elements inside various buckets is close to the uniform distribution. Even in that case, if the number of buckets is much smaller than the number of elements inside the table, the execution time of search in hash tables with buckets implemented as linked lists is $O(n)$, where $n$ is the number of different words that you have found.
This happends because in the simplest implementstions each bucket is a simple list and if inside a bucket you will have $k$ elements, the cost of the search would be the sum of the cost to calculate hash function plus the cost to find the right bucket plus the cost to find the right element inside the list. The first two costs are $O(1)$ the last one is $O(k)$ because you are performing linear search.
If you have few elements and lots of buckets, $O(k)$ will be close to $O(1)$, otherwise it will be close to $O(n)$ as stated above.
If the number of words is much bigger than the number of buckets, the best choices are:
For more discussion about hash table performance, see: Hash table vs Balanced binary tree
From wikipedia:
For the best possible choice of hash function, a table of size n with open addressing has no collisions and holds up to $n$ elements, with a single comparison for successful lookup, and a table of size $n$ with chaining and $k$ keys has the minimum $\max(0, k-n)$ collisions and $O(1 + k/n)$ comparisons for lookup.
[...]
In more realistic models, the hash function is a random variable over a probability distribution of hash functions, and performance is computed on average over the choice of hash function. When this distribution is uniform, the assumption is called "simple uniform hashing" and it can be shown that hashing with chaining requires $Θ(1 + k/n)$ comparisons on average for an unsuccessful lookup, and hashing with open addressing requires $Θ(1/(1 - k/n))$.
This method seems to work and, if implemented efficiently, it must be O(n), because each word is processed once. As each word must be processed at least once, the problem is Ω(n). So, such a solution is also efficient.
