5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ in practice (1) chaining is worse than linear probing and (2) BSTs are worse than hashtables for this task $\endgroup$ – rgrig May 15 '12 at 19:35
  • $\begingroup$ It's important to note that using a perfect hash function is entirely tractable for a natural language like English, which has a very small number of distinct formal words in its universal set. This may easily be intractable for other languages or for the universe of all candidate words (formally, $\sum_{m=1}^p n^m = n(n^p-1)/(n-1)$ for $n$ characters of your language and $p$ for the maximal number of characters per word), but OED is a reasonable approximate bound on English. $\endgroup$ – MrGomez May 17 '12 at 0:50
  • $\begingroup$ Just in case you're looking for an answer in practice: Use a set / dictionary data type, insert the words and count the length of the set. For Python sets, the average time complexity for insertion of one element is in $\mathcal{O}(1)$ (source). This is in principle exactly your approach, but you don't have to write your hash functions / decide about probing. $\endgroup$ – Martin Thoma Dec 27 '13 at 18:19
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I agree with svick, when you find a hash that is already present in your table, you simply do a +1 to that entry's counter. However, i don't fully agree that you should bother handling collisions. It is sufficient that you choose a "decent" hashing algorithm (SHA1 or better) and let it do its work. SHA1 produces 160bit hashed strings and should start having collisions after roughly 2^80 attempts (much less according to this article: schneier.com/blog/archives/2005/02/sha1_broken.html) however in a number always >> than any natural language dictionary. $\endgroup$ – Avio May 16 '12 at 10:06
  • 1
    $\begingroup$ @Avio, SHA1 won't help you with that, because it's not feasible to have $2^{160}$ buckets, which is required if you want to use it to the full extent. And the number of collisions depends on the number of buckets, not just on the number of possible values of the hashing algorithm. $\endgroup$ – svick May 16 '12 at 10:33
  • $\begingroup$ Uhm, I was talking about a plain and general purpose hashmap from stl or boost or whatever library one wants to use. If you chose to use, for example, SHA1 you can fill the map with hashed values (let's say strings for the sake of simplicity) that -likely- will never collide because of the small amount of natural language words with respect to the key-space chosen by using a "decent" hash algorithm. Here I'm just talking about collisions outside the hashmap but I agree that inside the hashmap there will be collisions (automatically handled by chaining or whatever method stl and boost use). $\endgroup$ – Avio May 16 '12 at 12:45
  • $\begingroup$ @Avio, oh, OK. But I don't see any advantage in using SHA1s of words rather than the words directly. If those were big files, it would make sense, but not for words. $\endgroup$ – svick May 16 '12 at 14:05
  • $\begingroup$ The advantage is exactly that you can somehow "override" the embedded hashing function inside the hashmap and use a more robust hashing algorithm. And then you can almost forget about collisions (in this specific case). $\endgroup$ – Avio May 16 '12 at 14:23
3
$\begingroup$

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:

  • implementing buckets as binary trees or as other hash tables (with other hash functions);
  • using a Self-balancing binary search tree, it would have $O(\log n)$ time to insert and $O(\log n)$ time to search.

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))$.

$\endgroup$
  • $\begingroup$ BST needs O(log n) time for each insertion. $\endgroup$ – MMS May 15 '12 at 14:39
  • $\begingroup$ I'm tempted to guess you never actually benchmarked this in practice. Am I right? $\endgroup$ – rgrig May 15 '12 at 19:36
  • $\begingroup$ @rgrig you are right! I have neve benchmarked this in practice. Did you? Is there something that I need to know? Please write me. $\endgroup$ – Виталий Олегович May 15 '12 at 19:46
  • $\begingroup$ i already put a comment on the question $\endgroup$ – rgrig May 15 '12 at 19:48
  • $\begingroup$ @rgrig could you please provide some links or references to books or articles or research papers that show the reason why in practice Hash Tables are better? $\endgroup$ – Виталий Олегович May 15 '12 at 19:51
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.