Estruturas de dados eficientes: Sets e Maps

Otimização de Código em Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Aplicando complexidade de espaço/tempo

Agora você já conhece complexidade de espaço e tempo!

Como aplicar isso para escrever código mais eficiente?

Escolhendo a estrutura de dados certa!

Um sistema de gerenciamento de usuários

Estamos criando um sistema de gerenciamento de usuários
Para um nome de usuário, precisamos verificar se o usuário existe
Usando uma lista: complexidade $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}

Sets

Uma coleção de elementos únicos com busca rápida
$O(1)$ de tempo médio para adicionar, remover e verificar existência

Solução aprimorada do sistema de usuários:

public class UserRegistry {
    private HashSet<String> users = new HashSet<>();

    public boolean userExists(String username) {
        return users.contains(username); // O(1) tempo médio
    }
}

Maps

Como um dicionário: palavra (chave) -> definição (valor)
HashMap: $O(1)$ de tempo médio por operação

public class UserCache {
    private HashMap<String, UserProfile> userProfiles = new HashMap<>();

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) tempo médio
    }
}

Método hashCode

O que torna isso rápido -> hashCode()
No exemplo com ArrayList, não sabíamos o índice do nome a buscar
Com hashcode(), dá para converter um objeto em um índice pesquisável
Exemplo pavlos.2020 -> 35189

pavlos.2020 processado por hashcode, resultando em 35189

Indexando elementos

HashMap e HashSet usam um array por baixo
Ao adicionar um elemento:
- Java chama hashCode() no elemento para obter um inteiro
- Aplica módulo ao valor para obter o número do bucket

Exemplo:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

"optimizingCodeInJava" -> 1406313774 // Implementado pelo Java
1406313774 % 16 = 14 <- esse é o nosso bucket!

Colisões

Quando mais de um item cai no mesmo bucket
- Chamamos de colisão
LinkedList para o bucket
Por isso dizemos $O(1)$ em média

Um lembrete importante

Escolher a estrutura de dados é como escolher a ferramenta certa: um martelo (ArrayList) é ótimo para pregos, mas péssimo para parafusos (onde um Set funciona melhor).

Uma caixa de ferramentas aberta com martelo, chave de fenda, chave inglesa e alicate lado a lado

Vamos praticar!

Otimização de Código em Java