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
Precisamos verificar, para um username, 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)$ em média para adicionar, remover e verificar existência

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

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

    public boolean userExists(String username) {
        return users.contains(username); // O(1) average time
    }
}

Maps

Como um dicionário: palavra (chave) -> definição (valor)
HashMap: complexidade média $O(1)$ para operações

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

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) average time
    }
}

Método hashCode

O que as torna rápidas -> hashCode()
No exemplo com ArrayList, não sabíamos o índice do username para buscar
Com hashcode(), podemos converter um objeto em um índice para procurar
Exemplo pavlos.2020 -> 35189

pavlos.2020 processado por hashcode, resultando em 35189

Indexando elementos

HashMap e HashSet têm um array subjacente
Ao adicionar um elemento:
- Java chama hashCode() no elemento para obter um inteiro
- Aplica módulo no valor acima 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 // Implemented by 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

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

Ferramentas

Vamos praticar!

Otimização de Código em Java