Implement dictionary using Java

Question

Task Dictionary ADT

• The dictionary ADT models a searchable collection of key-element entries
• Multiple items with the same key are allowed
• Applications: word-definition pairs

Dictionary ADT methods:

• find(k): if the dictionary has an entry with key k, returns it, else, returns null
• findAll(k): returns an iterator of all entries with key k
• insert(k, o): inserts and returns the entry (k, o)
• remove(e): remove the entry e from the dictionary
• size(), isEmpty()

Operation Output Dictionary

insert(5,A) (5,A) (5,A)
insert(7,B) (7,B) (5,A),(7,B)
insert(2,C) (2,C) (5,A),(7,B),(2,C)
insert(8,D) (8,D) (5,A),(7,B),(2,C),(8,D)
insert(2,E) (2,E) (5,A),(7,B),(2,C),(8,D),(2,E)
find(7) (7,B) (5,A),(7,B),(2,C),(8,D),(2,E)
find(4) null (5,A),(7,B),(2,C),(8,D),(2,E)
find(2) (2,C) (5,A),(7,B),(2,C),(8,D),(2,E)
findAll(2) (2,C),(2,E) (5,A),(7,B),(2,C),(8,D),(2,E)
size() 5 (5,A),(7,B),(2,C),(8,D),(2,E)
remove(find(5)) (5,A) (7,B),(2,C),(8,D),(2,E)
find(5) null (7,B),(2,C),(8,D),(2,E)

Detailed explanation: NO

Answer 1

Java already has a collection, which has almost all you need. You just need to add maybe one method. For starters explore java.util.Collection... classes. Then extend one to add required methods. If done properly, it's just a matter of few dozens lines.

For me, the easiest way to go is with Map<Object, Set<Object>>. The tricky thing is to return an iterator.

EDIT:

On the other hand I'd go with this Entry.java:

public class Entry<K, V> {

    K key;
    V value;

    public Entry(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K key() {
        return key;
    }

    public V value() {
        return value;
    }

    @Override
    public String toString() {
        return "(" + key + ", " + value + ")";
    }

    // Methods needed to correctly behave in containers like sets, hashmaps:
    // (I generated those automatically in NetBeans)
    @Override
    public boolean equals(Object obj) {
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Entry<K, V> other = (Entry<K, V>) obj;
        if (this.key != other.key && (this.key == null || !this.key.equals(other.key)))
            return false;
        if (this.value != other.value && (this.value == null || !this.value.equals(other.value)))
            return false;
        return true;
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 23 * hash + (this.key != null ? this.key.hashCode() : 0);
        hash = 23 * hash + (this.value != null ? this.value.hashCode() : 0);
        return hash;
    }
}

... also with this: Dictionary.java

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Dictionary<K, V> {

    private List<Entry<K, V>> set;

    public Dictionary() {
        this.set = new LinkedList<Entry<K, V>>();
    }

    /**
     * find(k): if the dictionary has an entry with key k, returns it, else, returns null
     */
    public Entry<K, V> find(K key) {
        // for all entries in set...
        //   check if key mathches
        //     - if it does than return it

        // else
        return null;
    }

    /**
     * findAll(k): returns an iterator of all entries with key k
     * @return
     */
    public Iterator<Entry<K, V>> findAll(K key) {
        // make a temporary list
        // for all entries in set...
        //   check if key matches
        //     - if it does than add it to temporary list

        // return the temporary list iterator (list.iterator())
        return null;
    }

    /**
     * insert(k, o): inserts and returns the entry (k, o)
     */
    public Entry<K, V> insert(K key, V value) {
        // obvious
        return null;
    }

    /**
     * remove(e): remove the entry e from the dictionary
     */
    public Entry<K, V> remove(Entry<K, V> entry) {
        return entry;
    }

    public int size() {
        return set.size();
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    @Override
    public String toString() {
        return set.toString();
    }
}

..., and this DictionaryTest.java:

public class DictionaryTest {

    static Dictionary<Integer, Character> dict = new Dictionary<Integer, Character>();

    public static void main(String[] args) {

        /*

        Test cases:

        1. insert(5,A) (5,A) (5,A)
        2. insert(7,B) (7,B) (5,A),(7,B)
        3. insert(2,C) (2,C) (5,A),(7,B),(2,C)
        4. insert(8,D) (8,D) (5,A),(7,B),(2,C),(8,D)
        5. insert(2,E) (2,E) (5,A),(7,B),(2,C),(8,D),(2,E)
        6. find(7) (7,B) (5,A),(7,B),(2,C),(8,D),(2,E)
        7. find(4) null (5,A),(7,B),(2,C),(8,D),(2,E)
        8. find(2) (2,C) (5,A),(7,B),(2,C),(8,D),(2,E)
        9. findAll(2) (2,C),(2,E) (5,A),(7,B),(2,C),(8,D),(2,E)
        10. size() 5 (5,A),(7,B),(2,C),(8,D),(2,E)
        11. remove(find(5)) (5,A) (7,B),(2,C),(8,D),(2,E)
        12. find(5) null (7,B),(2,C),(8,D),(2,E)
         */

        // Test case #1:
        test("insert(5,A)", dict.insert(5, 'A'));

        // Test case #2:
        test("insert(7,B)", dict.insert(7, 'B'));

        // Test case #3:
        test("insert(2,C)", dict.insert(2, 'C'));

        // ...

        // Test case #6:
        test("find(7))", dict.find(7));

        // implement all and check them during implementation


    }

    private static void test(String string, Object result) {
        System.out.print(string + " ");
        System.out.print(result);
        System.out.println(" " + dict);
    }
}

Answer 2

I will suggest read up Hash tables with separate chaining. Hash tables is a good way to implement dictionaries. There are MIT lectures in the open course ware for this.See this http://en.wikipedia.org/wiki/Hash_table for more details