[SOLUCIONADO] Implementar TablaHash

[detective_jd]

Hola a todos, tengo una consulta que hacerles verán estoy viendo cómo implementar un HashMap y encontré una implementación bastante simplificada pero tengo problemas para agregar las entradas hash ya que no me guarda bien los elementos:

Código Java:

private int findEntry(Object key){
       // System.out.println("hashcode -> " + hash(key.hashCode()));
        int hash = (key == null) ? 0 : hash(key.hashCode());        
        int index =  hash & (table.length-1);
       // System.out.println("pase -> " + index);
        return index;
    }
static int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
private HashEntry<K,V> getEntry(Object key){
        HashEntry<K,V> e = table[findEntry(key)];
        return (e != null && key.equals(e.key)) ? e : null;
    }
public V put(K key, V value) {
        if(key == null){
            return null;
        }
        Entry<K,V> e = this.getEntry(key);    
        if(e != null){
            return table[findEntry(key)].setValue(value);            
        } else if(size == table.length){
            table = Arrays.copyOf(table, table.length +1);
        }
        table[findEntry(key)] = new HashEntry(key,value);
        size++;
        return null;
    }
/*-----------------------------------------------------------*/    
    protected class HashEntry<K,V> implements Entry<K,V> {
        protected K key;
        protected V value;
        public HashEntry(K k, V v) {
            key = k;
            value = v;
        }
        @Override
        public V getValue() {
            return value;
        }
        @Override
        public K getKey() {
            return key;
        }
        @Override
        public V setValue(V val) {
            V oldValue = value;
            value = val;
            return oldValue;
        }       
        @Override
        public int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }        
        @Override
        public boolean equals(Object obj) {
            if(obj instanceof HashEntry){
                HashEntry<K, V> ent = (HashEntry<K, V>) obj;
                return Objects.equals(key, ent.key) && Objects.equals(value, ent.value);
            } else {
                return false;
            }
        }
        @Override
        public String toString() {
            return "(key: " + key + ", value: " + value + ")";
        }
    }
 

Calculo que mi problema está en cómo tengo el hashCode y la función hash pero no le he encontrado la vuelta, por favor denme una mano con esto.

Espero sus respuestas y saludos.

[detective_jd]

Por favor, alguna ayuda con esto, comparto el código cuando lo tengamos terminado.
No es una estructura que está de cero sólo es arreglar detalles nada más.

Por favor, espero sus respuestas, Saludos.

[detective_jd]

Buenas a todos, estuve mirando el código que encontré y lo que me falla son los índices que me obtienen las funciones nunca me ponen en la posición 0 cuando se agregan por primera vez elementos de la tablahash:

Código Java:

public V put(K key, V value) {
        if(key == null){
            return null;
        } 
        int index = getIndex(key); // acá no me obtiene el índice correcto me obtiene cualquier cosa
        Pair<K, V> pair = table[index];
        if (pair != null && (pair.key == key ||  pair.key.equals(key))) {
            V oldValue = pair.value;
            pair.value = value;
            return oldValue;
        }
        setPair(key, value, index);        
        return value;
    }
// funcion para obtener el hashCode de la clave
    private int hashFunction(Object key) {  
        if (key == null)
            return 0;
        String str = key.toString();
        int summation = 0;
        for (int i = 0; i < str.length(); i++)
            summation += str.charAt(i);
        return summation;
    }
// función para obtener el índice
    private int getIndex(Object key) {
        int hash = hashFunction(key);
        return hash % capacity;
    }
    private void setPair(K key, V value, int index) {
        Pair<K, V> e = table[index];
        while (e != null) {
            index++;
            if (index >= capacity) {
                table = Arrays.copyOf(table, table.length +1);
                put(key,value);
                return;
            }
            e = table[index];
        }
        table[index] = new Pair<>(key, value);
        size++;
    }
 

El punto es que busqué en internet y no encontré una solución acorde a lo que quiero y lo peor es que usan de forma parecida para obtener los índices de los hash....

Por favor, alguna respuesta, la agradeceré.

[Tipdar]

Hola detective_jd, me pregunto ¿qué sentido tiene implementar un hash map si ya Java cuenta con esa estructura de datos y muy bien implementada por cierto?

[detective_jd]

Hola Tipdar en realidad tiene mucho sentido si te pones a pensar, empezando que la estructuras hechas en Java (por la gente de Oracle) son un poco rebuscadas de entender si es que te pusiste a ver y trataste de entender el código, ya que siendo así te habrás dado por medio del HashMap se crean las HashSet, LinkedMashMap y LinkedHashSet, y sería bueno entender cómo funcionan bien los HashMap y cómo implementarlos......

Por otro lado estoy creando una estructura de datos para paginación de registros, de hecho tengo una creada para el uso de las listas que anda, y quiero hacer otra estructura de paginación pero con Maps ya que la de Set se logrará mediante Map.

Ahora si quieres ayudarme bienvenido sea, de lo contrario te pediré que reserves tu opinión. Gracias

Espero sus respuestas y Saludos.

[detective_jd]

Les cuento que encontrando una función hashCode me solucionó un poco el problema:

private int getIndex(Object key) {
return (key.hashCode() & 0x7FFFFFFF) % table.length;
}

pero me dio este resultado:

indice -> 1
indice -> 2
indice -> 3
indice -> 4

cuando tendría que hacer esto:

indice -> 0
indice -> 1
indice -> 2
indice -> 3

No sé si cambiar o agregar cosas en la Pair

Código Java:

class Pair<K,V> {
        final K key;
        V value;
        Pair(K k, V v) {
            value = v;
            key = k;
        }
        public final K getKey() {
            return key;
        }
        public final V getValue() {
            return value;
        }
        @Override
        public String toString() {
            return getKey() + "=" + getValue();
        }
    }
 

o cambiar algo de los métodos para guardar la entrada en mi tablahash

Código Java:

public V put(K key, V value) {
        if(key == null){
            return null;
        } else {
            int index = getIndex(key);
            System.out.println("indice -> "+ index);
            Pair<K, V> pair = table[index];
            if (pair != null && (pair.key == key ||  pair.key.equals(key))) {
                V oldValue = pair.value;
                pair.value = value;
                return oldValue;
            }
            setPair(key, value, index);        
            return value;
        }
    }
private int getIndex(Object key) {
       return (key.hashCode() & 0x7FFFFFFF) % table.length;
    }
 
    private void setPair(K key, V value, int index) {
        Pair<K, V> e = table[index];
        while (e != null) {
            index++;
            if (index >= capacity) {
                table = Arrays.copyOf(table, table.length +1);
                put(key,value);
                return;
            }
            e = table[index];
        }
        table[index] = new Pair<>(key, value);
        size++;
    }
 

Espero sus respuestas y Saludos.

[Tipdar]

Siempre puedes redefinir métodos... cambiar el comportamiento, ya sabes.

[detective_jd]

Hola Tipdar verás la estructura está casi hecha tuve que hacer un truco medio chancho para continuar con el resto de las funcionalidades del HashMap casero:

Código Java:

private int getIndex(Object key) {
       return (key.hashCode() & 0x7FFFFFFF) % table.length -1;
    }
 

Tuve que restarle 1 para obtener el índice pero sé que eso no está bien, por otro lado cuando le pongo un tamaño por defecto y luego necesito agrandarlo me da este problema en la consola:

indice -> 0
indice -> 1
indice -> 2
indice -> -1
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1

Código Java:

public V put(K key, V value) {
        if(key == null){
            return null;
        } else {
            int index = getIndex(key);
            System.out.println("indice -> "+ index);
            Entry<K, V> pair = table[index];
            if (pair != null && pair.getKey().equals(key)) {
                V oldValue = pair.getValue();
                pair.setValue(value);
                return oldValue;
            }
            setEntry(key, value, index);
            return value;
        }
    }
private void setEntry(K key, V value, int index) {
        Entry<K, V> e = table[index];
        while (e != null) {
            index++;
            if (index >= capacity) {
                table = Arrays.copyOf(table, table.length +1);
                put(key,value);
                return;
            }
            e = table[index];
        }
        table[index] = new Entry(key, value);
        size++;
    }
 

El resto de la estructura está hecha, ya pongo el código por si a alguien le interesa:

https://pastebin.com/QywGK6g8

Creo que quedaría esa parte del código para decir está listo.

Espero sus respuestas y Saludos

[CalgaryCorpus]

Por que le restas 1?
La operacion modulo retorna valores entre 0 y el (numero-1), de modo que si le restas 1, te dara valores entre -1 y el numero-2, eso es lo que quieres? por que?

[detective_jd]

Hola CalgaryCorpus justamente eso es lo que no quiero, lo había hecho para continuar con el desarrollo del HashMap, pero ahora me veo en que necesito que me obtenga bien el índice sin la resta pero no me sale bien, no tengo un plan cómo para hacerlo andar.
Por otro lado también tengo problemas en caso de que por ejemplo: tengo dicho map de tamaño 4 por defecto pero me da error cuando quiero agregar en la posición 3 y no me deja.

Los que andan son put, getIndex, setEntry (provisorio de momento, xq cuando haga andar bien los otros 2, trataré de deshacerme de él).

Código Java:

@Override
    public V put(K key, V value) {
        if(key == null){
            return null;
        } else {
            int index = getIndex(key);
            System.out.println("indice -> "+ index);
            Entry<K, V> pair = table[index];
            if (pair != null && pair.getKey().equals(key)) {
                V oldValue = pair.getValue();
                pair.setValue(value);
                return oldValue;
            }
            setEntry(key, value, index);
            return value;
        }
    }
    private int getIndex(Object key) {
       return (key.hashCode() & 0x7FFFFFFF) % table.length;
    }
 
    private void setEntry(K key, V value, int index) {
        Entry<K, V> e = table[index];
        while (e != null) {
            index++;
            if (index >= capacity) {
                table = Arrays.copyOf(table, table.length +1);
                put(key,value);
                return;
            }
            e = table[index];
        }
        table[index] = new Entry(key, value);
        size++;
    }
 

Espero sus respuestas y Saludos.

[CalgaryCorpus]

Ahora me parece mas razonable, dado que usas el modulo tamano de la tabla.
Que es lo que no funciona?

Como estas haciendo para probar que tu HashMap funciona?
Tienes uno o varios tests que ejercitas cada vez que cambias tu implementacion?
Si tienes tests, seria bueno incluirlos y decir algo como el test 1 no funciona, pero el 2, 3 y 4 si.
O poner nombres a los tests que digan que es lo que estan tratando de probar. Idealmente 1 sola cosa.

[detective_jd]

Gracias por responder CalgaryCorpus, mira estoy probando de esta manera la estructura:

Código Java:

package hashmapsimple;
public class Cuerpo 
{
    public static void main(String[] args) {
        MyMap<Integer,String>col= new MyMap();
        col.put(1, "Deborah");
        col.put(2, "Tommy");
        col.put(3, "Franco");
        col.put(4, "Manuela");
        col.put(null,"pepe");
        /*
        java.util.HashMap<Integer, String> m = new java.util.HashMap();
        m.put(5, "Miguel");
        m.put(6, "Denisse");        
        col.putAll(m);
        */
        System.out.println(" ");
        System.out.println("con containsKey: " + col.containsKey(1));
        System.out.println("con containsKey: " + col.containsKey(7));
        System.out.println(" "); 
        System.out.println("con get: " + col.get(1)); 
        System.out.println("con get: " + col.get(7));
        System.out.println(" ");
        System.out.println("con containsValue: " + col.containsValue("Franco"));
        System.out.println("con containsValue: " + col.containsValue("Rodrigo"));
        System.out.println("con containsValue: " + col.containsValue(null));
        //col.remove(2);
        //col.remove(7);
        //col.clear();
        System.out.println(" "); 
        System.out.println("tamaño -> " + col.size());
        System.out.println(" ");
        System.out.println(" --valores-- ");
        col.values().stream().forEach((s) -> {
            System.out.println(s);
        });
        System.out.println(" ");
        System.out.println(" --claves-- ");
        col.keySet().stream().forEach((s) -> {
            System.out.println(s);
        });
        System.out.println(" ");
        System.out.println(" --entradas-- ");
        col.entrySet().stream().forEach((e)->{
            System.out.println("clave -> "+ e.getKey() +" valor -> "+e.getValue());
        });        
    }    
}
 

sin la resta me da esto por consola:

sólo el key.hashCode(): 1
esta expresión (key.hashCode() & 0x7FFFFFFF); 1
indice -> 1

sólo el key.hashCode(): 2
esta expresión (key.hashCode() & 0x7FFFFFFF): 2
indice -> 2

sólo el key.hashCode(): 3
esta expresión (key.hashCode() & 0x7FFFFFFF): 3
indice -> 3

sólo el key.hashCode(): 4
esta expresión (key.hashCode() & 0x7FFFFFFF): 4
indice -> 0

para ver internamente el getIndex() hice esto:

Código Java:

private int getIndex(Object key) {
        System.out.println("sólo el key.hashCode(): " + key.hashCode());
        System.out.println("esta expresión (key.hashCode() & 0x7FFFFFFF): " + (key.hashCode() & 0x7FFFFFFF));
        return (key.hashCode() & 0x7FFFFFFF) % table.length;
    }
 

Prácticamente la función getIndex no funciona y ahí es dónde debo replantear el asunto.

Espero sus respuestas y saludos.

[CalgaryCorpus]

Creo que la razon esta en como inicializas la tabla table, que no veo como se inicializa en el codigo que muestras. Si la estas inicializando de tamano X, hazlo, para comprobarlo, de tamano 10*x, y estimo que tu codigo se va a comportar bien. Si es asi, verifica que el tamano de la tabla crezca adecuadamente.

[detective_jd]

Gracias por responder CalgaryCorpus verás al "HashMap" casero lo inicializo de está forma:

Código Java:

public class MyMap<K, V> implements Map<K,V>{
    private int capacity;
    private int size;
    private static final int DEFAULT_SIZE = 4;
    private Entry<K,V>[] table;    
    public MyMap() {
        this(DEFAULT_SIZE);
    }
    public MyMap(int xcapacity) {
        if(xcapacity <= 0){
            throw new IllegalArgumentException("Capacidad no permitida: " + capacity);
        } else {
            this.capacity = xcapacity;        
        }
        this.clear();
    }
    public MyMap(Map<? extends K, ? extends V> m) {
        this.putAll(m);
    }
    @Override
    public void clear() {
        table = new Entry[capacity];
        size = 0;
    }
    .............................
}
 

Con respecto al tamaño si crece o no tengo este dilema:

Código Java:

public V put(K key, V value) {
        if(key == null){
            return null;
        } else {
            int index = getIndex(key); // aqui me da los dolores de cabeza xq me termina haciendo relajo en la última posición como viste en el anterior mensaje
            System.out.println("indice -> "+ index);
            Entry<K, V> pair = table[index];
            if (pair != null && pair.getKey().equals(key)) {
                V oldValue = pair.getValue();
                pair.setValue(value);
                return oldValue;
            }
            setEntry(key, value, index);
            return value;
        }
    }
 

Espero sus respuestas y saludos.

[CalgaryCorpus]

capacity lo inicializas y no lo actualizas cuando pides mas memoria. Eso esta mal, pues lo estas usando para controlar si tienes que pedir mas memoria o no.
Por que no pides memoria para 1 mas que capacity inicialmente, y si pides mas memoria luego duplicas cada vez en vez de aumentar en 1?

[detective_jd]

Hola CalgaryCorpus cambié un poquito el código para simplificarlo:

Código Java:

@Override
    public V put(K key, V value) {
        if(key == null){
            return null;
        } else {
            int index = getIndex(key);
            System.out.println("indice -> "+ index);
            Entry<K, V> pair = table[index];
            if (pair != null && pair.getKey().equals(key)) {
                V oldValue = pair.getValue();
                pair.setValue(value);
                return oldValue;
            }
            if(size == table.length){
                table = Arrays.copyOf(table, table.length +1);
            }
            table[index] = new Entry(key, value);
            size++;
            return value;
        }
    }    
    private int getIndex(Object key) {
        return (key.hashCode() & 0x7FFFFFFF) % table.length;
    }
 

Estuve pensando en lo que me dijiste pero no le doy al clavo, te pongo la parte donde inicia, y todo xq no me encuentra el índice para posicionarlo en el array:

Código Java:

private int capacity;
    private int size;
    private static final int DEFAULT_SIZE = 4;
    private Entry<K,V>[] table;    
    public MyMap() {
        this(DEFAULT_SIZE);
    }
    public MyMap(int xcapacity) {
        if(xcapacity <= 0){
            throw new IllegalArgumentException("Capacidad no permitida: " + capacity);
        } else {
            this.capacity = xcapacity;        
        }
        this.clear();
    }
    public MyMap(Map<? extends K, ? extends V> m) {
        this.putAll(m);
    }
    @Override
    public void clear() {
        table = new Entry[capacity];
        size = 0;
    }
 

¿Cómo lo implementarías? ya que me queda sólo esto para terminar con la estructura.

Espero sus respuestas y Saludos.

[detective_jd]

Les cuento solucioné mi problema con lo de los índices, arreglando mi problema de esta forma:

crear una función para obtener el indice vacio para almacenar en el put

Código Java:

private int indexPut() {
        for(int i= 0 ; i < table.length; i++){
            if(table[i] == null){
                 return i;
            }
        }
        return -1;
    }
 

Y para cuando quiero filtrar mi map para el get, containsKey y remove, hago otra función pasándole cómo parámetro la clave:

Código Java:

private int getIndex(Object key) {
        for(int i= 0 ; i < table.length; i++){
            if(table[i] != null && table[i].getKey() == key){
                 return i;
            }
        }
        return -1;
    }
 

Aunque eso me hizo unos cuantos cambios, pero la estructura ya está en su 95% de funcionamiento salvo que no me anda el putAll:

Código Java:

@Override
    public V put(K key, V value) {
        if(key == null){
            return null;
        } else {
            int index = indexPut();
            Entry<K, V> pair = table[index];
            if(size == table.length){
                table = Arrays.copyOf(table, table.length +1);
            }
            if (pair != null && pair.getKey().equals(key)) {
                V oldValue = pair.getValue();
                pair.setValue(value);
                return oldValue;
            }            
            table[index] = new Entry(key, value);
            size++;
            return value;
        }
    }
@Override
    public void putAll(Map<? extends K, ? extends V> m) {
        if(m.size() > 0){
            m.entrySet().forEach((e) -> {
                this.put(e.getKey(), e.getValue());
            });
        }
    }
 

El problema se debe a que le pongo al inicializar un tamaño de 4 para probar si aumenta el almacenamiento del map en la función put pero no funciona.

Este error me da:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at hashmapsimple.MyMap.put(MyMap.java:38)
at hashmapsimple.MyMap.lambda$putAll$0(MyMap.java:135 )
at java.util.HashMap$EntrySet.forEach(HashMap.java:10 43)
at hashmapsimple.MyMap.putAll(MyMap.java:134)
at hashmapsimple.Cuerpo.main(Cuerpo.java:15)
/home/detectivejd/.cache/netbeans/8.2/executor-snippets/run.xml:53: Java returned: 1
BUILD FAILED (total time: 0 seconds)

Espero sus respuestas y Saludos.

[CalgaryCorpus]

Haz las validaciones antes de las acciones.

[detective_jd]

Hey CalgaryCorpus gracias por responder, verás pude resolver mi problema, la función put me quedó de esta forma:

Código Java:

@Override
    public V put(K key, V value) {
        if(key == null){
            return null;
        } else {            
            if(size == table.length){
                table = Arrays.copyOf(table, table.length +1);
            }
            int index = indexPut();
            if (table[index] != null && table[index].getKey().equals(key)) {
                V oldValue = table[index].getValue();
                table[index].setValue(value);
                return oldValue;
            }            
            table[index] = new Entry(key, value);
            size++;
            return value;
        }
    }
 

Luego tuve otro problemilla más pero lo resolví que era el de las iteraciones:

Código Java:

@SuppressWarnings("empty-statement")
        public Entry<K,V> nextEntry() {
            currEntry = nextEntry;                            
            index++;
            // tuve que hacer este if para que no me diera error por el tema de los índices
            if (index != size && table[index] != null) {
                nextEntry = table[index];               
            } else {
                nextEntry = null;
                for (;index < table.length; index++){
                    if (table[index] != null){
                        nextEntry = table[index];
                    }
                }
            }
            return currEntry;
        }       
    }
 

Quería saber tu opinión porque en así están rebuscados tanto el put como el de las iteraciones.
Y de paso preguntarte: ¿si publico mi código completo con comentarios lo mirarías? es que quiero tener una opinión objetiva de la estructura y también pondría tu nombre cómo autor del código además del mío jeje....

Espero sus respuestas y Saludos.

PD1: Porque luego de esto quiero ver si con este código puedo hacer bien HashSet (de la misma forma que Oracle, xq ellos trabajan internamente con el HashMap para las funciones y los métodos de HashSet).

PD2: Estaba trasnochado cuando escribí el mensaje anterior.

[detective_jd]

Buenas a todos, quería poner el código completo aquí:

Implementación de HashMap con comentarios de cada cosa hecha

https://pastebin.com/LnmEN8jJ

En este otro link están las pruebas hechas que hice verificando sí anda o no:

https://pastebin.com/KVyP3yd3

Me gustaría saber sus opiniones, ya que las cuales serán muy importantes para lo que vaya a hacer después.

Espero sus respuestas y Saludos.

[CalgaryCorpus]

Felicitaciones por la publicacion del codigo.
Has pensado en usar github o similar?
No creo que el foro sea la mejor manera de iterar sobre el, en realidad, pues es muy extenso y tal vez no sea de mucha utilidad algo como pastebin una vez que recibas comentarios y decidas cambiarlo.

Ejemplo:
- Elimina de los comentarios que cada metodo empiece con "metodo que ..." o "funcion que ..", es superfluo decirlo.
- Elimina en genral todos los comentarios superfluos o que no aporten a comprender el codigo. Ejemplo de esto es poner como comentario "constructor" al constructor por default.
- Por que tu constructor no pide memoria para la tabla?
- Por que al usar la capacidad de la tabla solo pides memoria para 1 elemento mas. No es razonable aumentar al doble? o aumentar tanto como se pidio al inicio en el constructor?
- Hay errores de tipeo en los comentarios, por ejemplo dice "incremenatamos", "qye"
- Como esta construido el metodo getIndex solo retorna un valor -1 si es que encuentra el objeto al interior, de modo que es superfluo preguntar una vez que usaste ese metodo si es que el objeto es efectivamente el que buscabas, si esto no fuera asi, tu metodo getIndex estaria mal construido.
- capacity no lo usas, eliminalo (o usalo, actualizalo)
- Si existiera una manera magica de que dado un objeto con una clave cualquiera te dijera exactamente donde esta o donde deberia ir, sin tener que recorrer el arreglo, y fuera super rapida, la usarias? Eso es lo que esta detras de hashCode que apareces menospreciando al inicio en el comentario inicial. Si tu arreglo creciera a varios miles de datos la funcion magica se hace mas y mas atractiva.
- getIndex podria terminar antes la iteracion al encontrar el primer null
- al borrar, puesto que no hay orden interno, por que no mueves solo el ultimo elemento a la posicion del que borras, en vez de mover todos 1 lugar?
- Sugiero hacer varias pruebas pequenas en vez de hacer 1 sola gran prueba. Cada prueba es 1 metodo, en cada prueba creas un hashmap, agregas entradas y pruebas que un cierto metodo del hashmap funciono. Cada prueba ejercita 1 cosa, y el resto de las pruebas asumen que lo que ya probaste no hay que probarlo de nuevo. Puedes probar los distintos constructores que provees, pues ahora estas probando solo 1, que pasa cuando usas un tamano explicito?

Una vez que tengas estos comentarios considerados, volveras a publicar en el foro un link a otro sitio? Eso es lo que me parece que no esta bien, pues el foro pierde su valor, no?

[detective_jd]

Hola CalgaryCorpus muchísimas gracias por responder, no sabés cómo me ayudó tu opinión:

Has pensado en usar github o similar?
No creo que el foro sea la mejor manera de iterar sobre el, en realidad, pues es muy extenso y tal vez no sea de mucha utilidad algo como pastebin una vez que recibas comentarios y decidas cambiarlo.

La verdad me había olvidado de github, bueno como eran 2 archivos pensé que no pasaría nada, pero con lo de las pruebas si, lo haré en github la próxima vez.

- Elimina de los comentarios que cada metodo empiece con "metodo que ..." o "funcion que ..", es superfluo decirlo.

Ya lo hice

- Elimina en genral todos los comentarios superfluos o que no aporten a comprender el codigo. Ejemplo de esto es poner como comentario "constructor" al constructor por default.

Ya lo hice

- Por que tu constructor no pide memoria para la tabla?

¿A que te refieres? Puede que haya olvidado el concepto y la idea.

- Por que al usar la capacidad de la tabla solo pides memoria para 1 elemento mas. No es razonable aumentar al doble? o aumentar tanto como se pidio al inicio en el constructor?

Me aseguré de que aumenté el doble.

- Hay errores de tipeo en los comentarios, por ejemplo dice "incremenatamos", "qye"

Me deshice de eso

- capacity no lo usas, eliminalo (o usalo, actualizalo)

Eliminé a capacity por relleno.

- al borrar, puesto que no hay orden interno, por que no mueves solo el ultimo elemento a la posicion del que borras, en vez de mover todos 1 lugar?

Hice lo que me dijiste y funcionó, además en las tablas hash el órden es lo que menos importa.

- Sugiero hacer varias pruebas pequenas en vez de hacer 1 sola gran prueba. Cada prueba es 1 metodo, en cada prueba creas un hashmap, agregas entradas y pruebas que un cierto metodo del hashmap funciono. Cada prueba ejercita 1 cosa, y el resto de las pruebas asumen que lo que ya probaste no hay que probarlo de nuevo. Puedes probar los distintos constructores que provees, pues ahora estas probando solo 1, que pasa cuando usas un tamano explicito?

Hice todas las pruebas y anda bien, aunque tuve que hacer algunas modificaciones.

Eso es lo que pude hacer
-----------------------------------------------------------------------------------------------------

Como esta construido el metodo getIndex solo retorna un valor -1 si es que encuentra el objeto al interior, de modo que es superfluo preguntar una vez que usaste ese metodo si es que el objeto es efectivamente el que buscabas, si esto no fuera asi, tu metodo getIndex estaria mal construido.

- Si existiera una manera magica de que dado un objeto con una clave cualquiera te dijera exactamente donde esta o donde deberia ir, sin tener que recorrer el arreglo, y fuera super rapida, la usarias? Eso es lo que esta detras de hashCode que apareces menospreciando al inicio en el comentario inicial. Si tu arreglo creciera a varios miles de datos la funcion magica se hace mas y mas atractiva.

- getIndex podria terminar antes la iteracion al encontrar el primer null

No es que menosprecie al HashCode para nada, el problema es que intenté e intenté implementarlo pero no dí al clavo....
Busqué algo llamado búsqueda por transformación de claves pero no hay una implementación y una de esas me manda sólo al principio.

Código Java:

public int hash(Object key){
        return key.hashCode() % table.length;
    }
 

que vimos que no funcionó, sé que logro eso y logro un mini calco de la implementación de Oracle.

Espero sus respuestas y saludos.

[detective_jd]

Hola CalgaryCorpus y a todos, estuve mirando lo de hashCode y encontré esto:

Código Java:

private int getIndex(Object key) {
        int ret = key.hashCode() % table.length;
        if(ret < 0) {
            ret += table.length;
        }
        return ret;
    }
 

El cual andar anda, pero cuando quiero agregar más de 4 elementos me hace esto por consola:

---PROBANDO MAP2---
tamaño -> 7

--valores--
John
Paula
Andrea

--claves--
4
1
6

--entradas--
clave -> 4 valor -> John
clave -> 1 valor -> Paula
clave -> 6 valor -> Andrea

cuando en el map2 agregue esto:

Código Java:

MyMap<Integer,String>m2= new MyMap(2);
        m2.put(1, "Paula");
        m2.put(2, "Pedro");
        m2.put(3, "Fabio");
        m2.put(4, "John");
        m2.put(5, "Manuela");
        m2.put(6, "Andrea");
        m2.put(7, "Luisa");
 

Por otro lado hice un pequeño cambio a addEntry xq cómo estaba haciendo de que duplica cuando la cantidad actual es igual al largo es ineficiente debido a la lentitud del mismo, y tuve que cambiar la condición:

Código Java:

@Override
    public V put(K key, V value) {
        if(key != null){
            int index = this.getIndex(key);
            if (table[index]!= null && table[index].getKey().equals(key)) {
                V oldValue = table[index].getValue();
                table[index].setValue(value);
                return oldValue;
            }  
            this.addEntry(key, value, index);
            return value;
        }
        return null;
    }
    private void addEntry(K key, V value, int index){
        if(size >= table.length * 3/4){
            table = Arrays.copyOf(table, table.length * 2);
        }
        table[index] = new Entry(key, value);
        size++;
    }
 

En esta página lo explica mejor: http://www.toves.org/books/data/ch06-hash/

A mi getIndex que tiene el código del hashCode le falta algo pero no sé que, no sé que pueden decir.

Espero sus respuestas y saludos.

[CalgaryCorpus]

La tabla está siendo recreada, usar el hashcode y la operación de modulo funciona bien si la tabla no cambia de tamaño, para comprobarlo, inicializa tu hashmap con un tamaño mayor que el número de elementos insertados.

Si vas a modificar el tamaño, vas a afectar tu cálculo del indíce, tal como lo tienes, o tienes en cuenta eso o bien cuentas con una estrategia para resolver colisiones.

[detective_jd]

Hola CalgaryCorpus acabo de probar inicializando con 16 o 24 y me hace esto:

1
2
3
4
5
6
7

---PROBANDO MAP2---
tamaño -> 7

--valores--

--claves--

--entradas--

no me da indice 0 y por consecuente tampoco me lista nada,
Estuve mirando en algunos sitios sobre resolución de colisiones y hasta lo que me pueda servir más puede ser esto:

https://www.infor.uva.es/~cvaca/asigs/doceda/tema5.pdf

Pero mañana lo probaré, aunque me gustaría tu opinión al respecto viendo visto mi código y estos leves cambios respecto que publiqué.

Espero sus respuestas y Saludos.

[CalgaryCorpus]

Si usas el hashCode tienes que dejar de usar el acceso secuencial de los datos, no te va a funcionar tampoco el borrado tal como lo tienes, pues tambien supone datos consecutivos, pero sera rapido de accesar los datos que ya estan, si conoces la key.

[detective_jd]

Hola CalgaryCorpus intenté hacer esto para el tema de las colisiones:

Código Java:

private int getIndex(Object key) {
        int ret = key.hashCode() % table.length;
        if(ret < 0) {
            ret += table.length;
        }
        System.out.println(ret);
        return ret;
    }
private void addEntry(K key, V value){
        if(size >= table.length * 3/4){
            Entry<K,V>[] tmp = table;
            size = 0;
            cap = 2 * cap;
            table = new Entry[cap];
            for(int i = 0; i < cap; i++){
                table[i] = null;
            }
            for (Entry<K, V> e : tmp) {     
                if(e != null){
                    put(e.getKey(),e.getValue());
                }
            } //table = Arrays.copyOf(table, table.length * 2);
        }
        int index = getIndex(key);
        table[index] = new Entry(key, value);
        size++;
    }
 

Pero me terminó haciendo esto:

run:
1
1
2
2
3
3
0
1
1
2
2
3
3
4

---PROBANDO MAP1---
tamaño -> 4

--valores--

--claves--

--entradas--

¿Que estrategia me dirías para el tema de las colisiones?

Espero sus respuestas y Saludos.

[CalgaryCorpus]

Asumo que no has cambiado el recorrido que haces para imprimir el contenido del hashmap. Hazlo. Sino, seguirás viendo contenido parcial o nada.
No estás haciendo nada por las colisiones, revisa los links que tú mismo dejaste aquí para que veas opciones.
Recuerda que si tu tabla crece, invalidas lo que ya tienes en el map.

[detective_jd]

Hola CalgaryCorpus con respecto a los recorridos, estuve mirando y no pude con esto, pero también dime cambiar el recorrido para imprimir debo tener en cuenta el hashCode ¿verdad? en este caso sería getIndex, xq excepto eso no se me ocurre nada:

Código Java:

private abstract class HashIterator<E> implements Iterator<E> {
        private int index = 0;
        private Entry<K,V> currEntry = null;
        private Entry<K,V> nextEntry = null;
        /**
         * Construye una nueva iteración hash
         */
        @SuppressWarnings("empty-statement")
        HashIterator() {
            if (table[index] != null){
                nextEntry = table[index];
            }            
        }
        /**
         * Verifica si hay una siguiente entrada
         * 
         * @return boolean -> verdadero o falso 
         */
        @Override
        public boolean hasNext() {
            return nextEntry != null;
        }
        /**
         * Obtiene la entrada próxima, y también es una función 
         * sobreexplotada para los recorridos ;)
         * 
         * @return Entry<K,V> -> entrada clave/valor
         */
        @SuppressWarnings("empty-statement")
        public Entry<K,V> nextEntry() {
            currEntry = nextEntry;
            index++;
            if (index < size && table[index] != null) {
                nextEntry = table[index];               
            } else {
                nextEntry = null;
                for (;index < size; index++){
                    if (table[index] != null){
                        nextEntry = table[index];
                    }
                }
            }
            return currEntry;
        }       
    }
 

Porque si no resuelvo esto, no podré continuar.

Espero sus respuestas y saludos.

[CalgaryCorpus]

Si el hashcode te indica posiciones disjuntas o separadas, especialmente si no parten del inicio del arreglo, no puedes hacer un recorrido que no considere eso.
Considera que la tabla ha sido llenada de manera disjunta y no necesariamente partiendo de la primera posicion. Miro tu codigo y es esto lo que asumes y por eso no funciona lo que has hecho. Obtener la siguiente posicion ocupada tambien tendra la misma suposicion (disjuntas) y tendra el mismo problema si supones que los datos estan uno despues del otro.