Counting repeated words in a file

Question

hi,

Goal: to find count of all words in a file. file contains 1000+ words

My approach: use a HashMap() to store and count the number of times each word appears in the file.

Question: Would a HashMap() be the best way or would it be better to use a Binary Tree for ensuring faster lookup as there is a large count of words in the file?

Or is there a better way to do this?

HashMap would result in a lot of memory overhead which is not desired.

Thanks

Answer 1

1000 - 10000 words is very small.

A Hashmap will be fine.

Answer 2

A HashMap is perfect. You need to store

• a copy of each word encountered
• the count for each

A HashMap really won't store much more than that!

Answer 3

So you're looking for distinct words?

The most efficient structure I can think of is a Trie

Here's one open source implementation: Google Code patricia-trie

Although I tend to agree with Mitch Wheat -- It sounds like a HashMap should work fine (It's always best to avoid premature optimization... so you should use a HashMap until you've shown that it's a bottleneck)

Answer 4

1. Assuming that the strings are not insanely long, a "Trie" approach as Michael suggest would be good. The node in the Trie can store the character and the "count" of the strings that end with that character. This should drastically reduce the storage requirements (again assuming the strings are uniformly distributed and overlapping)

2. Assuming that the counts are not to be persisted across invocations, while using a HashMap, let the Map be from Integer => Integer - where the "key" is the hashcode of the string and value the count. This should be a efficient solution - with fast lookup and reduced memory foot print.

Answer 5

I would recommend doing such a task in Perl/PHP. It's very hard to kill a fly with a machine gun.