c++ - unsorted - unordered_set



Como std:: unordered_map é implementado (1)

Manipulação de colisão c ++ unordered_map, redimensionar e refazer

Esta é uma pergunta anterior aberta por mim e vi que estou tendo muita confusão sobre como o unordered_map é implementado. Tenho certeza de que muitas outras pessoas compartilham essa confusão comigo. Com base nas informações que conheço sem ler o padrão:

Toda implementação unordered_map armazena uma lista vinculada a nós externos na matriz de buckets ... Não, essa não é a maneira mais eficiente de implementar um mapa de hash para os usos mais comuns. Infelizmente, uma pequena "supervisão" na especificação de unordered_map praticamente exige esse comportamento. O comportamento necessário é que os iteradores dos elementos devem permanecer válidos ao inserir ou excluir outros elementos

Eu esperava que alguém explicasse a implementação e como ela se encaixa na definição padrão C ++ (em termos de requisitos de desempenho) e se realmente não é a maneira mais eficiente de implementar uma estrutura de dados de mapa de hash, como ela pode ser melhorada?


O Standard exige efetivamente as implementações std::unordered_set e std::unordered_map que usam hash aberto, o que significa uma matriz de buckets, cada um dos quais mantém o cabeçalho de uma lista lógica (e geralmente real). Esse requisito é sutil: é uma conseqüência do fator de carga máxima padrão ser 1,0 e da garantia de que a tabela não seja reformulada, a menos que cresça além desse fator de carga: isso seria impraticável sem encadeamento, pois as colisões com hash fechado tornam-se avassaladoras. o fator de carga se aproxima de 1:

23.2.5 / 15: Os membros de insert e substituição não afetarão a validade dos iteradores se (N+n) < z * B , onde N é o número de elementos no contêiner antes da operação de inserção, n é o número de elementos inseridos, B é a contagem de baldes do contêiner e z é o fator de carga máxima do contêiner.

entre os efeitos do construtor em 23.5.4.2/1: max_load_factor() retorna 1.0 .

(Para permitir a iteração ideal sem passar sobre os buckets vazios, a implementação do GCC preenche os buckets com iteradores em uma única lista vinculada individual, com todos os valores: os iteradores apontam para o elemento imediatamente antes dos elementos do bucket, para que o próximo ponteiro possa ser religado se estiver apagando o último valor do balde.)

Em relação ao texto que você cita:

Não, essa não é a maneira mais eficiente de implementar um mapa de hash para os usos mais comuns. Infelizmente, uma pequena "supervisão" na especificação de unordered_map praticamente exige esse comportamento. O comportamento necessário é que os iteradores dos elementos devem permanecer válidos ao inserir ou excluir outros elementos

Não há "supervisão" ... o que foi feito foi muito deliberado e realizado com plena consciência. É verdade que outros compromissos poderiam ter sido atingidos, mas a abordagem de hash / encadeamento aberto é um compromisso razoável para uso geral, que lida razoavelmente com elegância com colisões de funções de hash medíocres, não é muito dispendioso com tipos de chave / valor pequenos ou grandes, e lida arbitrariamente - muitos pares de insert / erase sem degradar gradualmente o desempenho, como fazem muitas implementações de hash fechado.

Como evidência da conscientização, da proposta de Matthew Austern aqui :

Não estou ciente de nenhuma implementação satisfatória de endereçamento aberto em uma estrutura genérica. O endereçamento aberto apresenta vários problemas:

• É necessário distinguir entre uma posição vaga e uma ocupada.

• É necessário restringir a tabela de hash a tipos com um construtor padrão e construir todos os elementos da matriz com antecedência, ou então manter uma matriz com alguns dos quais elementos são objetos e outros com memória bruta.

• O endereçamento aberto dificulta o gerenciamento de colisões: se você estiver inserindo um elemento cujo código de hash mapeia para um local já ocupado, precisará de uma política que indique onde tentar em seguida. Este é um problema resolvido, mas as soluções mais conhecidas são complicadas.

• O gerenciamento de colisões é especialmente complicado quando a exclusão de elementos é permitida. (Veja Knuth para uma discussão.) Uma classe de contêiner para a biblioteca padrão deve permitir o apagamento.

• Os esquemas de gerenciamento de colisão para endereçamento aberto tendem a assumir uma matriz de tamanho fixo que pode conter até N elementos. Uma classe de contêiner para a biblioteca padrão deve poder crescer conforme necessário quando novos elementos são inseridos, até o limite da memória disponível.

A solução desses problemas pode ser um projeto de pesquisa interessante, mas, na ausência de experiência de implementação no contexto de C ++, seria inadequado padronizar uma classe de contêiner de endereço aberto.

Especificamente para tabelas somente de inserção com dados pequenos o suficiente para armazenar diretamente nos buckets, um valor sentinela conveniente para buckets não utilizados e uma boa função de hash, uma abordagem de hash fechado pode ser aproximadamente uma ordem de magnitude mais rápida e usar muito menos memória, mas isso não é objetivo geral.

Uma comparação e elaboração completas das opções de design da tabela de hash e suas implicações estão fora de tópico para o SO, pois é muito amplo para abordar corretamente aqui.





unordered-map