Chaves compostas: um guia sobre como lidar com elas

Chaves compostas ocorrem quando uma combinação de dados é necessária para definir a “chave” para seu mapa ou pesquisa de cache. Um exemplo disso pode ser quando você precisa armazenar valores em cache com base no nome de um cliente, bem como na função de um usuário. Num caso como este, seu cache precisaria ser capaz de armazenar valores exclusivos com base em cada um desses dois (ou mais) critérios.

Existem algumas maneiras diferentes pelas quais as chaves compostas podem ser tratadas no código.

Combine os critérios em uma string

A primeira resposta é combinar os critérios em uma string para usar como chave. É simples e não exige muito esforço:

 private String getMapKey(Long userId, String userLocale) { return userId + "." userLocale; }

Esta é uma maneira bastante básica de lidar com o problema. O uso de uma chave de string pode facilitar a depuração e as investigações, pois a chave de cache está em um formato legível por humanos. Mas existem alguns problemas a serem observados com esta abordagem:

1. Requer a criação de uma nova string em cada interação com o mapa. Embora essa alocação de strings seja geralmente pequena, se o mapa for acessado com frequência, isso pode levar a um grande número de alocações que levam tempo e precisam ser coletadas como lixo. O tamanho da alocação de string também pode ser maior dependendo do tamanho dos componentes da sua chave ou de quantos você possui.

   
   

2. Você precisa garantir que a chave composta criada não possa ser falsificada em outro valor de chave:

 public String getMapKey(Integer groupId, Integer accessType) { return groupId.toString() + accessType.toString(); }

Acima, se você tivesse groupId = 1 e accessType = 23, seria a mesma chave de cache que groupId = 12 e accessType = 3. Ao adicionar um caractere separador entre as strings, você pode evitar esse tipo de sobreposição. Mas tenha cuidado com as partes opcionais de uma chave:

 public String getMapKey(String userProvidedString, String extensionName) { return userProvidedString + (extensionName == null ? "" : ("." + extensionName)); }

No exemplo acima, extensionName é uma parte opcional da chave. Se extensionName for opcional, userProvidedString poderá incluir um separador e extensionName válido e obter acesso aos dados de cache aos quais não deveria ter acesso.

Ao usar strings, você deve pensar em como está combinando seus dados para evitar colisões nas chaves. Especialmente em torno de qualquer entrada gerada pelo usuário para a chave.

Use mapas/caches aninhados

Outra opção é não combinar as chaves e, em vez disso, aninhar suas estruturas de dados (Mapas de Mapas de Mapas):

 Map<Integer, Map<String, String>> groupAndLocaleMap = new HashMap<>(); groupAndLocaleMap.computeIfAbsent(userId, k -> new HashMap()).put(userLocale, mapValue);

Isso tem a vantagem de não precisar alocar nenhuma memória nova ao interagir com os mapas, pois os valores passados para as chaves já estão alocados. E embora você precise fazer várias pesquisas para chegar ao valor final, os mapas serão menores.

Mas a desvantagem dessa abordagem é que ela fica mais complicada à medida que o aninhamento se aprofunda. Mesmo com apenas dois níveis, a inicialização do mapa pode parecer confusa. Quando você começa a lidar com 3 ou mais dados, isso pode tornar seu código muito detalhado. Além disso, cada nível requer verificação nula para evitar ponteiros nulos.

Algumas “partes principais” também podem não funcionar bem como chave do mapa. Matrizes ou coleções não possuem métodos iguais padrão que comparam seu conteúdo. Portanto, você precisaria implementá-los ou usar outra alternativa.

O uso de mapas aninhados também pode se tornar menos eficiente em termos de espaço, dependendo de quão único é cada nível de suas chaves.

Crie um objeto-chave composto

A última opção é, em vez de combinar os valores da chave em uma string, criar um objeto personalizado para a chave:

 private class MapKey { private final int userId; private final String userLocale; public MapKey(int userId, String userLocale) { this.userId = userId; this.userLocale = userLocale; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; MapKey mapKey = (MapKey) o; return userId == mapKey.userId && Objects.equals(userLocale, mapKey.userLocale); } @Override public int hashCode() { return Objects.hash(userId, userLocale); } }

Embora cada interação ainda exija uma nova alocação de memória para um novo objeto. A alocação de chave de objeto é significativamente menor que a necessária para uma string composta. A razão para isso é que as partes que compõem a chave não precisam ser realocadas como strings. Em vez disso, apenas a chave do objeto de encapsulamento requer nova memória.

Um objeto de chave composto também pode permitir personalizações nas implementações de igualdade de chave e código hash. Como ignorar a capitalização em uma string ou usar uma matriz ou coleção como parte de uma chave.

A desvantagem aqui é que, novamente, requer muito mais código do que uma string composta. E exige garantir que você tenha contratos iguais e de código hash válidos na classe chave do seu mapa.

Então, qual devo escolher?

De modo geral, eu sugeriria usar uma chave de string composta. É simples e fácil de entender, requer menos código e é mais fácil de depurar posteriormente. Embora seja provavelmente o desempenho mais lento, escrever código simples e legível é geralmente mais importante do que os benefícios que você obteria usando uma das outras duas opções. Lembrar:

“A otimização prematura é a raiz de todos os males” Donald Knuth

Se você não tem evidências ou motivos para acreditar que sua pesquisa de mapa/cache será um gargalo de desempenho, opte pela legibilidade.

Mas se você ESTÁ em um cenário onde o rendimento do seu mapa ou cache é muito alto, então pode ser bom mudar para uma das outras duas opções. Vamos ver como todos os três se comparam em termos de desempenho, bem como em termos de tamanho de alocação de memória.

Para testar os três cenários acima, escrevi um código que replicaria a mesma implementação de todos os três cenários para uma chave composta. A chave em si consiste em um valor inteiro, um valor de string e um valor longo. Todas as três implementações usaram os mesmos dados de teste em cada execução para construir as chaves.

Todas as execuções foram executadas com 1 milhão de registros no mapa (foi usado o hashmap do Java). Foram feitas 3 execuções construindo a chave com diferentes combinações de tamanhos de chave:

• 100 ints, 100 strings, 100 longs — 1 milhão de chaves exclusivas

• 1 int, 1 string, 1.000.000 longs — 1 milhão de chaves exclusivas

• 1.000.000 de ints, 1 string, 1 long — 1 milhão de chaves exclusivas

  
  

Primeiro, vamos ver quanto espaço cada mapa ocupa na pilha. Isso é importante porque afeta a quantidade de memória necessária para executar seu aplicativo.

Há uma observação interessante e óbvia a ser feita aqui: no último cenário (1.000.000 ints), o tamanho dos mapas aninhados é significativamente maior que os outros. Isso ocorre porque, neste cenário, os mapas aninhados criam 1 mapa de primeiro nível com 1 milhão de entradas. Depois, para o segundo e terceiro níveis, cria 1 milhão de mapas com apenas uma entrada.

Todos esses mapas aninhados armazenam sobrecarga extra e estão quase todos vazios. Este é obviamente um caso extremo, mas eu queria mostrá-lo para deixar claro. Ao usar a implementação de mapas de ninho, a exclusividade (e a ordem dessa exclusividade) é muito importante.

Se você inverter a ordem para 1, 1, 1 milhão, obterá o menor requisito de armazenamento.

Nos outros dois cenários, o mapeamento aninhado é o mais eficiente, com o objeto-chave personalizado vindo em segundo lugar e as chaves de string em último.

A seguir, vamos ver o tempo que leva para criar cada um desses mapas do zero:

Novamente, vemos os mapas aninhados apresentando o pior desempenho no cenário 1 milhão-1–1 para alocação de memória, mas mesmo assim, eles superam os outros em tempo de CPU. Acima, também podemos ver como a chave String tem o pior desempenho em todos os casos, enquanto o uso de um objeto de chave personalizado é um pouco mais lento e requer mais alocação de memória do que as chaves aninhadas.

Por último, vejamos o cenário de maior rendimento e quão eficaz é a leitura. Executamos 1 milhão de operações de leitura (1 para cada chave criada); não incluímos nenhuma chave inexistente.

É aqui que realmente vemos o quão lenta é a pesquisa de chave baseada em string. É de longe o mais lento e aloca mais memória de qualquer uma das 3 opções. O objeto-chave personalizado tem um desempenho “próximo” à implementação de mapas aninhados, mas ainda é consistentemente mais lento por uma pequena margem.

No entanto, nas alocações de memória de pesquisa, observe como os mapas aninhados brilham. Não, isso não é uma falha no gráfico; procurar um valor nos mapas aninhados não requer alocações extras de memória para fazer a pesquisa. Como isso é possível?

Bem, ao combinar os objetos compostos em uma chave de string, você precisa alocar memória para um novo objeto de string sempre:

 private String lookup(int key1, String key2, long key3) { return map.get(key1 + "." + key2 + "." + key3); }

Ao usar uma chave composta, você ainda precisa alocar memória para um novo objeto-chave. Mas como os membros desse objeto já foram criados e referenciados, ele ainda aloca muito menos que uma nova string:

 private String lookup(int key1, String key2, long key3) { return map.get(new MapKey(key1, key2, key3)); }

Mas a implementação de mapas aninhados não requer nova alocação de memória na pesquisa. Você está reutilizando as partes fornecidas como chaves para cada um dos mapas aninhados:

 private String lookup(int key1, String key2, long key3) { return map.get(key1).get(key2).get(key3); }

Então, com base no que foi dito acima, qual tem o melhor desempenho?

É fácil ver que os mapas aninhados aparecem em primeiro lugar em quase todos os cenários. Se você procura desempenho bruto na maioria dos casos de uso, esta é provavelmente a melhor opção. Porém, você deve realizar seus próprios testes para confirmar seus casos de uso.

O objeto-chave é uma opção de uso geral muito boa quando mapas aninhados se tornam impraticáveis ou impossíveis de usar em sua implementação. E a chave de string composta, embora mais fácil de implementar, quase sempre será a mais lenta.

O último ponto a considerar ao implementar chaves compostas é que você pode combinar os itens acima. Por exemplo, você poderia usar mapas aninhados para o primeiro ou dois níveis e, em seguida, usar um objeto-chave composto para simplificar os níveis mais profundos.

Isso ainda pode manter seus dados particionados para pesquisas rápidas e, ao mesmo tempo, otimizar o armazenamento e o desempenho da pesquisa. E mantenha seu código legível também.

TLDR;

Na maioria das vezes, mantenha as coisas simples. Combine suas chaves compostas em uma chave de string para armazenamento em um mapa ou cache se essa for a opção mais fácil e o desempenho não for uma grande preocupação.

Em cenários onde o desempenho é crítico, faça seus próprios testes. Mas usar mapas aninhados terá o melhor desempenho na maioria dos casos. Provavelmente também terá os menores requisitos de armazenamento. E as chaves compostas ainda são uma alternativa de alto desempenho quando os mapeamentos de aninhamento se tornam impraticáveis.

Também publicado aqui