Implementing a Dictionary in Java: HashSet vs Trie

Could you provide some implementation of a Dictionary having a large number of words in Java?

Certainly! Implementing a dictionary in Java can be done using various data structures, but one of the most efficient ways to store a large number of words is by using a HashSet or a Trie. Below, I'll provide an example of both implementations.

1. Using HashSet

A HashSet is a collection that contains no duplicate elements and allows for fast lookups. This is a simple way to implement a dictionary.

import java.util.HashSet;

public class Dictionary {
    private HashSet<String> words;

    public Dictionary() {
        words = new HashSet<>();
    }

    // Method to add a word to the dictionary
    public void addWord(String word) {
        words.add(word.toLowerCase()); // Store words in lowercase for case-insensitivity
    }

    // Method to check if a word exists in the dictionary
    public boolean contains(String word) {
        return words.contains(word.toLowerCase());
    }

    // Method to get the size of the dictionary
    public int size() {
        return words.size();
    }

    public static void main(String[] args) {
        Dictionary dictionary = new Dictionary();
        dictionary.addWord("hello");
        dictionary.addWord("world");
        
        System.out.println("Contains 'hello': " + dictionary.contains("hello")); // true
        System.out.println("Contains 'java': " + dictionary.contains("java")); // false
        System.out.println("Size of dictionary: " + dictionary.size()); // 2
    }
}

2. Using Trie

A Trie (prefix tree) is a more complex data structure that is particularly useful for storing a large number of strings and allows for efficient prefix searches.

class TrieNode {
    TrieNode[] children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new TrieNode[26]; // Assuming only lowercase a-z
        isEndOfWord = false;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Method to add a word to the Trie
    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toLowerCase().toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    // Method to check if a word exists in the Trie
    public boolean contains(String word) {
        TrieNode node = root;
        for (char c : word.toLowerCase().toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.addWord("hello");
        trie.addWord("world");
        
        System.out.println("Contains 'hello': " + trie.contains("hello")); // true
        System.out.println("Contains 'java': " + trie.contains("java")); // false
    }
}

Summary

• The HashSet implementation is straightforward and provides O(1) average time complexity for insertions and lookups.
• The Trie implementation is more complex but allows for efficient prefix searches and can be more memory-efficient for large datasets with many common prefixes.

You can choose either implementation based on your specific requirements, such as the need for prefix searching or memory constraints.