Uma breve introdução à HashMap

Patrícia Clares — Sun, 02 Feb 2025 20:04:07 +0000

Sumário

HashMap
- Hash Function
- Load Factor
- Collisions
- Relacionando tudo e aprendendo sobre Open addressing e Separate chaining

HashMap

Um HashMap é uma estrutura de dados que faz parte da biblioteca de coleções em muitas linguagens de programação.
Ele é utilizado para armazenar pares de chave-valor.

Hash Function

Função responsável por transformar um input em um índice do array, o retorno de um Hash Function é chamado de Hash Value ou simplesmente Hash.
Um Hash Function é implementado usando criptografia como SHA-256, MD5 para ser consistente e minimizar duplicações de índices como veremos mais a frente.

Load Factor

Load Factor representa a quantidade que o array esta preenchido, por exemplo, um array que armazena 10 itens e nele ja existem 2 itens armazenados, significa que temos 20%(0.2%) do array preenchido.

Collisions

Quando uma Hash Function produz um hash que já existe como posição, é causado uma collision pois estamos tentando armazenar um valor em uma posição que já tem outro valor armazenado.

Relacionando tudo e aprendendo sobre Open addressing e Separate chaining

Quando o Load Factor atinge 0.7% ou 0.8% (ou seja, quando nosso array está 70% ou 80% preenchido), o HashMap aciona uma função para dobrar o tamanho do array para reduzir a probabilidade de colisão, e recalcular as posições dos elementos. No entanto, isso é muito custoso mas acontece algumas vezes.

Ao tentar realizar uma inserção em um HashMap e acontecer uma colisão, existem duas abordagens de implementação:

Open addressing: busca-se a próxima posição disponível, o que torna a inserção O(n).

Separate chaining -> os elementos são armazenados em uma estrutura encadeada, geralmente uma lista ligada ou, em algumas implementações uma árvore balanceada, tornando a inserção O(1). A intenção é que essa lista seja pequena, devido à baixa probabilidade de colisão quando a função hash é bem implementada.

O artigo foi baseado no curso "Estruturas de Dados e Algoritmos" do Augusto Galego, se curtiu o artigo e gostaria de aprender mais sobre o tema do curso utilize o meu link, irá ajudar bastante!
https://pay.hub.la/L8wi9vio7WPnWbmF8ZIO?ref=soIMpTHnaaX7oPqRCHak

Generics com Java

Patrícia Clares — Sun, 14 May 2023 22:57:39 +0000

Conteúdos

Motivação
Generic Methods
Generic Classes
Generics Interfaces
Bounded Generics
Multiple Bounds
Wildcards
Type erasure

Motivação

Generics foi introduzido no Java SE 5.0 para poupar o desenvolvedor de usar casting excessivos durante o desenvolvimento e reduzir bugs durante o tempo de execução.

Olhe no exemplo abaixo um código sem Generics

List list = new LinkedList();
list.add(new Integer(1));
// Na linha abaixo o compilador irá reclamar pois ele não sabe qual o tipo de dado do retorno
Integer i = list.iterator().next();

Então para silenciar o compilador, precisamos adicionar um casting:

Integer i = (Integer) list.iterator.next();

Não é garantido que a lista contenha apenas inteiros, pois é possível adicionar outros tipos de objetos nela:

List list = List.of(0, "a");

O que pode provocar uma exceção em tempo de execução.

Seria muito mais fácil especificar apenas uma vez o tipo de objeto que estamos trabalhando tornando o código mais fácil de ser lido, evitando os casts excessivos e também potencias problemas em tempo de execução.

// Na linha abaixo estamos especificando o tipo da nossa Lista
List<Integer> list = new LinkedList<>();
list.add(1);
Integer i = list.iterator().next();

Generic Methods

Vamos começar com as características de um método genérico, observe o código abaixo:

public static <T, G> Set<G> fromArrayToEvenSet(T[] a, Predicate<T> filterFunction, Function<T, G> mapperFunction) {
        return Arrays.stream(a)
                .filter(filterFunction)
                .map(mapperFunction)
                .collect(Collectors.toSet());
    }

A característica predominante de um método genérico é o diamond operator logo antes da tipagem do retorno da função, onde eles informam os tipos genéricos dos parâmetros que estamos recebendo, no nosso caso T e G

No código acima estamos recebendo na nossa função genérica um array a que pode ser de qualquer tipo (string, int e etc…).

Em seguida estamos recebendo uma função que é responsável por filtrar o conteúdo do array, note que a função é do tipo Predicate pois essa função tem uma única responsabilidade que é retornar true ou false.

Por último estamos recebendo uma função responsável por transformar um objeto em outro, nesse caso a função é do tipo Function pois ele trabalha em cima do objeto T para retornar um objeto diferente que estamos chamando de G.

Segue o exemplo completo:

public class Main {
    public static void main(String[] args) {

        Integer[] intArray = {1, 2, 3, 4, 5};

        final var stringEvens = fromArrayToEvenSet(intArray, Main::toNumeric, Main::isEven);

        System.out.println(stringEvens);
        // [number: 4, number: 2]
    }

    private static Numeric toNumeric(final int number){
        return new Numeric(number);
    }

    public static boolean isEven(final int number){
        return number % 2 == 0;
    }

    public static <T, G> Set<G> fromArrayToEvenSet(T[] a, Function<T, G> mapperFunction, Predicate<T> filterFunction) {
        return Arrays.stream(a)
                .filter(filterFunction)
                .map(mapperFunction)
                .collect(Collectors.toSet());
    }

    static class Numeric {
        private final int number;

        Numeric(int number) {
            this.number = number;
        }

        @Override
        public String toString() {
            return "number: " + this.number;
        }

    }
}

Generic Classes

Ja vimos anteriormente que um método pode ser genérico mas e se a classe fosse genérica o que aconteceria?

Quando usamos uma classe genérica, precisamos identificar com o diamond operator a quantidade de objetos genéricos que vamos trabalhar, Segue abaixo o exemplo:

public class Example<T> {

    public void doSomething(final T parameter) {
        System.out.println("parameter: " +  parameter);
    }

}

Se tentarmos adicionar um outro objeto como parâmetro no método, o compilador irá reclamar pois não especificamos ele na classe. Podemos adicionar esse objeto genérico no próprio método com o diamond operator como vimos antes, mas vamos seguir pela classe.

Na classe:

public class Example<T, G> {

    public void doSomething(final T parameter, final G parameter2) {
        System.out.println("parameter: " +  parameter);
        System.out.println("parameter2: " +  parameter2);
    }

}

Agora precisamos instanciar essa classe e utilizar esse método.

public class Main {
    public static void main(String[] args) {

        // Note que para cada uma das instâncias estamos passando objeto diferentes
        final var integerExample = new Example<Integer, String>();
        final var listExample = new Example<List, Double>();
        final var doubleExample = new Example<Double, Character>();

        // E ao utilizar o método, precisamos respeitar o objeto que espeficifamos na instância.
        integerExample.doSomething(1, "Olá");
        listExample.doSomething(List.of("1", 2, "3", 4), 4.88);
        doubleExample.doSomething(10.99, 'C');

    }

}

Generics Interfaces

Como vimos em classes, as interfaces seguem a mesma regra:

public interface ExampleInterface<T> {

    void doSomething(final T parameter);

}

Utilização da interface com o tipo inteiro.

// Note que estamos especificando o tipo que a interface irá receber aqui.
public class Example implements ExampleInterface<Integer>{

    // E então o método que estamos sobrescrevendo se transforma no mesmo tipo
    @Override
    public void doSomething(Integer parameter) {
        System.out.println("parameter: " + parameter );
    }

}

Utilização da interface com o tipo Lista.

public class Example implements ExampleInterface<List<String>>{

    @Override
    public void doSomething(List<String> parameter) {
        System.out.println("parameter: " + parameter );
    }
}

Bounded Generics

Bounded significa restrito/limitado, podemos limitar os tipos que o método aceita, por exemplo, podemos especificar que o método aceita todas as subclasses ou a superclasse de um tipo, o que também faz com que nesse exemplo, o nosso tipo genérico herde os comportamentos de Number:

public static <T extends Number> Set<Integer> fromArrayToSet(T[] a) {
        return Arrays.stream(a)
                .map(Number::intValue)
                .collect(Collectors.toSet());
    }

No exemplo acima, limitamos o tipo genérico T para aceitar apenas subclasses da superclasse Number, então o que aconteceria se tentarmos passar uma lista de String para o nosso parâmetro T[]?

String[] stringArray = {"a", "b", "c"};
// Na linha abaixo o compilador irá reclamar de instâncias inválidas do tipo String para Number
final var stringEvens = fromArrayToSet(stringArray);

Multiple Bounds

Como vimos em Bounded Generics podemos limitar quem pode utilizar nosso método genérico, e podemos limitar mais ainda usando interfaces, observe o código abaixo:

public class Main {
    public static void main(String[] args) {

        final Person wizard = new Wizard();
        final Person muggle = new Muggle();

        startWalkAndEat(wizard);
        startWalkAndEat(muggle);
    }

    public static <T extends Person> void startWalkAndEat(T a) {
        a.walk();
        a.eat();
    }

    static class Muggle extends Person {}

    static class Wizard extends Person implements Comparable{
        @Override
        public int compareTo(Object o) {
            return 0;
        }
    }

    static class Person {
        public void walk(){}
        public void eat(){}

    }

}

Tanto um Trouxa como um Bruxo podem comer e andar porque ambos são pessoas, que foi a restrição que adicionamos, apenas subclasses(classes filhas) de Person e a mesma(classe pai) podem utilizar o método startWalkAndEat() mas e se adicionarmos mais uma restrição em cima da atual, onde apenas as classes que implementam a interface Comparable seriam permitidas, o que aconteceria?

public class Main {
    public static void main(String[] args) {

        final Person wizard = new Wizard();
        final Muggle muggle = new Muggle();

        startWalkAndEat(wizard);
        // A linha abaixo começa a dar erro de compilação pois a classe muggle não implementa a interface Comparable
        startWalkAndEat(muggle);
    }
    // Adição da nova restrição
    public static <T extends Person & Comparable> void startWalkAndEat(T a) {
        a.walk();
        a.eat();
    }

    static class Muggle extends Person {}

    static class Wizard extends Person implements Comparable{
        @Override
        public int compareTo(Object o) {
            return 0;
        }
    }

    static class Person {
        public void walk(){}
        public void eat(){}

    }

}

Como comentado no código, agora não é possível passar a classe Muggle para o método startWalkAndEat(), porque esta classe não implementa a interface Comparable.

Wildcards

Observe o código abaixo:

public class Example<T extends Number> {

    public long sum(List<T> numbers) {
        return numbers.stream().mapToLong(Number::longValue).sum();
    }

}

Utilizaremos ele dessa forma:

public class Main {
    public static void main(String[] args) {

      final var example = new Example<>();

      List<Number> numbers = new ArrayList<>();
      numbers.add(5);
      numbers.add(10L);
      numbers.add(15f);
      numbers.add(20.0);
      example.sum(numbers);
  }

}

Estamos passando vários tipos de numbers para a lista, mas e se criarmos uma lista de inteiros?
Se inteiros pertence a Number então, não daria problema, certo?
Errado! Por isso nasceu a necessidade de termos o wildcard, segue o código a seguir.

public class Main {
    public static void main(String[] args) {

      final var example = new Example();

      List<Number> numbers = new ArrayList<>();
      numbers.add(5);
      numbers.add(10L);
      numbers.add(15f);
      numbers.add(20.0);
      // Aqui funciona
      example.sum(numbers);

      List<Integer> numbersInteger = new ArrayList<>();
      numbersInteger.add(5);
      numbersInteger.add(10);
      numbersInteger.add(15);
      numbersInteger.add(20);
      // Mas aqui temos um erro de compilação
      example.sum(numbersInteger);

    }

}

O List<Integer> e o List<Number> não estão relacionados como Integer e Number, eles apenas compartilham o pai comum (List<?>).

Então para resolver esse problema podemos utilizar o Wildcard:

public class Example {

    public long sum(List<? extends Number> numbers) {
        return numbers.stream().mapToLong(Number::longValue).sum();
    }

}

Dessa forma ambas as listas irão funcionar.

É importante observar que, apenas com wildcards podemos limitar os parâmetros dos métodos, não é possível fazer isso com generics.

Também seria possível utilizar sem wildcards, da forma a seguir:

public class Example {

    public <T extends Number> long sum(List<T> numbers) {
        return numbers.stream().mapToLong(Number::longValue).sum();
    }

}

Mas dessa forma limitamos T apenas para Numbers. Nesse caso o wildcard seria mais flexível.

Type erasure

Esse mecanismo possibilitou suporte para Generics em tempo de compilação mas não em tempo de execução.

Na prática isso significa que o compilador Java usa o tipo genérico em tempo de compilação para verificar a tipagem dos dados, mas em tempo de execução todos os tipos genéricos são substituídos pelo tipo raw correspondente.

public class MinhaLista<T> {

  private T[] array;

  public MinhaLista() {
    this.array = (T[]) new Object[10];
  }

  public void add(T item) {
    array[0] = item;
  }

  public T get(int index) {
    return array[index];
  }
}

Depois da compilação:

public class MinhaLista {

  private Object[] array;

  public MinhaLista() {
    this.array = (Object[]) new Object[10];
  }

  public void add(Object item) {
    // ...
  }

  public Object get(int index) {
    return array[index];
  }
}

Para saber mais sobre type erasure, segue o link da baeldung

DEV Community: Patrícia Clares