OK I'm implementing a data structure called "trie" to store a dictionary of words. The text file I'm reading in has over 172K words....this, with a good implementation of a trie should not take more than 20-22MBs of memory. For some reason my implementation gives me an OutOfMemoryError.
If I use a small dictionary....say 50K words everything is fine...any ideas?
BTW...I'm passing a hashedMap set to add.
Code:class TrieNode { TrieNode[] myLinks; boolean myIsWord; String myWord; /** * create a new TrieNode (characters a-z and ' ') */ public TrieNode() { myLinks = new TrieNode[Trie.ALPH]; myIsWord = false; myWord = null; } } public class Trie { TrieNode root; public static final int ALPH = 27; public Trie() { root = new TrieNode(); } /** * Add a string to the trie * * @param s The string added to Trie */ public void add(String s) { TrieNode t = root; int limit = s.length(); for(int k=0; k < limit; k++) { int index = index(s.charAt(k)); if (t.myLinks[index] == null) { t.myLinks[index] = new TrieNode(); } t = t.myLinks[index]; } t.myIsWord = true; t.myWord = s; } /** * print every word in the trie, one per line * */ public void printTrie() { printTrie(root); } private void printTrie(TrieNode t) { if (t != null) { if (t.myIsWord) { System.out.println(t.myWord); } for(int k=0; k < ALPH; k++) { if (t.myLinks[k] != null) { // System.out.println("Descend to child " + letter(k)); printTrie(t.myLinks[k]); } } } } /** * determine if a word is in the trie (starting at root) * * @param s The string searched for * @return true iff s is in trie (starting at root) */ public boolean contains(String s) { TrieNode t = root; int limit = s.length(); for(int k=0; k < limit; k++) { int index = index(s.charAt(k)); if (t.myLinks[index] == null) return false; t = t.myLinks[index]; } return t.myIsWord; } // convert all unknown symbols to spaces public static int index(char ch) { int i = (int) (ch - 'a'); if ((i < ALPH-1) && (i >= 0)) return i; else return ALPH-1; } public static char letter(int i) { if (i == ALPH-1) return ' '; else return (char) (i + 'a'); } }