Data structure to count occurrences of words
There are many ideas to speed up hashtables, or hash maps.  Some ideas appear in an article about hashtables in PHP, and a comment describing hashtables in Ruby.  I present some ideas here, but these ideas might or might not speed up your program, because I have not tested them.

Add a counter for each word.  If the word "the" appears 20 times, your code adds 20 entries for "the".  The idea is to have 1 entry for "the", with the counter set to 20.  This would be like using Java's HashMap&lt;String, int&gt; to map the word to the counter.

For this idea, you would add an int count; to class Node.  To add n copies of word, you would searches for the Node with word, and add n to its count.  If the Node didn't exist, you would insert a new Node and set its count.  Your table would have fewer nodes, so searches might be faster.  Also, there would be only one node for each word, so you would stop searching if you found the node.

Change the hash function.  Your hash function seems to multiply the character codes in a string.  If a string has one even-numbered character (like 'l', 'n', 'r', 't'), then the product is a multiple of 2.  If the string hash two such characters, then the product is a multiple of 4, and so on.  With 100 buckets, your hash might put most words in the multiple-of-4 buckets, and some words in the other even buckets, and almost no words in the odd buckets.  Then your program would search for most words in the power-of-4 buckets, but those buckets would have long lists of nodes.

A better hash function might use a rotation (also known as a barrel shift) to spread the bits, with addition to mix in each character.

int hash = 0;
for (int i = 0; i &lt; a.length(); i++) {
    hash = Integer.rotateLeft(hash, 5);
    hash += (int)a.charAt(i);
}


Use power-of-2 buckets.  Division a / b and modulus a % b tend to be slow when b isn't constant.  Your hash function has sum = sum % array.length.  If the length was a power of 2, you would use sum = sum &amp; (array.length - 1) to get the modulus.  For this idea, your constructor WordStoreImp(n) would round up n to a power of 2, with code like

if (n &lt; 16)
    n = 16;
else
    n = Integer.highestOneBit(n - 1) &lt;&lt; 1;


For example, if n was 100, then the highest 1-bit in 99 is 64, and 64 shifted left by 1 is 128.  Because 128 is 2 to the 7th power, so hash &amp; 127 extracts the low 7 bits of hash as an integer from 0 to 127.

Switch from open chaining to open addressing.  Your hash table uses an open chain (or linked list) in each bucket.  You allocate memory with new Node, but memory allocation might be slow.  The idea is to switch to open addressing and remove the new Node calls.

With open addressing, each bucket holds exactly one word.  You would allocate the buckets with

words = new String[n];
counts = new int[n];


This sets each word to null and each count to zero.  A bucket is empty when its word is null.  To search for a word, if the bucket has a different word, you check the next buckets until you find the correct word, or an empty bucket.

pos = hashFunction(word);
while (strings[pos] != null &amp;&amp; !strings[pos].equals(word))
    pos = (pos + 1) &amp; mask;  // where mask = strings.length - 1


At this point, count[pos] is the correct count for this word.  If the bucket is empty, then the count is still zero.  If you are adding the word, then you would put strings[pos] = word and increase the count.

In open addressing, a bucket with a word can never become empty; you can only remove a word by setting its count to zero, and leaving the word in the bucket.  To be fast, at least half of the buckets must be empty.  You would keep a count of the number of words in the table.  When the count reaches n/2, you would allocate a new table with twice as many buckets, and move all the words to the new table (skipping words where the count is zero).