Dictionary lookup using hash tables

Dictionary is an abstract data type composed of a collection of keys and values. The Dictionary does not take duplicate keys and must write to handle collisions that occur when two keys are mapped to same index.

Write a program to look up the item from the hash tables. Value can be duplicated and keys should not duplicate.

source Code

package com.dsacode.Algorithm.search;
 
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;
 
public class DictionaryLookup {
 
    public static void main(String[] args)  {
 
        Set < String > dictionary = new HashSet < String >();
 
        dictionary.add("Hello");
        dictionary.add("HelloWorld");
        dictionary.add("Hellosiva");
        dictionary.add("Hello");
        dictionary.add("Helo");
        dictionary.add("Hllo");
 
        System.out.print("Items in the dictionary: [");
        for (String s : dictionary) {
            System.out.print(s+",");
        }
        System.out.print("]\n");
         
        String input = "Hello";
 
        List < List < String > > results = new ArrayList < List < String > >();
 
        System.out.print("Search 'Hello' string from the dictionary: ");
        search(input, dictionary, new Stack < String >(), results);
 
        for (List < String > result : results) {
            for (String word : result) {
                System.out.print(word + " ");
            }
            System.out.println("(" + result.size() + " words)");
        }
        System.out.println();
 
    }
 
    public static void search(String input, Set < String > dictionary,
            Stack < String > words, List < List < String > > results) {
 
        for (int i = 0; i < input.length(); i++) {
 
            String substring = input.substring(0, i + 1);
 
            if (dictionary.contains(substring)) {
                words.push(substring);
                if (i == input.length() - 1) {
                    results.add(new ArrayList < String >(words));
                } else {
                    search(input.substring(i + 1), dictionary, words, results);
                }
 
                words.pop();
            }
        }
    }
}

Output

Items in the dictionary: [Helo,Hello,Hllo,Hellosiva,HelloWorld,]
Search 'Hello' string from the dictionary: Hello (1 words)

Algorithm Explanation

	The predefined dictionary has set of words.
	Take user input and split the string into tokens.
	Search a dictionary for the words in the key string. If it matches, add to the result.

Time Complexity

Reference

1. https://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK3/NODE129.HTM
2. http://en.wikipedia.org/wiki/Associative_array