[SOLUCIONADO] TablaHash y sus pasos

[detective_jd]

Este tema es una continuación de este tema como consejo de CalgaryCorpus.

Pongo el código subido:

https://github.com/detectivejd/HashS.../hashsetsimple

En fín la situación es esta:

Mis dudas están con los métodos extras como containsAll que verifica si el set tiene todos los elementos de una coleccion, si no tiene uno devuelve falso.
el retainAll que conserva los elementos comúnes pero borra los otros y el removeAll borra todos los elementos de una colección, y la pregunta es:
¿para que los quiero? ¿porque las interfaces List y Set los tienen? ¿no era más fácil que las estructuras list y set no implementaran Collection? xq tiene las mismas
firmas Collection, además parece que el que creo parte del lenguaje tenía fascinación por las matemáticas digo por lo de conjuntos, intersecciones y demás.

Con respecto a errores me dice esto:

java.lang.Exception
at hashsetsimple.Test.comprobar_que(Test.java:6)
at hashsetsimple.ConstructorTest.creando_set_con_capa cidad_de_dos_elementos(ConstructorTest.java:25)
at hashsetsimple.ConstructorTest.test(ConstructorTest .java:70)
at hashsetsimple.Cuerpo.main(Cuerpo.java:7)

Lo más curioso es que en vez de guardarme 7 elementos me guarda 6, no quiero pensar que el error esta en la función hash, no sé que se te ocurre xq lo demás no da error alguno.

Espero sus respuestas y saludos.

[CalgaryCorpus]

Las preguntas que haces al inicio no tienen que ver con Java, sino con estructuras de datos. Lista y Set son ambas colecciones de elementos, pero el set tiene caracteristicas que la lista no, y viceversa. En un set los elementos no estan repetidos, no existe orden necesariamente. Un set o conjunto, es un conjunto si cumple propiedades matematicas, sino el nombre no calzaria. Se definen operaciones sobre los conjuntos, union, interseccion, etc. Sugiero leas respecto a las estructuras de datos que quieres implementar, no ponerte a implementar sin entenderlas.

No mire' todo exhaustivamente, eso lo tienes que hacer tu, pero lo que mire es que la interseccion claramente esta mal, a menos que sea yo el que entienda mal lo que escribiste. Al leer el codigo pense', como puedes borrar de un conjunto un elemento que NO esta en ese conjunto? Eso es lo que dice tu codigo.

Haz un test que pruebe la interseccion matematicamente: dados 2 conjuntos con elementos comunes, la interseccion deberia obtener los elementos comunes, tienes una prueba asi? estas comprobando que la interseccion efectivamente obtiene los elementos comunes de los 2 conjuntos involucrados?

Lo mismo con todos los tests, haz las pruebas matematicas de conjuntos. No pruebes solamente que tus metodos se ejecutan, sino que los resultados tengan sentido matematico.

Los sets te daran muchas oportunidades de probar otras cosas, por ejemplo hacer interseccion o union de un conjunto sobre si mismo.

S interseccion S => S
S union S => S

O hacer interseccion o union con el conjunto vacio, interseccion de 2 conjuntos disjuntos, interseccion e union de conjunto vacio, etc.

Si tienes una excepcion, revisa por que ocurre, que es lo que estas haciendo o dejando de hacer que, por ejemplo, accedes a una referencia invalida.

Suerte.

[detective_jd]

Hola CalgaryCorpus, mira que hice las siguientes cosas:

No mire' todo exhaustivamente, eso lo tienes que hacer tu, pero lo que mire es que la interseccion claramente esta mal, a menos que sea yo el que entienda mal lo que escribiste. Al leer el codigo pense', como puedes borrar de un conjunto un elemento que NO esta en ese conjunto? Eso es lo que dice tu codigo.

Eso esta corregido, el removeAll y el retainAll lo arreglé, no tenía muy claro lo que hacía xq eran nuevos para mí.

Haz un test que pruebe la interseccion matematicamente: dados 2 conjuntos con elementos comunes, la interseccion deberia obtener los elementos comunes, tienes una prueba asi? estas comprobando que la interseccion efectivamente obtiene los elementos comunes de los 2 conjuntos involucrados?

Lo mismo con todos los tests, haz las pruebas matematicas de conjuntos. No pruebes solamente que tus metodos se ejecutan, sino que los resultados tengan sentido matematico.

Los sets te daran muchas oportunidades de probar otras cosas, por ejemplo hacer interseccion o union de un conjunto sobre si mismo.

S interseccion S => S
S union S => S

O hacer interseccion o union con el conjunto vacio, interseccion de 2 conjuntos disjuntos, interseccion e union de conjunto vacio, etc.

La verdad esos no los tenía pero puse los test de intersección, diferencia, subconjunto, unión. Sólo que el de la unión normal no anda por la función hash que me saca un elemento existente para agregar uno de la colección.

¿Recuerdas el problema de la capacidad? lo resolví cambiando:

de esto:

Código Java:

if(size >= table.length * 3/4){
 

a esto:

Código Java:

if(size >= table.length * 1/2){
 

pero en vista al fallo de ahora que parece que es el mismo problema parece que hay algo que le falta al HashMap (MyMap.java) pero no sé que le falta.

Las preguntas que haces al inicio no tienen que ver con Java, sino con estructuras de datos. Lista y Set son ambas colecciones de elementos, pero el set tiene caracteristicas que la lista no, y viceversa. En un set los elementos no estan repetidos, no existe orden necesariamente. Un set o conjunto, es un conjunto si cumple propiedades matematicas, sino el nombre no calzaria. Se definen operaciones sobre los conjuntos, union, interseccion, etc. Sugiero leas respecto a las estructuras de datos que quieres implementar, no ponerte a implementar sin entenderlas.

Se que las listas se manejan con posiciones para todas sus funcionalidades y que puedes ordenar sus datos, y que con los conjuntos (set) evitan los duplicados de datos, eso lo sabía, lo que me llamaba la atención que las firmas de sus funcionalidades sean las mismas en sus respectivas interfaces pero al ver que heredan de Collection me debo callar la boca xq aplican lo que llamamos principio de dependencia "una entidad de alto nivel no debe depender de otra de bajo nivel, sino de intermediarias".

Pero lo del problema de la función hash me preocupa.

Aquí pongo el repositorio del código:

https://github.com/detectivejd/HashS.../hashsetsimple

Espero sus respuestas y Saludos.

[CalgaryCorpus]

Si no eres capaz de darte cuenta por tus tests que es lo que falla, estas en un estado de perplejidad que no sabes que es lo que ocurre, etc. tienes que meditar respecto a los tests que estas haciendo.
- no estas haciendo suficientes tests

los test que si' estas haciendo
- estan malos o
- estan incompletos o
- prueban aquello que no te sirve.

Mirando alguno de ellos, se ve inmediatamente la fragilidad que ellos tienen.
Me refiero a que si la implementacion estuviera mala (como lo esta') algunos de tus tests igual pasarian y no se reportaria error. Tu necesitas hacer que los tests fallen cuando la implementacion este mala.

Imaginate que tu set modificara los datos y en vez de realmente mantener un set, hiciera una copia de un elemento cualquiera, inventado.
Por ejemplo, yo inserto 3, 4,5 en el set, y este guardara, dentro 1, 1, 1. (3 veces el numero 1). Cuantos de tus tests pasarian sin reportar error?
Ok, olvidate de eso, pero solo por un rato, imaginate que esto no fuera al insertar, sino al hacer las otras operaciones, cuando intersectas, o haces union, el hashmap se vuelve loco y se pone a repetir cosas e ignora la entrada. Cuantos de tus tests pasarian sin reportar error?

No lo tomes literalmente, tal vez no es lo que te esta' ocurriendo, tu Hashmap no esta repitiendo nada, o eso creo. Solo te lo doy como ejemplo para que analices tus tests y veas que ellos son fragils y lo que prueban no sirve.
A veces te conviene cambiar la implementacion de lo que tienes, a proposito, para ver si tus tests se dan cuenta de lo malo que hay detras, en este caso, dado que tus tests son malos, tu no te das cuenta de la implementacion mala porque ellos pasan sin reportar la mala implementacion.

Una vez que tengas la confianza que tus tests no son fragiles, es momento de ver cuales en particular fallan, y cuando ellos son solo algunos, es momento de depurar, pero parte arreglando los tests. Ellos te daran mas informacion una vez que esten bien escritos.

[detective_jd]

Hola CalgaryCorpus estuve viendo el error y el problema está con las malditas colisiones, y la solución está en lo que algunos llaman separate chaining.
Pero cómo lo implemento??

Código Java:

@Override
    public V put(K key, V value) {
        if(key != null){
            int hash = hash(key,table.length);
            for(Entry<K,V> e = table[hash]; e != null; e = e.next){
                if(e.getKey().equals(key)){
                    V oldValue = e.getValue();
                    e.setValue(value);
                    return oldValue;
                }                
            }
            this.addEntry(key, value);
            return value;                     
        } else {
            return null;
        }
    }
    private void addEntry(K key, V value){
        if(size >= table.length * 1/2){
            Entry<K,V>[] tmp = table;
            size = 0;
            table = Arrays.copyOf(table, table.length * 2);
            for(int i = 0; i < table.length; i++){
                table[i] = null;
            }
            for (Entry<K, V> e : tmp) {     
                if(e != null){
                    put(e.getKey(),e.getValue());
                }
            }            
        }
        int hash = hash(key,table.length);
        table[hash] = new Entry(key, value,table[hash]);
        size++;
    }
 

Porque así tengo para agregar entradas al array, pero ¿cómo rayos implemento el separate chaning? porque con eso resuelvo ese problema.

Espero sus respuestas y saludos.

[CalgaryCorpus]

Mejora tus tests.

[detective_jd]

Hola CalgaryCorpus en base al test de los Set es que me dí cuenta del problema de las colisiones, pero estoy casi con el problema resuelto:

Código Java:

private void addEntry(K key, V value){
        if(size >= table.length * 0.75){
            Entry<K,V>[] tmp = table;
            size = 0;
            table = Arrays.copyOf(table, table.length * 2);
            for(int i = 0; i < table.length; i++){
                table[i] = null;
            }
            for (Entry<K, V> e : tmp) {     
                if(e != null){
                    put(e.getKey(),e.getValue());
                }
            }            
        }
        int hash = hash(key,table.length);
        Entry<K,V> et = new Entry(key, value,table[hash]);
        if(table[hash] == null){
            table[hash] = et;
        } else {
            for (Entry e = table[hash]; e != null; e = e.next) {
                 // sólo necesito obtener la última entrada y así reemplazo el siguiente del último por la entrada nueva
            }
        }
        size++;
    }
 

Sólo queda eso para resolver lo de las colisiones, creo.

Por otro lado, dices esto:

Mejora tus tests.

No me doy cuenta que debo mejorar de los test, sinceramente no se me ocurre un test más o que mejora hacer.

Espero sus respuestas y saludos.

[CalgaryCorpus]

Revisa mi post anterior, tus tests estan (o estaban?) malos. Mejoralos.

[detective_jd]

Hola CalgaryCorpus los test que he hecho comprobaban los casos favorables es decir cuando funcionan xq cuando no te tira una excepción, depuré el código y estos fueron los errores con los que me encontré:

debug:
java.lang.Exception
at hashsetsimple.test.Test.comprobar_que(Test.java:6)
at hashsetsimple.test.ConstructorTest.creando_set_con _capacidad_de_dos_elementos(ConstructorTest.java:2 9)
at hashsetsimple.test.ConstructorTest.test(Constructo rTest.java:74)
at hashsetsimple.interfaz.Cuerpo.main(Cuerpo.java:10)
java.lang.Exception
at hashsetsimple.test.Test.comprobar_que(Test.java:6)
at hashsetsimple.test.UnionTest.probando_union_normal (UnionTest.java:30)
at hashsetsimple.test.UnionTest.test(UnionTest.java:6 2)
at hashsetsimple.interfaz.Cuerpo.main(Cuerpo.java:20)
BUILD SUCCESSFUL (total time: 33 seconds)

Y adivina ¿dónde está la falla? en que cuando la función hash me calcula el índice hacía uno que ya existe me reemplaza el contenido actual por el nuevo (malditas colisiones) pero también me borra un elemento existente sin invocar el remove.

Por cierto intenté obtener la última entrada del índice con una función privada para luego en addEntry preguntar con un if sí era el último, no funcionaba, intenté con esto ahora:

Código Java:

private void addEntry(K key, V value){
        if(size >= table.length * 0.75){
            Entry<K,V>[] tmp = table;
            size = 0;
            table = Arrays.copyOf(table, table.length * 2);
            for(int i = 0; i < table.length; i++){
                table[i] = null;
            }
            for (Entry<K, V> e : tmp) {     
                if(e != null){
                    put(e.getKey(),e.getValue());
                }
            }            
        }
        int hash = hash(key,table.length);
        Entry<K,V> et = new Entry(key, value,table[hash]);
        if(table[hash] == null){
            table[hash] = et;
        } else {
            Entry<K,V> l = this.getLast(hash);
            for (Entry e = table[hash]; e != null; e = e.next) {
                if(l == e){
                    e.next = et;
                    break;
                }
            }
        }
        size++;
    }
    private Entry<K,V> getLast(int hash){
        Entry<K,V> l = null;
        for (Entry e = table[hash]; e != null; e = e.next) {
            l = e;
        }
        return l;
    }
 

Este código tiene sentido para tí o es una locura enorme??

Dejé más organizado el código: https://github.com/detectivejd/HashS.../hashsetsimple

Espero sus respuestas y saludos.

[CalgaryCorpus]

Comantario general: Un hash DEBE manejar colisiones. No es algo raro, una excepcion, una cosa que no ocurre, algo raro, algo maldito. Al reves, es algo comun, predecible, esperable, normal, etc. Tus implementacion y tus tests tienen que considerarlas. Si no funcionan, mejoralo y (lo habia mencionado?) mejora tus tests.

Es 3ra vez que te digo que mejores tus tests y no parece haber ninguna evidencia que lo hagas. Sigo viendo los mismos problemas en tus tests: ante una mala implementacion, (algunos de) tus tests pasaran igual.

Como puedes confiar en tests que ante una mala implementacion igual pasaran?

Es posible que ahora algunos tests fallen y te sirvan para darte cuenta de algunos problemas, pero ... una vez que aquello que ahora falla este' bien y tus tests pasen, tu creeras que por fin lo has logrado, pero con los tests actuales si existen problemas, tus tests igual pasaran. Lee otra vez lo que ya escribi y revisa detenidamente lo que ahi digo, e intenta ver que problema hay en tus tests que hacen que ellos reportan que todo esta bien incluso cuando no esta bien todo.

Ultima vez que te lo digo antes de desaparecer para ver si tomas en cuenta lo que te digo: mejora tus tests.

[detective_jd]

Hola CalgaryCorpus tienes razón al molestarte por mi necedad, porque que mi código apesta (lo digo yo) es cierto xq no sé cómo manejar lo de las colisiones que es con lo que me estoy golpeando bastante, ya que la única referencia que tengo para enfrentarlo es este link.

Por otro lado es verdad que no sé me ocurre cómo mejorar mis test al igual que mi implementación sacando lo de las colisiones, recuerdo que en el otro post de TablaHash me diste una lista de que cosas mejorar: https://goo.gl/9Unp4p, porque de esa forma me daré cuenta que cambiar o sacar del código, es más digo que luego de solucionar lo de las colisiones tendría que ver remove para borrar la entrada colisionada, pero eso es una suposición que hago, que me puedo equivocar.

No te enojes conmigo por este mensaje, pero es lo que me pasa.

Espero sus respuestas y saludos.

[detective_jd]

Hola a todos, finalmente pude con el problema de las colisiones, era de esto:

Código Java:

@Override
    public V put(K key, V value) {
        if(key != null){
            int hash = hash(key,table.length);
            for(Entry<K,V> e = table[hash]; e != null; e = e.next){
                if(e.getKey().equals(key)){
                    V oldValue = e.getValue();
                    e.setValue(value);
                    return oldValue;
                }                
            }
            this.addEntry(key, value);
            return value;                     
        } else {
            return null;
        }
    }
 

a esto, tuve que agregar otro if para lo de las colisiones:

Código Java:

@Override
    public V put(K key, V value) {
        if(key != null){
            int hash = hash(key,table.length);
            for(Entry<K,V> e = table[hash]; e != null; e = e.next){
                if(e.getKey().equals(key)){
                    V oldValue = e.getValue();
                    e.setValue(value);
                    return oldValue;
                } else if(e.next == null){
                    e.next = new Entry(key,value);
                    size++;
                    return value;
                }                
            }
            this.addEntry(key, value);
            return value;                     
        } else {
            return null;
        }
    }
 

Ahora bien, seguiré haciendo pruebas a parte de las subidas en github, por lo que pido nuevamente que si ven que hay que mejorar del código y de los test que me lo escriban, así podré darle al clavo.

https://github.com/detectivejd/HashS.../hashsetsimple

https://github.com/detectivejd/HassM.../hashmapsimple

Espero sus respuestas y saludos.

[detective_jd]

También me había olvidado decir que para que lo de las colisiones ande, tenía que cambiar mi clase interna entry cosa que el next de la entrada sea null xq de lo contrario no iba a funcionar

Código Java:

class Entry<K,V> implements Map.Entry<K,V>{
        final K key;
        V value;
        Entry<K,V> next;
        public Entry(K xkey, V xvalue) {
            this.key = xkey;
            this.value = xvalue;
            this.next = null;
        }        
        @Override
        public K getKey() {
            return key;
        }
        @Override
        public V getValue() {
            return value;
        }
        @Override
        public V setValue(V v) {
            V val = value;
            value = v;
            return val;
        }        
    }
 

Nuevamente digo y pido si pueden mandarme por este post o como mensaje privado, los bugs, mejoras en el código o test xq si me dicen exactamente que falla o falta lo pongo.

Espero sus respuestas y saludos.

[detective_jd]

Hola a todos, en estos días no me anduve debido a que andaba con gripe y no me sentía bien cómo para andar programando, pero ahora estoy bien como para seguir.

Estuve haciendo una pequeña prueba y me ví que con las claves númericas no me genera colisiones:

0:
1: (1)
2: (2)
3: (3)
4: (4)
5: (5)
6: (6)
7: (7)
8: (8)
9: (9)
10: (10)
11: (11)
12: (12)
13: (13)
14: (14)
15: (15)
16: (16)
17: (17)
18: (18)
19: (19)
20: (20)
21: (21)
22: (22)
23: (23)
24: (24)
25: (25)
26: (26)
27: (27)
28: (28)
29: (29)
30: (30)
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:

pero cuando las claves son string, aunque parezca mentira si genera colisiones:

0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11: (Satoshi)
12: (Gaurav)
13:
14:
15: (Awadh)
16: (Rahul) (P)
17: (Q)
18: (R)
19: (Luis) (S)
20: (Santiago) (T)
21: (U)
22: (V)
23: (Richard) (W)
24: (Serena) (X)
25: (Y)
26: (Z)
27:
28:
29:
30: (Ada)
31: (Lidia)

Les pregunto: ¿Que debería mejorar en el código y/o en los test? hace semanas que no toco nada jeje

Código de HashSet Casero

Código de HashMap Casero

Espero sus respuestas y saludos.

[detective_jd]

Hola a todos, cómo están? espero que bien. En vista que no tuve ninguna respuesta o critica del código, comencé a desarrollar el código de LinkedHashMap casero, pero no estoy muy inspirado que digamos, no sé si estoy bien encaminado o no en el asunto.

Pongo el código:

Código Java:

package linkedmapsimple;
import java.util.Map;
public class MyLinkedMap<K,V> extends MyMap<K,V>
{
    private Entry<K,V>header;
    private boolean accessOrder;
    public MyLinkedMap() {
        super();
        accessOrder = false;
    }
 
    public MyLinkedMap(int xcap) {
        super(xcap);
        accessOrder = false;
    }
 
    public MyLinkedMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }
    
    @Override
    public void clear() {
        super.clear();
        header.before = header.after = header;
    }
    @Override
    public boolean containsValue(Object value) {
        // Overridden to take advantage of faster iterator        
        if (value==null) {
            for (Entry e = header.after; e != header; e = e.after)
                if (e.value==null)
                    return true;
        } else {
            for (Entry e = header.after; e != header; e = e.after)
                if (value.equals(e.value))
                    return true;
        }
        return false;
    }
    private void addEntry(K key, V value){
        
    }
    class Entry<K,V> extends MyMap.Entry {
        Entry<K,V> before;
        Entry<K,V> after;
        public Entry(K xkey, V xvalue) {
            super(xkey, xvalue);
        }
        private void remove() {
            before.after = after;
            after.before = before;
        }
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }
    }
}
 

En especial con el addEntry teniendo en cuenta mi código del HashMap.

Código del HashMap Casero

Espero sus respuestas y Saludos.

PD: Para aclarar, no estoy en plan de "háganme el código" porque esa no es la idea para nada.

[detective_jd]

Hola a todos, les comento que acabo de subir el repositorio con el código del LinkedHashMap a github, aprovecho a pedir una mano con respecto de si hay una falla o detalle a poner del código, además de los test que pueden faltar o mejorar.

Código del LinkedHashMap Casero

Código del HashMap Casero

Espero sus respuestas y Saludos.

[detective_jd]

Hola a todos, empecé a hacer el LinkedHashSet casero, y esta hecho:

Código Java:

package linkedsetsimplev1;
import java.util.Collection;
public class MyLinkedSet<E> extends MySet<E>
{
    public MyLinkedSet() {
        super(4,true);
    }
    public MyLinkedSet(int xcap) {
        super(xcap,true);
    }
    public MyLinkedSet(Collection<? extends E> c) {
        super(c.size(),true);
        addAll(c);
    } 
}
 

A lo que tuve que hacer mejoras en MySet, MyMap y MyLinkedMap, pero estoy teniendo problemas con el iterator para que muestre el siguiente ya que tengo en las entradas, el que está antes y después pero también tengo el sgte:

Código Java:

public MyLinkedMap.Entry<K, V> nextNode() {
            MyLinkedMap.Entry<K, V> e = next;            
            current = e;
            next = e.after;
            return e;
}
 
static class Entry<K,V> extends MyMap.Entry {
        Entry<K,V> before = null;
        Entry<K,V> after = null;
        public Entry(K xkey, V xvalue) {
            super(xkey, xvalue);
        }
    }
 

En la consola me muestra esto:

run:
ORDEN NORMAL
Deborah
Tommy
Franco

ORDEN NINGUNO
Franco
Manuela
Tommy
Deborah
Denisse

esta es una prueba aparte que no la pondré en github pero en listado normal a partir de la 3era entrada no me muestra las otras por esto de las colisiones.

Esta es la prueba:

Código Java:

package linkedsetsimplev1;
public class Cuerpo 
{
    public static void main(String[] args) {
        MySet<String>set = new MyLinkedSet();
        set.add("Deborah");
        set.add("Tommy");
        set.add("Franco");
        set.add("Manuela");
        set.add("Miguel");
        set.add("Denisse");
        System.out.println("\t\tORDEN NORMAL");
        set.stream().forEach((s) -> {
            System.out.println(s);
        });
        System.out.println("");
        MyLinkedSet<String>set2 = new MyLinkedSet();
        set2.add("Franco");
        set2.add("Miguel");
        set2.add("Manuela");
        set2.add("Tommy");        
        set2.add("Deborah");
        set2.add("Denisse");
        System.out.println("\t\tORDEN NINGUNO");        
        set2.stream().forEach((s) -> {
            System.out.println(s);
        });
    }    
}
 

Y no sé me ocurre nada para arreglarlo, espero sus respuestas y saludos.

[detective_jd]

Buenas a todos, acá ando con lo siguiente: decidí cambiar un poco a MyLinkedMap y tuve que adaptar el código de MyMap, pero tengo este pequeño problema en la consola:

run:
--TEST NORMAL--
tamaño -> 4

--valores--
Deborah

Tomás

Franco

Deborah

Tomás

Franco

Manuela

--claves--
1

2

3

1

2

3

4

--entradas--
clave -> 1 valor -> Deborah

clave -> 2 valor -> Tomás

clave -> 3 valor -> Franco

clave -> 1 valor -> Deborah

clave -> 2 valor -> Tomás

clave -> 3 valor -> Franco

clave -> 4 valor -> Manuela

Lo raro es que tendría que aparecerme las entradas 1,2,3 y 4 y no repetidos, acá pongo el código cambiado de MyLinkedMap:

Código Java:

@Override
    protected void createEntry(K key, V value) {
        int hash = hash(key,table.length);
        Entry<K,V> e = new Entry(key, value);
        table[hash] = e;
        e.addBefore(head);
        size++;
    }
 
class Entry<K,V> extends MyMap.Entry {
        Entry<K,V> before, after;
        public Entry(K xkey, V xvalue) {
            super(xkey, xvalue);
        }
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }
 
        @Override
        void recordAccess(MyMap m) {
            MyLinkedMap<K,V> lm = (MyLinkedMap<K,V>)m;
            if (lm.accessOrder) {
                remove();
                addBefore((Entry<K, V>) lm.head);
            }
        }
        @Override
        void recordRemoval(MyMap m) {
            remove();
        }
        private void remove() {
            before.after = after;
            after.before = before;
        }
    }
 

Porque en MyMap tuve que adaptar el put, además de agregar el init al constructor para inicializar la cabecera en el Linked:

Código Java:

@Override
    public V put(K key, V value) {
        if(key != null){
            int hash = hash(key,table.length);
            for(Entry<K,V> e = table[hash]; e != null; e = e.next){
                if(e.getKey().equals(key)){
                    V oldValue = e.getValue();
                    e.setValue(value);
                    e.recordAccess(this);
                    return oldValue;
                } else if(e.next == null){
                    e.next = new Entry(key,value);
                    e.recordAccess(this);
                    size++;
                    return value;
                }                
            }
            this.addEntry(key, value);
            return value;                     
        } else {
            return null;
        }
    }
 

Me gustaría arreglar esto pero no sé me ocurre nada, espero sus respuestas y saludos.

[detective_jd]

Buenas a todos, al final solucioné el problema que tenía resulta que tenía que cambiar el addEntry de MyMap y arreglarlo a esto:

Código Java:

private void addEntry(K key, V value){
        if(size >= table.length * 0.75){
            Entry<K,V>[] tmp = table;
            table = Arrays.copyOf(table, table.length * 2);
            this.clear();
            for (Entry<K, V> e : tmp) {     
                if(e != null){
                    put(e.getKey(),e.getValue());
                }
            }            
        }
        this.createEntry(key,value);
    }
 

También actualice mis repositorios en github:

https://github.com/detectivejd/HassMap_casero

https://github.com/detectivejd/HashSet_casero

https://github.com/detectivejd/LinkedHashMap_casero

Ahora veré si puedo completar el LinkedHashSet, si lo logro genial y lo pongo en este medio, si falta algún test o hay que hacerle alguna corrección por favor diganlo.

Espero sus respuestas y saludos.

[detective_jd]

Bueno, llegué al LinkedHashSet o bien MyLinkedSet, pero tengo el problema en las colisiones (en MyMap esta el lio de nuevo :( ) y el problema que tengo es que cuando llego ahí no puedo listar los siguientes datos:

Código Java:

@Override
    public V put(K key, V value) {
        if(key != null){
            int hash = hash(key,table.length);
            for(Entry<K,V> e = table[hash]; e != null; e = e.next){
                if(e.getKey().equals(key)){
                    V oldValue = e.getValue();
                    e.setValue(value);
                    e.recordAccess(this);
                    return oldValue;
                } else if(e.next == null){ // este else if es el que me complica
                    e.next = new Entry(key,value);
                    e.recordAccess(this); // -> ¿pero cómo resuelvo esto?
                    size++;
                    return value;
                }                
            }
            this.addEntry(key, value);
            return value;                     
        } else {
            return null;
        }
    }
 

y otra vez la clave está en MyMap y MyLinkedMap que ya los puse en el código, digo esto xq Mi Set Enlazado tiene esto de código:

Código Java:

package linkedsetsimplev1;
import java.util.Collection;
public class MyLinkedSet<E> extends MySet<E>
{
    public MyLinkedSet() {
        super(4,true);
    }
    public MyLinkedSet(int xcap) {
        super(xcap,true);
    }
    public MyLinkedSet(Collection<? extends E> c) {
        super(c.size(),true);
        addAll(c);
    } 
}
 

Porque lo único nuevo q tiene MySet es este constructor que MyLinkedSet usa:

Código Java:

MySet(int xcap, boolean dummy) {
        map = new MyLinkedMap(xcap);
    }
 

Y les pregunto que ideas me dan para arreglar esto????

Espero sus respuestas y Saludos.

[detective_jd]

Buenas a todos, solucioné un poco el código y el primer listado me anda bien pero el segundo no debido por las colisiones, quedando de esta forma:

ORDEN NORMAL
Deborah
Tommy
Franco
Manuela
Miguel
Denisse

ORDEN NINGUNO
Franco
Manuela
Tommy
Deborah
Denisse

Había cambiado en Entry el poner una función llamada chain para las colisiones cosa que el Entry de MyLinkedMap solo cambie su implementación, pongo el repositorio en github para ver si dan alguna idea de que cambiar porque no se me ocurre nada.

https://github.com/detectivejd/Linke...kedsetsimplev1

Espero sus respuestas y saludos.

[Fuzzylog]

Esto lo has corregido?

else if(e.next == null){ // este else if es el que me complica
e.next = new Entry(key,value);
e.recordAccess(this); // -> ¿pero cómo resuelvo esto?
size++;
return value;
}


llamas 2 veces a e.next...

[detective_jd]

Hola FuzzyLog gracias por responder, verás para que me muestre como lo hace ahora sí pero para cómo debería andar no.

En el put de MyMap.java sufrió algunos cambios como este:

Código Java:

public V put(K key, V value) {
        if(key != null){
            int hash = hash(key,table.length);           
            for(Entry<K,V> e = table[hash]; e != null; e = e.next){
                if(e.getKey().equals(key)){
                    V oldValue = e.getValue();
                    e.setValue(value);
                    e.recordAccess(this);
                    return oldValue;
                } else {
                    return e.chain(key, value);
                }                
            }
            this.addEntry(key, value);
            return value;                     
        } else {
            return null;
        }
    }
 

En la clase interna Entry de MyMap.java puse la función chain quedando de esta forma:

Código Java:

V chain(K key, V value){
            this.next = new Entry(key,value);
            size++;
            return value;
        }
 

Cosa que en Entry de MyLinkedMap.java lo pueda redefinir de esta forma:

Código Java:

@Override
        Object chain(Object key, Object value) {
            this.next = new Entry(key,value);
            ((MyLinkedMap.Entry)this.next).addBefore(head);            
            size++;
            return value;
        }
 

pero en el método main no lista los datos por órden de inserción:

Código Java:

public static void main(String[] args) {
        MySet<String>set = new MyLinkedSet();
        set.add("Deborah");
        set.add("Tommy");
        set.add("Franco");
        set.add("Manuela");
        set.add("Miguel");
        set.add("Denisse");
        System.out.println("\t\tORDEN NORMAL");
        set.stream().forEach((s) -> {
            System.out.println(s);
        });
        System.out.println("");
        MyLinkedSet<String>set2 = new MyLinkedSet();
        set2.add("Franco");
        set2.add("Miguel"); // -> aqui tengo los problemas
        set2.add("Manuela");
        set2.add("Tommy");        
        set2.add("Deborah");
        set2.add("Denisse");
        System.out.println("\t\tORDEN NINGUNO");        
        set2.stream().forEach((s) -> {
            System.out.println(s);
        });
    }
 

Pero tengo problemas con las colisiones, sé que me falta algo para que me ande bien el MyLinkedMap y MyLinkedSet, el código lo puse en github y no sé me ocurre nada para arreglarlo, si ven algo avisen por favor.

https://github.com/detectivejd/Linke...kedsetsimplev1

Espero sus respuestas y saludos.

[Fuzzylog]

A lo mejor tendrías que comprobar la futura cantidad de elementos a almacenar y en caso de que supere el máximo existente incrementar el tamaño del set y añadir el elemento.

En todo caso puedes hacer debug para ver dónde se te pierde el valor.

[detective_jd]

Hola FuzzyLog me sirvió muchísimo lo que me dijiste resulta que era ese el problema, así que hice este cambio:

Código Java:

protected void addEntry(K key, V value){
        if(size >= table.length * 0.75){
            Entry<K,V>[] tmp = table;
            table = Arrays.copyOf(table, table.length * 2);
            this.clear();
            for (Entry<K, V> e : tmp) {     
                if(e != null){
                    put(e.getKey(),e.getValue());
                    for(;e != null; e = e.next){ // -> puse este for para que también almacene las entradas por colisiones
                        put(e.getKey(),e.getValue());
                    }
                }
            } 
        }
        this.createEntry(key,value);
    }
 

Y funcionó:

run:
ORDEN NORMAL
Deborah
Tommy
Franco
Manuela
Miguel
Denisse

ORDEN NINGUNO
Franco
Miguel
Manuela
Tommy
Deborah
Denisse

Ya lo subí a github: enlace

Puede que le ponga los test que tengo hasta para ver que tal. Saludos y gracias.

[CalgaryCorpus]

En el codigo que pones, en la linea 7 se chequea si e es null, y solo se ejecuta lo que esta dentro del if si e no es null.

Por lo tanto la linea 8 se ejecuta. Esa linea no cambia el valor de e, por lo que e sigue siendo distinto de null.

En la linea 9 se vuelve a comparar, en la condicion de continuacion del ciclo for, si e no es null, sabemos que no es - sino no estariamos aqui -, y se vuelve a hacer en la linea 10, lo que se hizo justo antes, en la linea 8. Parece todo repetido.

Puesto que es lo mismo, sugiero eliminar la linea 8.

Al eliminarla, quedaria el ciclo for dentro del if, pero el if chequea lo mismo que el for, entonces el if se hace superfluo.

Resumen: Elimina el if y la primera instruccion de ese if, y quedate con el ciclo for solamente.

[detective_jd]

Hola a todos, CalgaryCorpus que bueno es verte de nuevo, mira hice lo que me dijiste:

Código Java:

protected void addEntry(K key, V value){
        if(size >= table.length * 0.75){
            Entry<K,V>[] tmp = table;
            table = Arrays.copyOf(table, table.length * 2);
            this.clear();
            for (Entry<K, V> e : tmp) {     
                for(;e != null; e = e.next){
                    put(e.getKey(),e.getValue());
                }
            } 
        }
        this.createEntry(key,value);
    }
 

Pero gracias a eso me dí cuenta que en algunos casos el código no ordena por inserción, los listados 1,2 y 4 andan pero el 3 no, y en el 3 me ordena hasta el 2do elemento que es la función reverse del test UpTest.java.

1
Deborah
Tommy
Franco
Manuela
Miguel
Denisse

2

3
Denisse
Franco
Miguel
Manuela
Deborah
Tommy

4
Deborah
Tommy
Franco
Manuela
Miguel
Denisse

Estos listados no los verás en el repositorio, pero sí la función que te dije y en dónde te dije, los Set son siempre los que me dan los problemas pero me pulen los Map.

En MyLinkedMap tengo el método init y addBefore de la clase Entry que es el que me da las ordenaciones por inserción.

Pongo el repositorio de LinkedSetSimple: https://goo.gl/g3hFwz

Espero sus respuestas y Saludos.

[CalgaryCorpus]

No entiendo lo que intentas probar.
Supongo que tus tests unitarios siguen malos.

Es mejor que recortes tus problemas en pequeños problemas que entregar un link a kilómetros de código para que alguien más los encuentre por ti.

Haz uno o varios tests que usen lo más básico de los tipos que estás definiendo, alguno(s) de ellos debería(n) fallar. Corrijelo (s). Haz que ese test sea parte de tus tests para que modificaciones futuras detecten errores en implementaciones de otras funcionalidades.

Publica en este foro dudas puntuales con código pequeño.
Crea varios posts con distintas dudas. Este post no termina nunca de la forma que lo has hecho.

[detective_jd]

Hola Calgary Corpus, te respondo por partes

No entiendo lo que intentas probar.

Verás gracias a tu otro comentario pude arreglar con los for, pero probando me dí cuenta que en ciertas ocasiones el LinkedHashSet casero (MyLinkedSet) no ordena por inserción de datos, en la función reverse de la clase UpTest.java porque los puse en la función en este órden:

"Denisse","Franco","Manuela","Deborah","Miguel","T ommy"

pero en la consola me muestra de esta forma:

Denisse
Franco
Miguel
Manuela
Deborah
Tommy

verás que el elemento 3, 4 y 5 no están ordenados por inserción eso es lo que quiero probar y arreglar. En la clase MyLinkedMap hereda de MyMap (como lo hace LinkedHashMap con HashMap) el método addBefore y
init son para el tema de las ordenaciones, ahí está mi problema.

Supongo que tus tests unitarios siguen malos.

Dame una idea de cómo cambiarlos porque así estuvimos que son malos, malos y más malos pero no sé ocurrió una forma de mejorarlos sinceramente, pensé más en las funcionalidades,

Es mejor que recortes tus problemas en pequeños problemas que entregar un link a kilómetros de código para que alguien más los encuentre por ti.

En estos momentos el problema a resolver está en el addBefore de la clase MyLinkedMap para que independiente de cómo pongas los datos, los órdenes por inserción.

Haz uno o varios tests que usen lo más básico de los tipos que estás definiendo, alguno(s) de ellos debería(n) fallar. Corrijelo (s). Haz que ese test sea parte de tus tests para que modificaciones futuras detecten errores en implementaciones de otras funcionalidades.

Cada clase del paquete linkedsetsimple.test es un test diferente, dame ideas para mejorarlos. Con respecto a:

Haz que ese test sea parte de tus tests para que modificaciones futuras detecten errores en implementaciones de otras funcionalidades.

Aparte de lo que hacen las estructuras de datos CRUD, no sé me ocurre otra implementación de otra funcionalidad, estas estructuras de hashing que estoy haciendo son para ver entender cómo funcionan los Hashing normales:

* HashMap
* HashSet - que delega todo de HashMap)

los Hashing enlazados, que estoy en los últimos detalles para terminarlos:

* LinkedHashMap - hereda de HashMap pero algunos métodos son redifinidos y cambian los iterators.
* LinkedHashSet - usa el 4to constructor de HashSet para usar en el Map una instancia de LinkedHashMap

y después de esto quiero intentar implementar TreeMap y TreeSet caseros, todo esto es una antesala de lo que quiero hacer pero para eso quiero entender bien los Hashing cómo se implementan y funcionan.

Pongo el repositorio, el que hay que mirar es MyMap,MyLinkedMap y MyLinkedSet, probar e ver en MyLinkedSet (en especial) el tema de las pruebas, supongo que no viste los últimos cambios de las estructuras.

https://goo.gl/g3hFwz

Espero sus respuestas y saludos

[CalgaryCorpus]

No voy a revisar el codigo por ti, a menos que presentes un subconjunto limitado, en un problema puntual, en otro post. Haz tu mismo lo necesario para descubrir lo que esta mal ahora. Asi aprenderas mas.

Aqui tienes una idea:
En vez de insertar 5 o 6 elementos, inserta 2 o 3, o lo que sea, pero que sea la minima cantidad de elementos para que el problema que ves ahora se reproduzca.
Haz un metodo que te permita espiar tus estructuras y espialas por cada insercion que hagas, luego revisa el metodo que usas para imprimir los datos. Tal vez tu estructura esta bien, pero cuando lo imprimes, la recorres mal. O no, tal vez tu insercion es incorrecta y tu impresion esta bien. O tal vez ambos procesos estan mal.

Una vez que compruebes que' estaba mal, haz un test unitario que falle en las condiciones actuales. Una vez corregido el problema, ese test deberia pasar, junto a todos los otros.

Si este proceso te conduce a corregir algo y aparece OTRO problema, usa la misma metodologia para descubrir tus propios problemas y haz post cortos.

Abandono este thread. Te veo en otro.

Suerte.