Use Dictionary with Java

Question

Task Dictionary ADT

• ADT Dictionary Models a Searchable Collection of Key Item Records
• Multiple items with the same key allowed
• Applications: word definition pairs

ADT Method Dictionary:

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

Operational 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 that has almost everything you need. You just need to add maybe one method. Start by exploring the java.util.Collection classes .... Then add one to add the required methods. If done correctly, these are just a few dozen lines.

For me, the easiest way is Map<Object, Set<Object>> . The hard thing is to return the iterator.

EDIT:

On the other hand, I would 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 suggest reading Hash tables with a separate chain. Hash tables are a good way to implement dictionaries. To do this, lecture MIT in an open tutorial. See http://en.wikipedia.org/wiki/Hash_table for details