Tutorial da estrutura de dados da tabela de hash

Na ciência da computação, a palavra "mapa" significa vincular um item em um conjunto a outro item em outro conjunto. Imagine que em uma página, há palavras em círculo à esquerda e, no lado direito da mesma página, há outro círculo dentro do qual há outras palavras. Suponha que em cada círculo, as palavras sejam escritas aleatoriamente, espalhadas dentro do círculo. Além disso, suponha que as palavras no círculo esquerdo sejam chamadas de teclas, e as palavras no círculo direito são chamadas de valores. Se uma seta for extraída de cada palavra à esquerda para cada palavra à direita, seria dito que as chaves foram mapeadas para os valores.

Suponha que você seja o proprietário de uma grande loja de provisões no condado onde você mora. Suponha que você mora em uma grande área, que não é uma área comercial. Você não é o único com uma loja de provisões na área; Você tem alguns concorrentes. E então ocorre a você que você deve gravar os números de telefone de seus clientes em um livro de exercícios. Obviamente, o livro de exercícios é pequeno e você não pode gravar todos os números de telefone para todos os seus clientes.

Então você decide gravar apenas os números de telefone de seus clientes regulares. E então você tem uma mesa com duas colunas. A coluna à esquerda tem os nomes dos clientes, e a coluna à direita tem os números de telefone correspondentes. Dessa forma, há um mapeamento entre nomes de clientes e números de telefone. A coluna certa da tabela pode ser considerada como a tabela de hash do núcleo. Os nomes dos clientes agora são chamados de teclas e os números de telefone são chamados de valores. Observe que quando um cliente for transferido, você terá que cancelar sua linha, permitindo a linha vazia ou ser substituída pela de um novo cliente regular. Observe também que, com o tempo, o número de clientes regulares pode aumentar ou diminuir e, portanto, a mesa pode crescer ou encolher.

Como outro exemplo de mapeamento, suponha que haja um clube de agricultores em um município. Claro, nem todos os agricultores serão membros do clube. Alguns membros do clube não serão membros regulares (presentes e contribuição). O BAR-MAN pode decidir registrar os nomes dos membros e sua escolha de bebida. Ele desenvolve uma tabela de duas colunas. Na coluna da esquerda, ele escreve os nomes dos membros do clube. Na coluna certa, ele escreve a escolha correspondente de bebida.

Há um problema aqui: há duplicatas na coluna certa. Isto é, o mesmo nome de uma bebida é encontrado mais de uma vez. Em outras palavras, membros diferentes bebem a mesma bebida doce ou a mesma bebida alcoólica, enquanto outros membros bebem uma bebida doce ou alcoólica diferente. O Homem do Bar decide resolver esse problema inserindo uma coluna estreita entre as duas colunas. Nesta coluna do meio, começando de cima, ele numerou as linhas começando de zero (i.e. 0, 1, 2, 3, 4, etc.), descendo, um índice por linha. Com isso, seu problema é resolvido, pois um nome de membro agora mapeia um índice, e não para o nome de uma bebida. Portanto, como uma bebida é identificada por um índice, um nome do cliente é mapeado para o índice correspondente.

Somente a coluna de valores (bebidas) forma a tabela básica de hash. Na tabela modificada, a coluna de índices e seus valores associados (com ou sem duplicatas) formam uma tabela de hash normal - a definição completa de uma tabela de hash é dada abaixo. As chaves (primeira coluna) não fazem necessariamente parte da tabela de hash.

Como outro exemplo novamente, considere um servidor de rede em que um usuário do computador cliente pode adicionar algumas informações, excluir algumas informações ou modificar algumas informações. Existem muitos usuários para o servidor. Cada nome de usuário corresponde a uma senha armazenada no servidor. Aqueles que mantêm o servidor podem ver os nomes de usuário e a senha correspondente e, portanto, poder corromper o trabalho dos usuários.

Portanto, o proprietário do servidor decide produzir uma função que criptografa uma senha antes de ser armazenada. Um usuário faz login no servidor, com sua senha normal compreendida. No entanto, agora, cada senha é armazenada em uma forma criptografada. Se alguém vê uma senha criptografada e tentar fazer login usando -a, ela não funcionará, porque o login recebe uma senha compreendida pelo servidor, e não uma senha criptografada.

Nesse caso, a senha entendida é a chave e a senha criptografada é o valor. Se a senha criptografada estiver em uma coluna de senhas criptografadas, essa coluna é uma tabela básica de hash. Se essa coluna for precedida por outra coluna com índices a partir de zero, para que cada senha criptografada esteja associada a um índice, a coluna da coluna de índices e a coluna de senha criptografada, formem uma tabela de hash normal. As chaves não fazem necessariamente parte da tabela de hash.

Observe, neste caso, que cada chave, que é uma senha entendida, corresponde a um nome de usuário. Portanto, existe um nome de usuário que corresponde a uma chave que é mapeada para um índice, que está associado a um valor que é uma chave criptografada.

A definição de uma função de hash, a definição completa de uma tabela de hash, o significado de uma matriz e outros detalhes são fornecidos abaixo. Você precisa ter conhecimento em ponteiros (referências) e listas vinculadas, a fim de apreciar o restante deste tutorial.

Significado da função de hash e tabela de hash

Variedade

Uma matriz é um conjunto de locais de memória consecutivos. Todos os locais são do mesmo tamanho. O valor no primeiro local é acessado com o índice, 0; O valor no segundo local é acessado com o índice, 1; O terceiro valor é acessado com o índice, 2; quarto com índice, 3; e assim por diante. Uma matriz normalmente não pode aumentar ou encolher. Para alterar o tamanho (comprimento) de uma matriz, uma nova matriz deve ser criada e valores correspondentes copiados para a nova matriz. Os valores de uma matriz são sempre do mesmo tipo.

Função hash

No software, uma função de hash é uma função que leva uma chave e produz um índice correspondente para uma célula de matriz. A matriz é de tamanho fixo (comprimento fixo). O número de chaves é de tamanho arbitrário, geralmente maior que o tamanho da matriz. O índice resultante da função de hash é chamado de valor de hash ou um resumo ou código de hash ou simplesmente um hash.

Tabela de hash

Uma tabela de hash é uma matriz com valores, para cujos índices, as chaves são mapeadas. As chaves são indiretamente mapeadas para os valores. De fato, diz -se que as chaves são mapeadas para os valores, uma vez que cada índice está associado a um valor (com ou sem duplicatas). No entanto, a função que mapeia (eu.e. hashing) relaciona chaves com os índices de matriz e não realmente com os valores, pois pode haver duplicatas nos valores. O diagrama a seguir ilustra uma tabela de hash para os nomes das pessoas e seus números de telefone. As células da matriz (slots) são chamadas de baldes.

Observe que alguns baldes estão vazios. Uma tabela de hash não deve necessariamente ter valores em todos os seus baldes. Os valores nos baldes não devem necessariamente estar em ordem crescente. No entanto, os índices com os quais estão associados estão em ordem crescente. As setas indicam o mapeamento. Observe que as chaves não estão em uma matriz. Eles não precisam estar em nenhuma estrutura. Uma função de hash leva qualquer chave e hashes um índice para uma matriz. Se não houver valor no balde associado ao hashed de índice, um novo valor poderá ser colocado naquele balde. A relação lógica está entre a chave e o índice, e não entre a chave e o valor associado ao índice.

Os valores de uma matriz, como os desta tabela de hash, são sempre do mesmo tipo de dados. Uma tabela de hash (baldes) pode conectar teclas aos valores de diferentes tipos de dados. Nesse caso, os valores da matriz são todos ponteiros, apontando para diferentes tipos de valor.

Uma tabela de hash é uma matriz com uma função de hash. A função pega uma chave e hashes um índice correspondente e, portanto, conecta chaves aos valores, na matriz. As chaves não precisam fazer parte da mesa de hash.

Por que a lista de matriz e não vinculada para a tabela de hash

A matriz para uma tabela de hash pode ser substituída por uma estrutura de dados da lista vinculada, mas haveria um problema. O primeiro elemento de uma lista vinculada é naturalmente no índice, 0; O segundo elemento está naturalmente no índice, 1; O terceiro está naturalmente no índice, 2; e assim por diante. O problema com a lista vinculada é que, para recuperar um valor, a lista deve ser iterada, e isso leva tempo. Acessar um valor em uma matriz é por acesso aleatório. Depois que o índice é conhecido, o valor é obtido sem iteração; Este acesso é mais rápido.

Colisão

A função hash leva uma chave e hashes o índice correspondente, para ler o valor associado ou inserir um novo valor. Se o objetivo é ler um valor, não há problema (sem problemas), até agora. No entanto, se o objetivo é inserir um valor, o índice de hash já poderá ter um valor associado, e isso é uma colisão; O novo valor não pode ser colocado onde já existe um valor. Existem maneiras de resolver colisão - veja abaixo.

Por que a colisão ocorre

No exemplo da loja de provisões acima, os nomes dos clientes são as chaves e os nomes das bebidas são os valores. Observe que os clientes são demais, enquanto a matriz tem um tamanho limitado e não pode levar todos os clientes. Então, apenas as bebidas de clientes regulares são armazenadas na matriz. A colisão ocorreria quando um cliente não regular se torna regular. Os clientes da loja formam um conjunto grande, enquanto o número de baldes para clientes na matriz é limitado.

Com as tabelas de hash, são os valores para as chaves que são muito prováveis, que são registradas. Quando uma chave que não era provável se torna provável, provavelmente haveria uma colisão. De fato, a colisão sempre ocorre com tabelas de hash.

Básico da resolução de colisão

Duas abordagens para a resolução de colisão são chamadas de encadeamento separado e endereçamento aberto. Em teoria, as chaves não devem estar na estrutura de dados ou não devem fazer parte da tabela de hash. No entanto, ambas as abordagens exigem que a coluna chave precede a tabela de hash e se torne parte da estrutura geral. Em vez de as chaves estarem na coluna das chaves, os ponteiros para as chaves podem estar na coluna das chaves.

Uma tabela de hash prática inclui uma coluna de chaves, mas esta coluna chave não faz parte oficialmente da tabela de hash.

Qualquer abordagem para resolução pode ter baldes vazios, não necessariamente no final da matriz.

Encadeamento separado

No encadeamento separado, quando ocorre uma colisão, o novo valor é adicionado à direita (não acima ou abaixo) do valor colidido. Então, dois ou três valores acabam tendo o mesmo índice. Raramente mais de três deveriam ter o mesmo índice.

Mais de um valor pode realmente ter o mesmo índice em uma matriz? - Não. Portanto, em muitos casos, o primeiro valor para o índice é um ponteiro para uma estrutura de dados da lista vinculada, que mantém um, dois ou três valores colididos. O diagrama a seguir é um exemplo de uma tabela de hash para encadeamento separado de clientes e seus números de telefone:

Os baldes vazios estão marcados com a letra x. O restante dos slots tem ponteiros para listas vinculadas. Cada elemento da lista vinculada possui dois campos de dados: um para o nome do cliente e outro para o número de telefone. O conflito ocorre para as chaves: Peter Jones e Suzan Lee. Os valores correspondentes consistem em dois elementos de uma lista vinculada.

Para chaves conflitantes, o critério para inserir valor é o mesmo critério usado para localizar (e ler) o valor.

Endereçamento aberto

Com endereçamento aberto, todos os valores são armazenados na matriz de balde. Quando o conflito ocorre, o novo valor é inserido em um balde vazio novo o valor correspondente para o conflito, após algum critério. O critério usado para inserir um valor em conflito é o mesmo critério usado para localizar (pesquisar e ler) o valor.

O diagrama a seguir ilustra a resolução de conflitos com o endereçamento aberto:

A função de hash leva a chave, Peter Jones e Hashes the Index, 152, e armazena seu número de telefone no balde associado. Depois de algum tempo, a função de hash hashes o mesmo índice, 152 da chave, Suzan Lee, colidindo com o índice de Peter Jones. Para resolver isso, o valor para Suzan Lee é armazenado no balde do próximo índice, 153, que estava vazio. A função de hash hashes o índice, 153 para a chave, Robin Hood, mas esse índice já foi usado para resolver o conflito para uma chave anterior. Portanto, o valor para Robin Hood é colocado no próximo balde vazio, que é o do índice 154.

Métodos de resolução de conflitos para encadeamento separado e endereçamento aberto

O encadeamento separado tem seus métodos de resolução de conflitos, e o endereço aberto também tem seus próprios métodos de resolução de conflitos.

Métodos para resolver conflitos de encadeamento separados

Os métodos para tabelas de hash de encadeamento separados são explicados brevemente agora:

Encadeamento separado com listas vinculadas

Este método é o explicado acima. No entanto, cada elemento da lista vinculado não deve necessariamente ter o campo chave (e.g. Nome do cliente Campo acima).

Encadeamento separado com células da lista

Neste método, o primeiro elemento da lista vinculado é armazenado em um balde da matriz. Isso é possível, se o tipo de dados para a matriz, for o elemento da lista vinculada.

Encadeamento separado com outras estruturas

Qualquer outra estrutura de dados, como a árvore de pesquisa binária de auto -balanceamento que suporta as operações necessárias, pode ser usada no lugar da lista vinculada - veja posteriormente.

Métodos para resolver conflitos de abordagem aberta

Um método para resolver conflitos no endereço aberto é chamado de sequência de sonda. Três seqüências de sonda bem conhecidas são explicadas brevemente agora:

Sondagem linear

Com a investigação linear, quando ocorre um conflito, o balde vazio mais próximo abaixo do balde em conflito é procurado. Além disso, com sondagem linear, a chave e seu valor são armazenadas no mesmo balde.

Sondagem quadrática

Suponha que o conflito ocorra no índice H. O próximo slot vazio (balde) no índice H + 1² é usado; Se isso já estiver ocupado, então o próximo vazio em H + 2² é usado, se isso já estiver ocupado, então o próximo vazio em H + 3² é usado e assim por diante. Existem variantes para isso.

Hash duplo

Com hash duplo, existem duas funções de hash. O primeiro calcula (hashes) o índice. Se ocorrer um conflito, o segundo usa a mesma chave para determinar até que ponto o valor deve ser inserido. Há mais nisso - veja mais tarde.

Função de hash perfeita

Uma função de hash perfeita é uma função de hash que não pode resultar em colisão. Isso pode acontecer quando o conjunto de chaves é relativamente pequeno e cada chave de chave para um número inteiro específico na tabela de hash.

No conjunto de caracteres ASCII, os caracteres maiores podem ser mapeados para as letras minúsculas correspondentes usando uma função de hash. As cartas são representadas na memória do computador como números. No conjunto de caracteres ASCII, A é 65, B é 66, C é 67, etc. e A é 97, B é 98, C é 99, etc. Para mapear de A a A, adicione 32 a 65; Para mapear de B a B, adicione 32 a 66; Para mapear de C a C, adicione 32 a 67; e assim por diante. Aqui, as letras maiúsculas são as chaves e as letras minúsculas são os valores. A tabela de hash para isso pode ser uma matriz cujos valores são os índices associados. Lembre -se, baldes da matriz podem estar vazios. Então, baldes na matriz de 64 a 0 podem estar vazios. A função de hash simplesmente adiciona 32 ao número do código da caixa superior para obter o índice e, portanto, a letra de minúscula. Essa função é uma função de hash perfeita.

Hash dos índices inteiros a inteiros

Existem diferentes métodos para hash de inteiro. Um deles é chamado de método da divisão Modulo (função).

A função de hash da divisão Modulo

Uma função no software de computador não é uma função matemática. Na computação (software), uma função consiste em um conjunto de declarações precedidas por argumentos. Para a função da divisão Modulo, as chaves são inteiros e são mapeadas para os índices da variedade de baldes. O conjunto de chaves é grande; portanto, apenas as chaves que provavelmente ocorrerão na atividade seriam mapeadas. Portanto, as colisões ocorrem quando as chaves improváveis ​​devem ser mapeadas.

Na declaração,

20 /6 = 3r2

20 é o dividendo, 6 é o divisor e 3 restante 2 é o quociente. O restante 2 também é chamado de módulo. Nota: é possível ter um módulo de 0.

Para este hash, o tamanho da tabela geralmente é uma potência de 2, e.g. 64 = 2⁶ ou 256 = 2⁸, etc. O divisor para esta função de hash é um número primo próximo ao tamanho da matriz. Esta função divide a chave pelo divisor e retorna o módulo. O módulo é o índice da matriz de baldes. O valor associado no balde é um valor de sua escolha (valor para a chave).

Chaves de comprimento variável de hashing

Aqui, as chaves do conjunto de chaves são textos de diferentes comprimentos. Inteiros diferentes podem ser armazenados na memória usando o mesmo número de bytes (o tamanho de um personagem em inglês é um byte). Quando as teclas diferentes são de tamanhos de bytes diferentes, diz -se que eles são de comprimento variável. Um dos métodos para comprimentos variáveis ​​de hash é chamado de hash de conversão de radix.

Hash de conversão de radix

Em uma string, cada caractere no computador é um número. Neste método,

Código de hash (índice) = x₀a^{K - 1}+x₁a^{K - 2}+… +X_{K - 2}a¹+x_{K - 1}a⁰

Onde (x0, x1,…, xk - 1) são os caracteres da sequência de entrada e a é uma radix, e.g. 29 (veja mais tarde). k é o número de caracteres na string. Há mais nisso - veja mais tarde.

Chaves e valores

Em um par de chave/valor, um valor pode não ser necessariamente um número ou texto. Também pode ser um recorde. Um registro é uma lista escrita horizontalmente. Em um par de chaves/valor, cada tecla pode realmente estar se referindo a algum outro texto ou número ou registro.

Matriz associativa

Uma lista é uma estrutura de dados, onde os itens da lista estão relacionados e há um conjunto de operações que operam na lista. Cada item da lista pode consistir em um par de itens. A tabela de hash em geral com suas chaves pode ser considerada como uma estrutura de dados, mas é mais um sistema do que uma estrutura de dados. As chaves e seus valores correspondentes não são muito dependentes um do outro. Eles não estão muito relacionados um com o outro.

Por outro lado, uma matriz associativa é uma coisa semelhante, mas as chaves e seus valores são muito dependentes um do outro; Eles estão muito relacionados um com o outro. Por exemplo, você pode ter uma variedade associativa de frutas e suas cores. Cada fruta naturalmente tem sua cor. O nome da fruta é a chave; a cor é o valor. Durante a inserção, cada chave é inserida com seu valor. Ao excluir, cada chave é excluída com seu valor.

Uma matriz associativa é uma estrutura de dados da tabela de hash composta por pares de chave/valor, onde não há duplicata para as chaves. Os valores podem ter duplicados. Nesta situação, as chaves fazem parte da estrutura. Isto é, as chaves precisam ser armazenadas, enquanto que, com a mesa Hast Hast, as chaves não precisam ser armazenadas. O problema dos valores duplicados é naturalmente resolvido pelos índices da matriz de baldes. Não confunda entre valores duplicados e colisão em um índice.

Como uma matriz associativa é uma estrutura de dados, o IS possui pelo menos as seguintes operações:

Operações de matriz associativa

insira ou adicione

Isso insere um novo par de chave/valor na coleção, mapeando a chave para seu valor.

reatribuir

Esta operação substitui o valor de uma chave específica para um novo valor.

exclua ou remova

Isso remove uma chave mais o seu valor correspondente.

olho para cima

Esta operação procura o valor de uma chave específica e retorna o valor (sem removê -lo).

Conclusão

Uma estrutura de dados da tabela de hash consiste em uma matriz e uma função. A função é chamada de função de hash. A função mapeia as teclas dos valores na matriz através dos índices da matriz. As chaves não devem necessariamente fazer parte da estrutura de dados. O conjunto de chaves geralmente é maior que os valores armazenados. Quando ocorre uma colisão, ela é resolvida pela abordagem de encadeamento separada ou pela abordagem de endereçamento aberto. Uma matriz associativa é um caso especial da estrutura de dados da tabela de hash.