| Linha 43: | Linha 43: | ||
= O que são colisões? = | = O que são colisões? = | ||
A função de hash é determinística. A mesma chave de índice sempre é mapeada para o mesmo bucket no índice de hash. | |||
Várias chaves de índice podem ser mapeadas para o mesmo bucket de hash. | |||
Se duas chaves de índice forem mapeadas para o mesmo bucket de hash, haverá uma colisão de hash. Um número grande de colisões | |||
de hash pode afetar o desempenho das operações de leitura. | |||
Colisões não são admitidas em sistemas de criptografias, a solução para estas se dá por meio da utilização de funções hash em conjunto com outras estruturas de dados, como as árvores e as listas. | |||
= Vantagens = | = Vantagens = | ||
Edição das 19h32min de 15 de janeiro de 2015
Pablo
O que são índices hash?
Um índice corresponde a um identificador, utilizado para agilizar o processo de busca de informações, reduzindo o custo de
acesso a uma informação qualquer. A característica essencial de um índice é seu caráter único, que diz que sua escolha deve
corresponder a uma informação única, dentro do conjunto de dados armazenados, que possa servir como referência a esse
conjunto.Um exemplo muito comum, quando se trata da ilustração de índices é o CPF, que se trata um número com 11 dígitos, capaz
de identificar pessoas físicas maiores de 16 anos. “A ideia central do hash é utilizar uma função aplicada sobre a parte da informação (chave), para retornar o índice onde a
informação deve ou deveria estar armazenada”. Sendo assim, uma tabela hash armazenainformações, associando a estas uma chave de
pesquisa, podendo ser representada, por exemplo, por vetores e/ou vetores+listas encadeadas. Uma função hash se encarrega por gerar índices e tratar possíveis colisões (endereços de pesquisa iguais, ou já ocupados),
distribuindo as informações ao longo da tabela.
Os índices são usados como pontos de entrada para tabelas com otimização de memória. A leitura das linhas de uma tabela requer
um índice para localizar os dados na memória. Um índice de hash consiste em uma coleção de buckets organizados em uma matriz. Uma função de hash mapeia chaves de índice para
buckets correspondentes no índice de hash.
Indices Hash, são valores de identificação produzidos através da execução de uma operação numérica, denominada função de
hashing, em um item de dado. O valor identifica de forma exclusiva o item de dado, mas exige um espaço de armazenamento bem
menor. Por isso, o computador pode localizar mais rapidamente os valores de hashing que os itens de dado, que são mais extensos.
Uma tabela de hashing associa cada valor a um item de dado exclusivo.
O que são buckets?
Buckets são unidadee de armazenamento que contém um ou mais registros (tipicamente é um bloco do disco).
O que são colisões?
A função de hash é determinística. A mesma chave de índice sempre é mapeada para o mesmo bucket no índice de hash. Várias chaves de índice podem ser mapeadas para o mesmo bucket de hash. Se duas chaves de índice forem mapeadas para o mesmo bucket de hash, haverá uma colisão de hash. Um número grande de colisões
de hash pode afetar o desempenho das operações de leitura. Colisões não são admitidas em sistemas de criptografias, a solução para estas se dá por meio da utilização de funções hash em conjunto com outras estruturas de dados, como as árvores e as listas.