# Como funciona um Map + Hash Table.

Um `map` tem uma performance muito melhor que uma lista. Isso se dá pelo fato de que o `map` tem acesso direto aos seus recursos a partir de uma chave. Um exemplo básico disso é um `Array` que você acessa a partir de um índice; pro processador você está basicamente dizendo: me dá o que está nessa posição de memória X.

Abaixo vou demonstrar uma implementação muito simples de um `map` + `hash table`.

Primeiro, vamos construir uma classe que se comporte como um map.

class Map {
    constructor() {
        this.elements = [];
    }

    add(key, value) {}
    find(key) {}
    remove(key) {}
    exists(key) {}
}

Nessa classe, ainda não adicionei a implementação desses métodos pois juntamente com eles, explicarei a hash table. (Que nada mais é do que o array chamado `elements` dentro da classe `Map`)

Vou criar agora uma classe chamada `HashUtils` somente pra separar as responsabiliades do `Map` e da geração do hash.

class HashUtils {
    constructor() {
        throw 'Não instancie';
    }

    static toHash(value) {
        if (typeof value === 'string') { // se for string, calcula os charcodes de cada valor
            return value
            .split('')
            .reduce((acc, curr) => acc += curr.charCodeAt(0), 0);
        }
        return value; // se for qualquer coisa além de string, retorna ele mesmo
    }
}

Por exemplo:

HashUtils.toHash('casa'); // retornaria 408
// c = 99
// a = 97
// s = 115
// a = 97

// ou

HashUtils.toHash(25); // retornaria 25

// ou

HashUtils.toHash({ a: 'b' }); // retornaria { a: 'b' } - se fizer algo desse tipo vai ter muito problema relacionado a posição de memória e comparação de objetos. Então evite por favor.

Voltando então a classe `Map`, teremos esse código pra o método `add`:

add(key, value) {
    const idx = HashUtils.toHash(key); // obtenho o índice
    this.elements[idx] = value; // adiciono o valor no array no índice obtido
}

Porém, o que aconteceria se dois textos somassem o mesmo hash? Um exemplo simples disso, seriam palavras que são anagramas.

HashUtils.toHash('saca'); // retornaria 408
// s = 115
// a = 97
// c = 99
// a = 97

Assim, um valor sobreporia o outro, correto? Então vamos deixar o código do `add` mais inteligente!

add(key, value) {
    const idx = HashUtils.toHash(key); // obtenho o índice
    const v = this.elements[idx];
    if (v) { // checo se há valor nesse índice - caso haja
        if (!Array.isArray(v)) { // checo se não é um array - se não for
            this.elements[idx] = [v]; // transformo ele em array e adiciono o valor já existente
        }
        this.elements[idx].push({ key, value }); // após essa checagem, adiciono o novo valor
    } else { // caso não haja
        this.elements[idx] = { key, value }; // adiciono o valor no array
    }
}

Uma mudança nítida foi a forma que os valores são adicionados dentro desse array. Anteriormente adicionávamos apenas o valor, e agora adicionamos um objeto um pouco mais complexo. Isso se dá pela necessidade de checar qual valor obter na hora do `find`.

Mas e o que aconteceria se adicionássemos duas vezes valores distintos com a mesma chave? De acordo com as implementações atuais, o último valor sobreporia o anterior. Vamos implementar dessa forma então:

add(key, value) {
    const idx = HashUtils.toHash(key);
    const v = this.elements[idx];
    if (v) {
        if (!Array.isArray(v)) {
            this.elements[idx] = [v];
        }
        const foundEl = this.elements[idx].find(e => e.key === key); // busco o elemento dentro da minha lista - lembrando que find retorna o primeiro valor encontrado ou undefined. Dada a nossa implementação, sempre teremos só um valor.
        if (foundEl) {
            foundEl.value = value; // caso encontre um elemento, substituo só o valor anterior pelo novo
        } else {
            this.elements[idx].push({ key, value });
        }
    } else {
        this.elements[idx] = { key, value };
    }
}

Como já expliquei todas as intrinsecidades do mapa, vou mostrar a implementação dos outros métodos.

find(key) {
    const idx = HashUtils.toHash(key);
    const v = this.elements[idx];
    if (v) {
        if (Array.isArray(v)) {
            const foundEl = v.find(e => e.key === key);
            return foundEl ? foundEl.value : undefined; // se for array retorno o valor encontrado da chave. (ou undefined caso não exista no array)
        }
        if (v.key === key) {
            return v.value; // se não for array, retorno só o valor encontrado caso a chave seja igual
        }
    }
    return undefined;
}

remove(key) {
    const idx = HashUtils.toHash(key);
    const v = this.elements[idx];
    if (v) {
        if (Array.isArray(v)) {
            const arrIndex = v.findIndex(e => e.key === key);
            if (arrIndex > -1) {
                const valueToBeRemoved = v.splice(arrIndex, 1); // removo esse valor do array 
                if (v.length === 0) {
                    delete this.elements[idx]; // caso nao tenha mais valores na lista, remove por completo o index
                }
                return valueToBeRemoved[0].value;  // e retorno o valor removido pra quem chamou
            }
            return undefined;
        }
        if (v.key === key) {
            delete this.elements[idx];
            return v.value;  // se não for array, retorno só o valor encontrado
        }
    }
    return undefined; // caso não tenha nada pra remover, retorno undefined
}

exists(key) {
    return !!this.find(key); // só utilizo do find pra retornar um booleano
}

Ao final a classe `Map` ficaria assim:

class Map {
    constructor() {
        this.elements = [];
    }

    add(key, value) {
        const idx = HashUtils.toHash(key);
        const v = this.elements[idx];
        if (v) {
            if (!Array.isArray(v)) {
                this.elements[idx] = [v];
            }
            const foundEl = this.elements[idx].find(e => e.key === key); // busco o elemento dentro da minha lista - lembrando que find retorna o primeiro valor encontrado ou undefined. Dada a nossa implementação, sempre teremos só um valor.
            if (foundEl) {
                foundEl.value = value; // caso encontre um elemento, substituo só o valor anterior pelo novo
            } else {
                this.elements[idx].push({ key, value });
            }
        } else {
            this.elements[idx] = { key, value };
        }
    }

    find(key) {
        const idx = HashUtils.toHash(key);
        const v = this.elements[idx];
        if (v) {
            if (Array.isArray(v)) {
                const foundEl = v.find(e => e.key === key);
                return foundEl ? foundEl.value : undefined; // se for array retorno o valor encontrado da chave. (ou undefined caso não exista no array)
            }
            if (v.key === key) {
                return v.value; // se não for array, retorno só o valor encontrado caso a chave seja igual
            }
        }
        return undefined;
    }

    remove(key) {
        const idx = HashUtils.toHash(key);
        const v = this.elements[idx];
        if (v) {
            if (Array.isArray(v)) {
                const arrIndex = v.findIndex(e => e.key === key);
                if (arrIndex > -1) {
                    const valueToBeRemoved = v.splice(arrIndex, 1); // removo esse valor do array 
                    if (v.length === 0) {
                        delete this.elements[idx]; // caso nao tenha mais valores na lista, remove por completo o index
                    }
                    return valueToBeRemoved[0].value;  // e retorno o valor removido pra quem chamou
                }
                return undefined;
            }
            if (v.key === key) {
                delete this.elements[idx];
                return v.value;  // se não for array, retorno só o valor encontrado
            }
        }
        return undefined; // caso não tenha nada pra remover, retorno undefined
    }

    exists(key) {
        return !!this.find(key); // só utilizo do find pra retornar um booleano
    }
}

E sua utilização assim:

const myMap = new Map;

myMap.add('test', 12345);
myMap.add('testa', 123456);
myMap.add(22, 'e ae');
myMap.add(3020, { id: 1234, nome: 'Fulano' });

myMap.find('test'); // retorna 12345
myMap.find(3020); // retorna { id: 1234, nome: 'Fulano' }
myMap.find('valorinexistente'); // retorna undefined

myMap.remove('testa'); // retorna 123456 e remove o valor
myMap.remove('valorinexistente'); // retorna undefined

myMap.exists('test'); // retorna true
myMap.exists('valorinexistente'); // retorna false

É isso. Tentei simplificar ao máximo a explicação, e tenha em vista que é uma implementação puramente didática.

A implementação real com certeza é muito mais complexa e performática. Uma coisa que podemos perceber rapidamente nessa implementação é que o uso de memória é elevado, dado que eu posso escrever em qualquer posição dentro do `Array` e consequentemente ter diversos outros elementos vazios. Por exemplo: Se escrevo somente na posção 499 do array. Meu array vai ter um length de 500, mesmo tendo 499 (do 0 ao 498) vazios. De acordo com [essa thread](https://stackoverflow.com/a/6499525) caso não façamos atribuições (nem mesmo undefined) aos outros índices do array, nunca será alocado um espaço em memória.

Se quiser dar uma olhada em um artigo mais complexo em relação a isso dê uma lida [nesse](https://medium.com/javascript-in-plain-english/algorithm-in-javascript-hash-table-7b0464d2b81b).

Valeu!