Implementar diccionario utilizando Java

Question

Tarea Diccionario ADT

• Los modelos ADT diccionario de una colección de los registros de elementos clave
• artículos múltiples con la misma clave se permite
• Aplicaciones: pares de palabras definición

diccionario métodos ADT:

• find (k): si el diccionario tiene una entrada con clave k, lo devuelve, de lo contrario, devuelve un valor nulo
• findAll (k): devuelve un iterador de todas las entradas con la clave k
• inserción (K, O): inserciones y devuelve la entrada (k, o)
• remove (e): quitar la entrada e del diccionario
• size(), estaVacia()

Operación de salida Diccionario

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) 

Explicación detallada: NO

Answer 1

Java ya tiene una colección, que tiene casi todo lo que necesita. Solo necesitas agregar un método. Para empezar, explore java.util.Collection ... classes. Luego extiende uno para agregar los métodos requeridos. Si se hace correctamente, es solo cuestión de algunas docenas de líneas.

Para mí, la forma más fácil de hacerlo es con Map<Object, Set<Object>>. Lo complicado es devolver un iterador.

EDIT:

Por otro lado me gustaría ir con este 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; 
    } 
} 

... También con esto: 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(); 
    } 
} 

..., y esto 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

Sugeriré tablas hash de lectura con encadenamiento separado. Las tablas Hash son una buena forma de implementar diccionarios. Hay clases de MIT en el curso abierto ware para esto. Consulte esto http://en.wikipedia.org/wiki/Hash_table para más detalles