HashMap Time Complexidade e C ++
Em teoria, uma função de hash converteria dados de qualquer tamanho (qualquer texto grande) em um número inteiro que seja maior ou igual a zero. Diferentes textos grandes são convertidos em números diferentes. O interesse neste artigo não é converter texto grande em um número inteiro. O interesse neste artigo é mapear dados de qualquer tamanho para um número inteiro. Isso inclui a possibilidade de mapear (converter) um único número em outro número único.
Os dados (à esquerda) a serem mapeados são chamados de chaves. Portanto, cada chave é convertida em um número inteiro igual ou maior que zero. Imagine que existem cinco chaves que foram convertidas em números: 0, 1, 2, 3 e 4. Se essas chaves forem os índices de uma matriz com cinco valores do mesmo tipo, essas chaves foram mapeadas para cinco valores diferentes.
E assim, o que é um hashmap (mapa de hash)? Um hashmap é uma estrutura de dados que consiste em pares de chave/valor, onde cada chave foi mapeada para um valor. Na verdade, cada chave foi hash em várias matrizes, e a célula de matriz correspondente é manter um valor. No tópico Hashmap, o local para a célula de cada índice de matriz é chamado de balde.”
Problema de colisão e resolução
Na prática, diferentes chaves podem ser mapeadas para mais de um valor. Considere o caso de dez chaves para uma variedade de comprimentos 5, com 5 baldes. Nesse caso, uma estrutura como uma matriz de marcas seria construída. Cada balde seria realmente uma variedade de comprimento 2. Duas chaves compartilhariam o mesmo balde. Nesse compartilhamento, a primeira chave mapearia para o primeiro elemento da matriz para o balde, e a segunda chave mapearia para o segundo elemento da matriz para o mesmo balde. Este esquema resolve o problema de colisão e dez chaves foram mapeadas para 10 valores, como esperado.
Para o restante deste artigo, imagine um hashmap com o problema de colisão resolvido. O objetivo deste artigo é fornecer a complexidade do tempo da codificação para inserção em um hashmap, codificação de exclusão em um hashmap e codificação para pesquisar em um hashmap. A complexidade do tempo para o hashmap é descrita com esses três recursos. O mapeamento de hash para C ++ também é abordado neste artigo.
Pares de chave/valor e value_type
Imagine um hashmap de nomes de pessoas contra números de telefone para uma diretoria telefônica. Os nomes dos usuários de telefone são do tipo de dados, texto (string). Os valores dos números de telefone são de tipo de dados e texto, assumindo que os espaços e/ou hífens são permitidos em um número de telefone. Os nomes de usuário são as chaves e os números de telefone são os valores. Não se esqueça que, internamente, as chaves são realmente convertidas em índices de matriz na estrutura de dados. Portanto, o tipo de chave é o texto e o tipo de valor ainda é texto.
Tipo de valor significa o par de chaves/valor como um elemento. Em C ++, cada elemento (par) é apontado por um iterador. Então, em C ++, há mapeamento de iterador/par também. Um par (chave e seu valor) é referido como um tipo de valor.
Complexidade do tempo para inserção de hashmap
A complexidade do tempo para um hashmap não se refere ao tempo necessário para criar o hashmap. Refere -se ao tempo necessário para inserir, excluir ou procurar um valor com base em uma determinada chave. A complexidade do tempo é normalmente escrita usando a notação Big-O. A notação Big-O consiste em O na maçaneta, seguida de parênteses. Nos parênteses são variáveis e números, que dão o tempo de execução relativo para um pedaço de código e não necessariamente todo o programa. Com o hashmap, k significa o número de chaves e n significa o número de baldes. Lembre -se de que, com alguns hashmaps, um balde pode ter mais de um valor para chaves correspondentemente diferentes. Nesse caso, mais de uma chave é hashed no mesmo índice de balde. Um bom hashmap resolve esta colisão.
Inserção
Dada uma nova chave, a complexidade do tempo médio para ter a chave e seu valor correspondente inserido em uma estrutura de dados de hashmap é:
O (1 + n/k)Onde n é o número de baldes e k é o número de chaves. Por exemplo, n talvez 10 e k talvez 5. Nesta situação em particular, alguns baldes estão vazios (não têm valor). Portanto, o número de operações seria, 1 + 10/5 = 1 + 2 = 3. Isto é, haveria 3 operações de codificação para inserir um elemento de chave de chave/valor (dada a chave). Dada uma nova chave e valor, a pior complexidade do tempo para ter a chave e seu valor correspondente inserido em uma estrutura de dados de hashmap é:
Sobre)Onde n é o número de baldes para N operações, se o hashmap levar mais de um valor por balde para mais de uma chave, então qualquer tempo extra para inserir um valor adicional no mesmo balde é insignificante e negligenciado.
Eliminação
Dada uma chave que já. A complexidade do tempo médio do caso para a exclusão é:
O (1 + n/k)Onde n é o número de baldes e k é o número de chaves. Por exemplo, n talvez 10 e k talvez 5. Nesta situação em particular, alguns baldes estão vazios (não têm valor). Portanto, o número de operações para o código de exclusão seria, 1 + 10/5 = 1 + 2 = 3. Então, aqui, haveria três operações de codificação para excluir um elemento de par de chaves/valores, dada a chave.
A pior complexidade do tempo para exclusão, dada uma chave, é:
Sobre)Onde n é o número de baldes, portanto, se houver n baldes para a estrutura de dados de hashmap, no limite, levaria 10 operações para excluir um elemento de chave/valor no hashmap.
Procurando
Pesquisar significa encontrar o elemento do par de chaves/valores que possui a chave fornecida, que já deveria estar no hashmap. A complexidade do tempo médio para isso é:
O (1 + n/k)Com os argumentos com os mesmos significados que acima. A pior complexidade do tempo para isso é:
Sobre)Com o argumento tendo o mesmo significado que acima.
C ++ 20
C ++ 20 tem uma aula de hashmap? - Bem, sim, mas não com o nome, hashmap. C ++ 20 possui quatro recipientes associativos não ordenados, que são diferentes formas de classes de hashmap. Os contêineres são: UNODERED_MAP, UNODERED_MULTIMAP, UNODERED_SET e UNODERED_MULTISET. Esses recipientes associativos estão na biblioteca padrão C ++ 20. O contêiner associativo a considerar neste artigo não é ordenado_map. O UNODERED_MAP usa uma função de hash padrão fornecida pela biblioteca padrão C ++.
Para incluir o cabeçalho UNODERED_MAP em um programa, use a diretiva,
#incluirNão use #include, que incluirá o ordenado_map. C ++ não leva #include . O cabeçalho UNODERED_MAP traz a classe UNODEDED_MAP para o programa C ++.
Insira com c++
O segmento de código a seguir na função principal do C ++ inserirá um elemento de chave/valores (nome e número de telefone) no objeto UNODERED_MAP, UMP:
#incluirUNODERED_MAP
ump.inserir ("John Rambo", "555-5555");
Exclua com c++
A sintaxe para excluir um elemento do par de chaves/valores de um objeto não ordenado_map, dada a chave, k, é:
a.Apagar (K)Onde “a” é o objeto não -ordered_map (como o UMP acima), e EASE () é a função de membro não -ordered_map.
Procurando
A sintaxe para pesquisar um elemento de par de chave/value em um objeto UNODEDED_MAP, dada a chave K, que já deveria estar no UNODERED_MAP, é:
b.Encontre (k)Onde B é o objeto não -ordered_map (como o UMP acima), e find () é a função de membro não -ordered_map.
Conclusão
Complexidade do tempo significa tempo de execução relativo para algum código. Embora a complexidade do tempo para criar um hashmap possa ser determinada, ao lidar com o hashmap, a complexidade do tempo é para inserir, excluir e pesquisar tarefas. As complexidades médias e piores do tempo de caso para uma inserção de hashmap bem definida são:
O (1 + n/k)Sobre)
As complexidades médias e piores do tempo de caso para um exclusão bem definido de hashmap são:
O (1 + n/k)Sobre)
As complexidades médias e piores do tempo de caso para uma pesquisa bem definida de hashmap são:
O (1 + n/k)Sobre)