HashMap - implementación propia

package hashmapsimple;
import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
/**
 * Hacer una implementación propia de HashMap ha sido una experiencia algo
 * desafiante ya que el HashMap que hace Oracle y desde versiones antes de la
 * 7 dicha estructura depende ciegamente de la función hashCode para que su
 * funcionamiento sea óptimo, pero al investigar un poco usando funciones de
 * búsqueda secuencial como indexPut y getIndex hace cuestionar un poco la
 * existencia de la función hashCode, además de decir que querían un estilo
 * diferente para obtener las posiciones para almacenar o buscar mediante
 * fórmulas matemáticas.
 * Por otro lado esta temática de hacer distintos Iterators basándose en uno
 * abstracto y hacer que su comportamiento sea distinto en base a su clase
 * abstracta es algo ingenioso de parte de Oracle, aunque algunas condiciones
 * y métodos que usé para lograr dicha implementación son un poco cuestionados
 * porque no se me ocurrió una idea mejor de cómo implementarlos.
 * El reto sería implementar un HashSet "casero" y que funcione internamente
 * por medio de este HashMap "creado"
 *
 * @author detectivejd
 * @param <K>
 * @param <V>
 */
public class MyMap<K, V> implements Map<K,V>{
    private int capacity;
    private int size;
    private Entry<K,V>[] table;
    /**
     * Contructor del HashMap
     */
    public MyMap() {
        this(4);
    }
    /**
     * Constructor del HashMap con disponibilidad de decir que cantidad
     * de elementos deseamos almacenar
     *
     * @param xcapacity
     */
    public MyMap(int xcapacity) {
        if(xcapacity <= 0){
            throw new IllegalArgumentException("Capacidad no permitida: " + capacity);
        } else {
            this.capacity = xcapacity;
        }
        this.clear();
    }
    /**
     * Constructor del HashMap que utilizamos para almacenar toda una estructura
     * de datos map a nuestra estructura de datos
     *
     * @param m
     */
    public MyMap(Map<? extends K, ? extends V> m) {
        this.putAll(m);
    }
    /**
     * Método utilizado para vaciar la estructura de datos
     */
    @Override
    public void clear() {
        /*
            inicializo el array de las entradas según la capacidad
            puesta por defecto o pasada en el constructor
        */
        table = new Entry[capacity];
        // inicializo la cantidad de elementos a 0
        size = 0;
    }
    /**
     * Método utilizado para transferir toda una estructura de tipo
     * Map a nuestro HashMap "casero"
     *
     * @param m -> mapa de clave/valor
     */
    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        /*
            Si la cantidad del Map a transferir es mayor a 0,
            recorremos dicho Map y por cada entrada que tenga
            el mismo será almacenado a nuestro "HashMap"
        */
        if(m.size() > 0){
            m.entrySet().forEach((e) -> {
                this.put(e.getKey(), e.getValue());
            });
        }
    }
    /**
     * Función que utilizamos para guardar una entrada clave/valor
     * a nuestro HashMap "casero"
     *
     * @param key -> clave
     * @param value -> valor
     * @return V -> valor
     */
    @Override
    public V put(K key, V value) {
        // si la clave es nula, la función retorna nula
        if(key == null){
            return null;
        } else {
            /*
                de lo contrario creamos una variable entera llamada index a la
                cual le asigno como valor el resultado de la función getIndex
                pasándole nuestra clave como parámetro, dicha función devuelve
                el índice de una entrada de datos existente.
            */
            int index = this.getIndex(key);
            /*
                si index es distinto a -1 es porque encontró una entrada en
                nuestra estructura de datos. Sería lo mismo que decir si es != null
            */
            if(index != -1){
                /*
                    Luego preguntamos si la entrada del índice encontrado cuya
                    clave es igual a la clave que pasamos por parámetro en la
                    función
                */
                if (table[index].getKey().equals(key)) {
                    /*
                        creamos una variable tipo Value llamada oldValue
                        al cual le pasamos el valor actual de la entrada
                        cuyo índice fue encontrado
                    */
                    V oldValue = table[index].getValue();
                    /*
                        reemplazamos el valor actual de la entrada encontrada
                        por el valor pasado por parámetro
                    */
                    table[index].setValue(value);
                    /*
                        retornamos en la función la variable oldValue dando
                        nuestra función finalizada en caso de que la clave pasada
                        por parámetro ya existe en una de las entradas almacenadas
                    */
                    return oldValue;
                }
            }
            /*
                Pero en caso de que la clave pasada por parámetro no exista en
                nuestra estructura, utilizamos el método addEntry para almacenar
                la clave y valor pasados por parámetro en nuestro Map
            */
            this.addEntry(key, value);
            /*
                retornamos en nuestra función el valor pasado por parámetro
                dando finalizada nuestra función
            */
            return value;
        }
    }
    /**
     * Método privado para almacenar la clave/valor a nuestra
     * estructura de datos
     *
     * @param key -> clave
     * @param value -> valor
     */
    private void addEntry(K key, V value){
        /*
            si la cantidad almacenada en nuestra estructura de datos es
            igual a la cantidad disponible del array
        */
        if(size == table.length){
            // incrementamos a 1 la capacidad disponible del array
            table = Arrays.copyOf(table, table.length +1);
        }
        /*
            creamos una variable a la cual le asignamos el resultado de
            la función indexPut la cual sirve para obtener un índice en
            dónde pueda posicionar la entrada a creer
        */
        int index = indexPut();
        /*
            Creamos una nueva entrada a la cual le pasamos la clave y valor
            los cuales pasamos por parámetro en nuestra función, luego lo
            posicionamos en la posición disponible para almacenar en el map.
        */
        table[index] = new Entry(key, value);
        // incremenatamos la cantidad de elementos a 1 más
        size++;
    }
    /**
     * Función privada utilizada para obtener un índice disponible
     * cuyo fin será posicionar una entrada de datos nueva
     *
     * @return int -> índice para almacenar una entrada nueva
     */
    private int indexPut() {
        /*
            Recorre el array interno de nuestra estructura y si hay
            una posición que esté vacía la función retornará esa posición
        */
        for(int i= 0 ; i < table.length; i++){
            if(table[i] == null){
                 return i;
            }
        }
        /*
            de lo contrario retornará -1, lo cual nunca pasará
        */
        return -1;
    }
    /**
     * Funciona privada para obtener el índice de una entrada
     * existente
     *
     * @param key -> clave
     * @return int -> índice para obtener una entrada existente
     */
    private int getIndex(Object key) {
        /*
            recorre el array interno de nuestra estructura y si nuestro
            array en la posición actual es distinto de nulo y si el mismo
            cuya clave es igual a la clave pasada por parámetro, entonces
            la función devolverá dicha posición actual quedando finalizada
        */
        for(int i= 0 ; i < table.length; i++){
            if(table[i] != null && table[i].getKey() == key){
                 return i;
            }
        }
        /*
            de lo contrario, la función devolverá -1 dejando en claro
            que no encontró nada, además -1 es lo mismo que decir null
            pero en enteros.
        */
        return -1;
    }
    /**
     * Función utilizada para encontrar un valor mediante una clave
     * pasada por parámetro
     *
     * @param key -> clave
     * @return V -> valor
     */
    @Override
    public V get(Object key) {
        /*
            Usando un operador ternario preguntamos si el resultado de la función
            getEntry a la cual le pasamos por parámetro una clave es null,
            retornará null, de lo contrario retornará el valor de la función
            getEntry que usamos antes
        */
        return (this.getEntry(key) == null) ? null : this.getEntry(key).getValue();
    }
    /**
     * Función útil para determinar si existe una entrada existente
     * por medio de una clave pasada por parámetro
     *
     * @param key -> clave
     * @return boolean -> verdadero o falso
     */
    @Override
    public boolean containsKey(Object key) {
        /*
            Mediante una prueba lógica hacemos que la función devuelve
            el resultado de la función getEntry pasándole la clave
            por parámetro y que la misma es distinto de null
        */
        return this.getEntry(key) != null;
    }
    /**
     * Función privada que utilizamos para obtener una entrada
     * mediante una clave pasada por parámetro
     *
     * @param key
     * @return Entry<K, V> -> entrada clave/valor
     */
    private Entry<K, V> getEntry(Object key) {
        /*
            creamos una variable entera llamada index a la
            cual le asigno como valor el resultado de la función getIndex
            pasándole nuestra clave como parámetro, dicha función devuelve
            el índice de una entrada de datos existente.
        */
        int index = getIndex(key);
        /*
            si index es distinto a -1 es porque encontró una entrada en
            nuestra estructura de datos. Sería lo mismo que decir si es != null
        */
        if(index != -1){
            /*
                si nuestro array en la posición encontrada es distinto de nulo y si
                el mismo cuya clave es igual a la clave pasada por parámetro
            */
            if (table[index] != null && table[index].getKey().equals(key)){
                /*
                    en caso de que la condición se cumpla la función devolverá
                    el contenido del array de la posición encontrada
                */
                return table[index];
            }
        }
        /*
            y si la primera condición no sé cumplió o sea que no encontró
            nada, la función devolverá null
        */
        return null;
    }
    /**
     * Función útil para determinar si existe una entrada existente
     * por medio de un valor pasado por parámetro
     *
     * @param value -> valor
     * @return boolean -> verdadero o falso
     */
    @Override
    public boolean containsValue(Object value){
        // sí el valor pasado por parámetro es distinto de null
        if(value != null){
            // recorremos las entradas existentes de nuestro array interno
            for (Entry val : table) {
                /*
                    si valor recorrido actual es distinto de nulo y si el mismo
                    es igual al valor pasado por parámetro
                */
                if (val != null && value.equals(val.getValue())){
                    // la función devolverá true o sea verdadero
                    return true;
                }
            }
        }
        /*
            pero si ninguna condición se cumple, la función devolverá
            false o sea falso
        */
        return false;
    }
    /**
     * Devuelve la cantidad de elementos almacenados en nuestra
     * estructura de datos
     *
     * @return int -> entero
     */
    @Override
    public int size() {
        return size;
    }
    /**
     * Función que determina si nuestra estructura de datos esta vacía o no
     *
     * @return boolean -> verdadero o falso
     */
    @Override
    public boolean isEmpty(){
        return size == 0;
    }
    /**
     * Función útil para eliminar un elemento existente por medio de
     * una clave pasada por parámetro
     *
     * @param key
     * @return V -> valor
     */
    @Override
    public V remove(Object key){
        /*
            creamos una variable entera llamada index a la
            cual le asigno como valor el resultado de la función getIndex
            pasándole nuestra clave como parámetro, dicha función devuelve
            el índice de una entrada de datos existente.
        */
        int index = getIndex(key);
        /*
            si index es distinto a -1 es porque encontró una entrada en
            nuestra estructura de datos. Sería lo mismo que decir si es != null
        */
        if(index != -1){
            /*
                creamos una entrada a la cuál le pasamos por valor el contenido
                del array en la posición que fue encontrada anteriormente, en
                realidad la entrada creada la usaremos sólo para que la función
                retorne el valor de la misma nada más.
            */
            Entry<K,V> e = table[index];
            /*
                recorremos desde el posición encontrada hasta la cantidad de
                elementos almacenados de nuestra estructura
            */
            for(; index < size; index++){
                /*
                    mediante los recorridos que hagamos reemplazaremos el
                    contenido de la posición actual por el de la próxima
                    posición, sólo qye tuve que usar un operador ternario
                    debido a que cómo tenía: table[index] = table[index +1];
                    sólo me modificaba hasta la penúltima posición y no la
                    última, hasta el momento encontré esta forma para llevar
                    a cabo mi cometido
                */
                table[index] = ((index +1) == size) ? null : table[index + 1];
            }
            // disminuímos la cantidad almacenada de elementos
            size--;
            /*
                la función retorna el valor de nuestra entrada que antes
                habíamos creado
            */
            return e.getValue();
        }
        /*
            pero si no cumple para nada la condición del principio, la función
            devolverá null debido a que no encontró entrada con la clave que
            pasamos por parámetro
        */
        return null;
    }
    /*-----------------------------------------------------------*/
    /**
     * Devuelve un conjunto de todas las claves almacenadas en
     * nuestra estructura de datos
     *
     * @return Set<K> -> tupla de claves
     */
    @Override
    public Set<K> keySet() {
        /*
            devolvemos a esta función una nueva instancia de
            KeySet para el recorrido de las claves
        */
        return new KeySet();
    }
    /*-----------------------------------------------------------*/
    /**
     * KeySet es una clase interna que utilizamos para las iteraciones
     * (recorridos que hacemos con foreach) de las claves
     */
    private class KeySet extends AbstractSet<K>{
        /**
         * Función usada para dar estilo al recorrido pertinente
         * o sea para las claves
         *
         * @return Iterator<K> -> recorrido de claves
         */
        @Override
        public Iterator<K> iterator() {
            /*
                Retornamos en la función una nueva instancia de la clase
                KeyIterator para dar estilo al recorrido de las claves
            */
            return new KeyIterator();
        }
        /**
         * Misma idea de la función size de nuestra estructura
         *
         * @return int -> entero
         */
        @Override
        public int size() {
            return size;
        }
    }
    /**
     * Clase interna para dar estilo al recorrido de las claves
     */
    private final class KeyIterator extends HashIterator<K> {
        /**
         * Obtiene la siguiente clave del recorrido
         *
         * @return K -> clave
         */
        @Override
        public K next() {
            return nextEntry().getKey();
        }
    }
    /*-----------------------------------------------------------*/
    /**
     * Devuelve una colección de los valores almacenados de
     * nuestra estructura de datos
     *
     * @return Collection<V> -> colección de valores
     */
    @Override
    public Collection<V> values() {
        /*
            devolvemos a esta función una nueva instancia de
            Values para el recorrido de los valores
        */
        return new Values();
    }
    /**
     * Values es una clase interna que utilizamos para las iteraciones
     * (recorridos que hacemos con foreach) de los valores
     */
    private class Values extends AbstractCollection<V>{
        @Override
        public Iterator<V> iterator() {
            /*
                Retornamos en la función una nueva instancia de la clase
                ValueIterator para dar estilo al recorrido de los valores
            */
            return new ValueIterator();
        }
        /**
         * Misma idea de la función size de nuestra estructura
         *
         * @return int -> entero
         */
        @Override
        public int size() {
            return size;
        }
    }
    /**
     * Clase interna para dar estilo al recorrido de los valores
     */
    private final class ValueIterator extends HashIterator<V>{
        /**
         * Devuelve el siguiente valor del recorrido
         *
         * @return V -> valor
         */
        @Override
        public V next() {
            return nextEntry().getValue();
        }
    }
    /*-----------------------------------------------------------*/
    /**
     * Devuelve un conjunto de las entradas almacenadas en
     * nuestra estructura de datos
     *
     * @return Set<Map.Entry<K, V>> -> conjunto de entradas
     */
    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        /*
            devolvemos a esta función una nueva instancia de
            EntrySet para el recorrido de las entradas
        */
        return new EntrySet();
    }
    /**
     * EntrySet es una clase interna que utilizamos para las iteraciones
     * (recorridos que hacemos con foreach) de las entradas
     */
    private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        @Override
        public Iterator<Map.Entry<K, V>> iterator() {
            /*
                Retornamos en la función una nueva instancia de la clase
                EntryIterator para dar estilo al recorrido de las entradas
            */
            return new EntryIterator();
        }
        /**
         * Misma idea de la función size de nuestra estructura
         *
         * @return int -> entero
         */
        @Override
        public int size() {
            return size;
        }
    }
    /**
     * Clase interna para dar estilo al recorrido de las entradas
     */
    private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
        /**
         * Devuelve la siguiente entrada del recorrido
         *
         * @return V -> valor
         */
        @Override
        public Entry<K, V> next() {
            return nextEntry();
        }
    }
    /*-----------------------------------------------------------*/
    /**
     * Clase abstracta que usamos para los distintos tipos de
     * recorridos empleados en nuestra estructura de datos
     *
     * @param <E>
     */
    private abstract class HashIterator<E> implements Iterator<E> {
        /*
            index una variable que usamos para los recorrer
            entrada por entrada
        */
        private int index = 0;
        // currEntry es la entrada en la que estamos actualmente parados
        private Entry<K,V> currEntry = null;
        // nextEntry es la entrada que le sigue a la actual
        private Entry<K,V> nextEntry = null;
        /**
         * Constructor del HashIterator
         */
        @SuppressWarnings("empty-statement")
        HashIterator() {
            /*
                Sí el contenido del array en la posición actual 0 es distinto
                de null, nextEntry tendrá el valor de la primera entrada
                almacenada ya que hacemos esto para obtener la primera entrada
            */
            if (table[index] != null){
                nextEntry = table[index];
            }
        }
        /**
         * Función booleana que determina si hay o no una siguiente
         * entrada
         *
         * @return boolean -> verdadero o falso
         */
        @Override
        public boolean hasNext() {
            /*
                retornamos la función con una prueba lógica de sí
                la próxima entrada es distinta de null o no
            */
            return nextEntry != null;
        }
        /**
         * Función utilizada para obtener la entrada próxima, y también
         * una función sobreexplotada para los recorridos ;)
         *
         * @return Entry<K,V> -> entrada clave/valor
         */
        @SuppressWarnings("empty-statement")
        public Entry<K,V> nextEntry() {
            /*
                a la entrada actual le pasamos como valor la siguiente para
                usarla al final de la función
            */
            currEntry = nextEntry;
            // incrementamos el índice al siguiente
            index++;
            /*
                tuve que hacer esta condición así porque si sólo le ponía
                de esta forma: if(table[index] != null) me daba este error:
                Exception in thread "main" ArrayIndexOutOfBoundsException: 6
                pero la idea es que si el índice actual es menor al tamaño de
                la entradas almacenadas y el contenido del array de dicha
                posición es distinto de nulo
            */
            if (index < size && table[index] != null) {
                /*
                    le asignamos a la siguiente entrada el contenido del
                    array de la posición en la que estamos parados
                */
                nextEntry = table[index];
            } else {
                /*
                    de lo contrario le asignamos a la siguiente entrada nulo
                    y recorremos desde el índice actual hasta el tamaño del
                    array, preguntando si el índice en el que estamos parados
                    es distinto de null, siendo le asignamos a la siguiente
                    entrada el contenido del array de la posición en la que
                    estamos parados
                */
                nextEntry = null;
                for (;index < size; index++){
                    if (table[index] != null){
                        nextEntry = table[index];
                    }
                }
            }
            // y retornamos la entrada actual que mostraría la siguiente
            return currEntry;
        }
    }
    /*-----------------------------------------------------------*/
    /**
     * Clase interna para definir las entradas clave/valor que
     * almacenaremos en nuestra estructura de datos
     *
     * @param <K>
     * @param <V>
     */
    class Entry<K,V> implements Map.Entry<K,V>{
        /*
            key es la clave que usaremos para identificar nuestra entrada,
            la cual cuyo valor no se modificará
        */
        final K key;
        /*
            value será el valor que tenga la entrada
        */
        V value;
        Entry(K k, V v) {
            value = v;
            key = k;
        }
        @Override
        public final K getKey() {
            return key;
        }
        @Override
        public final V getValue() {
            return value;
        }
        @Override
        public V setValue(V v) {
            V val = value;
            value = v;
            return val;
        }
        @Override
        public String toString() {
            return getKey() + " -> " + getValue();
        }
    }
}