Explicação sobre hashing e seu uso para a compressão de dados

Question

Eu estou enfrentando um aplicativo que usa hash, mas não posso ainda descobrir como ele funciona. Aqui está o meu problema, hash é usado para gerar algum índice, e com esses índices I acesso a tabelas diferentes, e depois que eu adicionar o valor de cada mesa que eu me utilizando os índices e com isso eu recebo o meu valor final. Isso é feito para reduzir os requisitos de memória. A entrada para a função hash está fazendo o XOR entre um número constante aleatória e alguns parâmetros da aplicação.

Esta é uma aplicação hashing típico ?. A única coisa que eu não entendo é como usando hashing podemos reduzir os requisitos de memória ?. Alguém pode esclarecer isso?.

Obrigado

Answer 1

Hash sozinho não tem nada a ver com a memória.

O que é muitas vezes usado para um hashtable. Hashtables trabalho calculando o de hash do que você está digitando fora, que é então utilizado como um índice em uma estrutura de dados.

Hashing permite reduzir a chave (string, etc.) em um valor mais compacto como um inteiro ou conjunto de bits.

Isso pode ser a poupança de memória que você está se referindo -. Reduzindo uma grande chave para um inteiro simples

Note, porém, que os hashes não são únicos! Um bom algoritmo de hash minimiza colisões, mas eles não têm a intenção de reduzir para um valor exclusivo - isso não é possível (por exemplo, se o seu de hash gera um número inteiro de 32 bits, o haxixe teria apenas 2 ^ 32 valores únicos)

Answer 2

É um href="http://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow noreferrer"> bloom filtro você está falando? Este usa funções hash para obter uma forma eficiente do espaço à participação de teste de um conjunto. Se sim, então veja o link para uma explicação.

Answer 3

A maioria das implementações boa fritas são a memória ineficiente, caso contrário não haveria mais computação envolvidos -. E que seria exatamente estar faltando o ponto de hashing

implementações de hash são utilizados para o processamento de eficiência, como eles vão lhe fornecer constante tempo de execução para operações como a inserção, remoção e recuperação.

Você pode pensar sobre a qualidade de hashing de uma forma que todos os seus dados, não importa o tipo ou tamanho, é sempre representado em uma única forma de comprimento fixo.

Answer 4

Isto poderia ser explicado se o hash que está sendo feito não é para construir uma tabela hash verdade, mas é apenas para criar um índice em uma tabela bloco corda / memória. Se você tivesse a (ou sequência de memória) mesma cadeia 20 vezes em seus dados, e você, em seguida, substituiu todos os 20 casos desta cadeia com apenas o seu índice hash / mesa, você poderia conseguir a compressão de dados dessa forma. Se há uma cadeia de colisão real contida nessa tabela para cada valor hash, no entanto, então o que eu acabei de descrever não é o que está acontecendo; nesse caso, a razão para o hashing seria provavelmente para acelerar a execução (fornecendo acesso rápido a valores armazenados), ao invés de compressão.