hash table c programs implement hash table
Este tutorial explica tabelas de hash C ++ e mapas de hash. Você também aprenderá sobre aplicativos de tabela de hash e implementação em C ++:
Hashing é uma técnica com a qual podemos mapear uma grande quantidade de dados para uma tabela menor usando uma “função hash”.
Usando a técnica de hashing, podemos pesquisar os dados com mais rapidez e eficiência quando comparados a outras técnicas de pesquisa, como pesquisa linear e binária.
Vamos entender a técnica de hashing com um exemplo neste tutorial.
=> Leia a série de treinamento Easy C ++.
O que você aprenderá:
Hashing em C ++
Tomemos o exemplo de uma biblioteca universitária que abriga milhares de livros. Os livros são organizados de acordo com assuntos, departamentos, etc. Mas, ainda assim, cada seção terá vários livros que tornam a busca por livros muito difícil.
Assim, para superar essa dificuldade, atribuímos um número ou chave única a cada livro, de modo que possamos saber instantaneamente a localização do livro. Na verdade, isso é feito por meio de hashing.
Continuando com nosso exemplo de biblioteca, em vez de identificar cada livro com base em seu departamento, assunto, seção, etc. que pode resultar em uma cadeia muito longa, calculamos um valor inteiro único ou chave para cada livro na biblioteca usando uma função única e armazene essas chaves em uma tabela separada.
A função única mencionada acima é chamada de “Função de hash” e a tabela separada é chamada de “Tabela de hash”. Uma função hash é usada para mapear o valor fornecido para uma chave única específica na tabela de hash. Isso resulta em um acesso mais rápido aos elementos. Quanto mais eficiente for a função de hashing, mais eficiente será o mapeamento de cada elemento para a chave exclusiva.
Vamos considerar uma função hash h (x) que mapeia o valor “ x ' no ' x% 10 ”Na matriz. Para os dados fornecidos, podemos construir uma tabela hash contendo chaves ou códigos Hash ou Hashes, conforme mostrado no diagrama abaixo.
No diagrama acima, podemos ver que as entradas na matriz são mapeadas para suas posições na tabela de hash usando uma função de hash.
Assim, podemos dizer que o hashing é implementado usando duas etapas, conforme mencionado abaixo:
# 1) O valor é convertido em uma chave inteira exclusiva ou hash usando uma função hash. Ele é usado como um índice para armazenar o elemento original, que cai na tabela hash.
No diagrama acima, o valor 1 na tabela hash é a chave exclusiva para armazenar o elemento 1 da matriz de dados fornecida no LHS do diagrama.
#dois) O elemento da matriz de dados é armazenado na tabela hash, onde pode ser recuperado rapidamente usando a chave hash. No diagrama acima, vimos que armazenamos todos os elementos na tabela hash após calcular seus respectivos locais usando uma função hash. Podemos usar as seguintes expressões para recuperar valores de hash e índice.
hash = hash_func(key) index = hash % array_sizeFunção Hash
Já mencionamos que a eficiência do mapeamento depende da eficiência da função hash que usamos.
Uma função hash basicamente deve cumprir os seguintes requisitos:
- Fácil de calcular: Uma função hash deve ser fácil de calcular as chaves exclusivas.
- Menos colisão: Quando os elementos são iguais aos mesmos valores-chave, ocorre uma colisão. Deve haver o mínimo de colisões possível na função hash que é usada. Como as colisões estão prestes a ocorrer, temos que usar técnicas de resolução de colisão apropriadas para cuidar delas.
- Distribuição uniforme: A função de hash deve resultar em uma distribuição uniforme de dados na tabela de hash e, assim, evitar o agrupamento.
Tabela de hash C ++
A tabela de hash ou um mapa de hash é uma estrutura de dados que armazena ponteiros para os elementos da matriz de dados original.
Em nosso exemplo de biblioteca, a tabela hash da biblioteca conterá ponteiros para cada um dos livros da biblioteca.
Ter entradas na tabela hash torna mais fácil procurar um elemento específico na matriz.
Como já vimos, a tabela hash usa uma função hash para calcular o índice na matriz de baldes ou slots usando os quais o valor desejado pode ser encontrado.
Considere outro exemplo com a seguinte matriz de dados:
Suponha que tenhamos uma tabela hash de tamanho 10, conforme mostrado abaixo:
Agora vamos usar a função hash fornecida abaixo.
Hash_code = Key_value % size_of_hash_tableIsso será igual a Hash_code = Key_value% 10
Usando a função acima, mapeamos os valores-chave para os locais da tabela de hash conforme mostrado abaixo.
| Item de dados | Função Hash | Hash_code |
|---|---|---|
| 22 | 22% 10 = 2 | dois |
| 25 | 25% 10 = 5 | 5 |
| 27 | 27% 10 = 7 | 7 |
| 46 | 46% 10 = 6 | 6 |
| 70 | 70% 10 = 0 | 0 |
| 89 | 89% 10 = 9 | 9 |
| 31 | 31% 10 = 1 | 1 |
Usando a tabela acima, podemos representar a tabela hash como segue.
Assim, quando precisamos acessar um elemento da tabela hash, levará apenas O (1) tempo para fazer a pesquisa.
Colisão
Normalmente calculamos o código hash usando a função hash para que possamos mapear o valor da chave para o código hash na tabela hash. No exemplo acima da matriz de dados, vamos inserir um valor 12. Nesse caso, o hash_code para o valor-chave 12 será 2. (12% 10 = 2).
Mas na tabela de hash, já temos um mapeamento para o valor-chave 22 para hash_code 2, conforme mostrado abaixo:
Conforme mostrado acima, temos o mesmo código hash para dois valores, 12 e 22, ou seja, 2. Quando um ou mais valores-chave equivalem ao mesmo local, isso resulta em uma colisão. Assim, a localização do código hash já está ocupada por um valor de chave e há outro valor de chave que precisa ser colocado no mesmo local.
No caso de hashing, mesmo se tivermos uma tabela hash de tamanho muito grande, é provável que haja uma colisão. Isso ocorre porque encontramos um pequeno valor exclusivo para uma grande chave em geral, portanto, é completamente possível que um ou mais valores tenham o mesmo código hash a qualquer momento.
Dado que uma colisão é inevitável no hashing, devemos sempre procurar maneiras de prevenir ou resolver a colisão. Existem várias técnicas de resolução de colisão que podemos empregar para resolver a colisão que ocorre durante o hashing.
Técnicas de resolução de colisão
A seguir estão as técnicas que podemos empregar para resolver a colisão na tabela hash.
faça um endereço de e-mail temporário falso
Encadeamento separado (Hashing aberto)
Esta é a técnica de resolução de colisão mais comum. Isso também é conhecido como hashing aberto e é implementado usando uma lista vinculada.
Na técnica de encadeamento separada, cada entrada na tabela hash é uma lista vinculada. Quando a chave corresponde ao código hash, ela é inserida em uma lista correspondente a esse código hash específico. Portanto, quando duas chaves têm o mesmo código hash, ambas as entradas são inseridas na lista vinculada.
Para o exemplo acima, o encadeamento separado é representado abaixo.
O diagrama acima representa o encadeamento. Aqui usamos a função mod (%). Vemos que, quando dois valores-chave são iguais ao mesmo código hash, vinculamos esses elementos a esse código hash usando uma lista vinculada.
Se as chaves forem distribuídas uniformemente na tabela de hash, o custo médio de pesquisa de uma chave específica depende do número médio de chaves nessa lista vinculada. Assim, o encadeamento separado permanece eficaz mesmo quando há um aumento no número de entradas do que de slots.
O pior caso para encadeamento separado é quando todas as chaves equivalem ao mesmo código hash e, portanto, são inseridas em apenas uma lista vinculada. Portanto, precisamos procurar todas as entradas na tabela hash e o custo que são proporcionais ao número de chaves na tabela.
Sondagem Linear (Endereçamento Aberto / Hashing Fechado)
No endereçamento aberto ou na técnica de teste linear, todos os registros de entrada são armazenados na própria tabela hash. Quando o valor-chave é mapeado para um código hash e a posição apontada pelo código hash está desocupada, o valor-chave é inserido nesse local.
Se a posição já estiver ocupada, então usando uma sequência de sondagem, o valor da chave é inserido na próxima posição que está desocupada na tabela hash.
Para análise linear, a função hash pode mudar conforme mostrado abaixo:
hash = hash% hashTableSize
hash = (hash + 1)% hashTableSize
hash = (hash + 2)% hashTableSize
hash = (hash + 3)% hashTableSize
Vemos que, no caso de sondagem linear, o intervalo entre slots ou sondas sucessivas é constante, ou seja, 1.
No diagrama acima, vemos que no 0ºlocalização, inserimos 10 usando a função hash “hash = hash% hash_tableSize”.
Agora, o elemento 70 também equivale ao local 0 na tabela hash. Mas esse local já está ocupado. Portanto, usando uma sondagem linear, encontraremos o próximo local que é 1. Como este local está desocupado, colocamos a chave 70 neste local como mostrado com uma seta.
A tabela de hash resultante é mostrada abaixo.
A sondagem linear pode apresentar o problema de “Clustering primário”, no qual existe uma chance de que as células contínuas sejam ocupadas e a probabilidade de inserir um novo elemento seja reduzida.
Além disso, se dois elementos obtiverem o mesmo valor na primeira função hash, esses dois elementos seguirão a mesma sequência de teste.
Sondagem Quadrática
O teste quadrático é o mesmo que o teste linear com a única diferença sendo o intervalo usado para o teste. Como o nome sugere, essa técnica usa distância não linear ou quadrática para ocupar slots quando ocorre uma colisão em vez de distância linear.
Na sondagem quadrática, o intervalo entre os slots é calculado adicionando um valor polinomial arbitrário ao índice já hash. Essa técnica reduz o clustering primário de forma significativa, mas não melhora o clustering secundário.
Hashing duplo
A técnica de hashing duplo é semelhante à análise linear. A única diferença entre hashing duplo e sondagem linear é que na técnica de hash duplo o intervalo usado para sondagem é calculado usando duas funções hash. Como aplicamos a função hash à chave, uma após a outra, ela elimina o clustering primário, bem como o clustering secundário.
Diferença entre encadeamento (hash aberto) e sondagem linear (endereçamento aberto)
| Encadeamento (Hashing aberto) | Sondagem Linear (Endereçamento Aberto) |
|---|---|
| Os valores-chave podem ser armazenados fora da tabela usando uma lista vinculada separada. | Os valores-chave devem ser armazenados apenas na tabela. |
| O número de elementos na tabela hash pode exceder o tamanho da tabela hash. | O número de elementos presentes na tabela hash não excederá o número de índices na tabela hash. |
| A exclusão é eficiente na técnica de encadeamento. | A exclusão pode ser complicada. Pode ser evitado se não for necessário. |
| Como uma lista vinculada separada é mantida para cada local, o espaço ocupado é grande. | Como todas as entradas são acomodadas na mesma tabela, o espaço ocupado é menor. |
Implementação de tabela de hash C ++
Podemos implementar hashing usando arrays ou listas vinculadas para programar as tabelas de hash. Em C ++, também temos um recurso chamado “mapa hash”, que é uma estrutura semelhante a uma tabela hash, mas cada entrada é um par de valor-chave. Em C ++ é chamado de mapa hash ou simplesmente um mapa. O mapa de hash em C ++ geralmente não é ordenado.
Há um cabeçalho definido na Standard Template Library (STL) de C ++ que implementa a funcionalidade de mapas. Nós cobrimos STL Maps em detalhes em nosso tutorial sobre STL.
A implementação a seguir é para hash usando as listas vinculadas como uma estrutura de dados para a tabela hash. Também usamos “Chaining” como uma técnica de resolução de colisão nesta implementação.
#include #include using namespace std; class Hashing { int hash_bucket; // No. of buckets // Pointer to an array containing buckets list *hashtable; public: Hashing(int V); // Constructor // inserts a key into hash table void insert_key(int val); // deletes a key from hash table void delete_key(int key); // hash function to map values to key int hashFunction(int x) { return (x % hash_bucket); } void displayHash(); }; Hashing::Hashing(int b) { this->hash_bucket = b; hashtable = new list (hash_bucket); } //insert to hash table void Hashing::insert_key(int key) { int index = hashFunction(key); hashtable(index).push_back(key); } void Hashing::delete_key(int key) { // get the hash index for key int index = hashFunction(key); // find the key in (inex)th list list :: iterator i; for (i = hashtable(index).begin(); i != hashtable(index).end(); i++) { if (*i == key) break; } // if key is found in hash table, remove it if (i != hashtable(index).end()) hashtable(index).erase(i); } // display the hash table void Hashing::displayHash() { for (int i = 0; i ' << x; cout << endl; } } // main program int main() { // array that contains keys to be mapped int hash_array() = {11,12,21, 14, 15}; int n = sizeof(hash_array)/sizeof(hash_array(0)); Hashing h(7); // Number of buckets = 7 //insert the keys into the hash table for (int i = 0; i < n; i++) h.insert_key(hash_array(i)); // display the Hash table cout<<'Hash table created:'< Resultado:
Tabela de hash criada:
0 -> 21 -> 14
1 -> 15
dois
3
4 -> 11
5 -> 12
6
Tabela de hash após exclusão da chave 12:
0 -> 21 -> 14
1 -> 15
dois
3
4 -> 11
5
6
A saída mostra uma tabela hash criada de tamanho 7. Usamos o encadeamento para resolver a colisão. Exibimos a tabela hash após excluir uma das chaves.
Aplicações de Hashing
# 1) Verificação de senhas: A verificação de senhas geralmente é feita usando funções de hash criptográficas. Quando a senha é inserida, o sistema calcula o hash da senha e é enviado ao servidor para verificação. No servidor, os valores de hash das senhas originais são armazenados.
# 2) Estruturas de dados: Diferentes estruturas de dados, como unordered_set e unordered_map em C ++, dicionários em python ou C #, HashSet e hash map em Java, todos usam par de chave-valor em que as chaves são valores únicos. Os valores podem ser iguais para chaves diferentes. O hash é usado para implementar essas estruturas de dados.
# 3) Resumo da mensagem: Este é mais um aplicativo que usa um hash criptográfico. Nos resumos de mensagens, calculamos um hash para os dados enviados e recebidos ou até mesmo para os arquivos e os comparamos com os valores armazenados para garantir que os arquivos de dados não sejam violados. O algoritmo mais comum aqui é “SHA 256”.
# 4) Operação do compilador: Quando o compilador compila um programa, as palavras-chave da linguagem de programação são armazenadas de forma diferente das outras identificações. O compilador usa uma tabela hash para armazenar essas palavras-chave.
# 5) Indexação de banco de dados: As tabelas de hash são usadas para indexação de banco de dados e estruturas de dados baseadas em disco.
# 6) Matrizes associativas: Matrizes associativas são matrizes cujos índices são de tipo de dados diferente de strings do tipo inteiro ou outros tipos de objeto. As tabelas de hash podem ser usadas para implementar matrizes associativas.
Conclusão
O hash é a estrutura de dados mais amplamente usada, pois leva um tempo constante O (1) para as operações de inserção, exclusão e pesquisa. O hash é implementado principalmente usando uma função hash que calcula um valor de chave menor exclusivo para grandes entradas de dados. Podemos implementar hashing usando matrizes e listas vinculadas.
Sempre que uma ou mais entradas de dados equivalem aos mesmos valores de chaves, isso resulta em uma colisão. Vimos várias técnicas de resolução de colisão, incluindo teste linear, encadeamento, etc. Vimos também a implementação de hashing em C ++.
Para concluir, podemos dizer que o hashing é de longe a estrutura de dados mais eficiente no mundo da programação.
=> Procure toda a série de treinamento C ++ aqui.
Leitura recomendada
- Como escrever cenários complexos de teste de lógica de negócios usando a técnica da tabela de decisão
- Tabela de validação de campo (FVT): uma técnica de design de teste para validação de campo
- QTP Tutorial # 15 - Usando área de texto, tabela e pontos de verificação da página no QTP
- MAPS em STL
- Tudo sobre roteadores: tipos de roteadores, tabela de roteamento e roteamento IP
- As 40 melhores perguntas e respostas para entrevistas em MySQL (2.021 perguntas)
- 90 principais perguntas e respostas da entrevista SQL (mais recentes)
- Comandos dos programas de utilitários do Unix: Qual, Man, Find Su, Sudo (Parte D)