Sondagem linear - Linear probing

A colisão entre John Smith e Sandra Dee (ambos com hashing para a célula 873) é resolvida colocando Sandra Dee no próximo local livre, a célula 874.

A análise linear é um esquema em programação de computador para resolver colisões em tabelas hash , estruturas de dados para manter uma coleção de pares chave-valor e procurar o valor associado a uma determinada chave. Foi inventado em 1954 por Gene Amdahl , Elaine M. McGraw e Arthur Samuel e analisado pela primeira vez em 1963 por Donald Knuth .

Junto com o teste quadrático e o hashing duplo , o teste linear é uma forma de endereçamento aberto . Nesses esquemas, cada célula de uma tabela hash armazena um único par chave-valor. Quando a função hash causa uma colisão mapeando uma nova chave para uma célula da tabela hash que já está ocupada por outra chave, a análise linear procura na tabela o local livre seguinte mais próximo e insere a nova chave lá. As pesquisas são realizadas da mesma forma, pesquisando a tabela sequencialmente a partir da posição fornecida pela função hash, até encontrar uma célula com uma chave correspondente ou uma célula vazia.

Como escrevem Thorup & Zhang (2012) , "as tabelas de hash são as estruturas de dados não triviais mais comumente usadas, e a implementação mais popular em hardware padrão usa sondagem linear, que é rápida e simples." A análise linear pode fornecer alto desempenho por causa de sua boa localidade de referência , mas é mais sensível à qualidade de sua função hash do que alguns outros esquemas de resolução de colisão. Leva um tempo constante esperado por pesquisa, inserção ou exclusão quando implementado usando uma função hash aleatória, uma função hash independente 5 ou hash de tabulação . Bons resultados também podem ser obtidos na prática com outras funções hash, como MurmurHash .

Operações

A análise linear é um componente dos esquemas de endereçamento aberto para usar uma tabela hash para resolver o problema do dicionário . No problema do dicionário, uma estrutura de dados deve manter uma coleção de pares de valores-chave sujeitos a operações que inserem ou excluem pares da coleção ou que procuram o valor associado a uma determinada chave. Em soluções de endereçamento aberto para esse problema, a estrutura de dados é uma matriz $T$ (a tabela hash) cujas células $T [i]$ (quando não vazias) armazenam, cada uma, um único par chave-valor. Uma função hash é usada para mapear cada chave na célula de $T$ onde essa chave deve ser armazenada, normalmente embaralhando as chaves de modo que as chaves com valores semelhantes não sejam colocadas próximas umas das outras na tabela. Uma colisão de hash ocorre quando a função hash mapeia uma chave em uma célula que já está ocupada por uma chave diferente. A sondagem linear é uma estratégia para resolver colisões, colocando a nova chave na célula vazia seguinte mais próxima.

Procurar

Para pesquisar uma determinada chave $x$ , as células de $T$ são examinadas, começando com a célula no índice $h (x)$ (onde $h$ é a função hash) e continuando para as células adjacentes $h (x) + 1$ , $h (x) + 2$ , ..., até encontrar uma célula vazia ou uma célula cuja chave armazenada é $x$ . Se uma célula que contém a chave for encontrada, a pesquisa retorna o valor dessa célula. Caso contrário, se uma célula vazia for encontrada, a chave não pode estar na tabela, porque ela teria sido colocada nessa célula em preferência a qualquer célula posterior que ainda não tenha sido pesquisada. Nesse caso, a pesquisa retorna como resultado que a chave não está presente no dicionário.

Inserção

Para inserir um par de valores-chave $(x, v)$ na tabela (possivelmente substituindo qualquer par existente pela mesma chave), o algoritmo de inserção segue a mesma sequência de células que seria seguida para uma pesquisa, até encontrar uma célula vazia ou uma célula cuja chave armazenada é $x$ . O novo par de valores-chave é então colocado nessa célula.

Se a inserção fizer com que o fator de carga da tabela (sua fração de células ocupadas) cresça acima de algum limite predefinido, toda a tabela pode ser substituída por uma nova tabela, maior por um fator constante, com uma nova função hash, como em uma matriz dinâmica . Definir esse limite próximo a zero e usar uma alta taxa de crescimento para o tamanho da tabela leva a operações de hash table mais rápidas, mas maior uso de memória do que valores de limite próximos a um e taxas de crescimento baixas. Uma escolha comum seria dobrar o tamanho da mesa quando o fator de carga excedesse 1/2, fazendo com que o fator de carga ficasse entre 1/4 e 1/2.

Eliminação

Quando um par de valores-chave é excluído, pode ser necessário mover outro par de volta para sua célula, para evitar que pesquisas pela chave movida encontrem uma célula vazia.

Também é possível remover um par de valores-chave do dicionário. No entanto, não é suficiente simplesmente esvaziar a célula. Isso afetaria as pesquisas de outras chaves que possuem um valor hash anterior à célula esvaziada, mas que são armazenadas em uma posição posterior à célula esvaziada. A célula esvaziada faria com que essas pesquisas relatassem incorretamente que a chave não está presente.

Em vez disso, quando uma célula $i$ é esvaziada, é necessário pesquisar as células seguintes da tabela até encontrar outra célula vazia ou uma chave que pode ser movida para a célula $i$ (ou seja, uma chave cujo valor hash é igual a ou antes de $i$ ). Quando uma célula vazia é encontrada, esvaziar a célula $i$ é seguro e o processo de exclusão termina. Mas, quando a pesquisa encontra uma chave que pode ser movida para a célula $i$ , ela executa esse movimento. Isso tem o efeito de acelerar as buscas posteriores pela chave movida, mas também esvazia outra célula, mais tarde no mesmo bloco de células ocupadas. A busca por uma chave móvel continua para a nova célula vazia, da mesma forma, até que termina ao atingir uma célula que já estava vazia. Nesse processo de mover chaves para células anteriores, cada chave é examinada apenas uma vez. Portanto, o tempo para concluir todo o processo é proporcional ao comprimento do bloco de células ocupadas que contém a chave excluída, correspondendo ao tempo de execução das outras operações da tabela hash.

Alternativamente, é possível usar uma estratégia de exclusão preguiçosa na qual um par de valor-chave é removido substituindo o valor por um valor de sinalizador especial indicando uma chave excluída. No entanto, esses valores de sinalizador contribuirão para o fator de carga da tabela hash. Com essa estratégia, pode ser necessário limpar os valores dos sinalizadores do array e refazer todos os pares de chave-valor restantes, uma vez que uma fração muito grande do array é ocupada por chaves deletadas.

Propriedades

A análise linear fornece boa localidade de referência , o que faz com que exija poucos acessos à memória não armazenada em cache por operação. Por causa disso, para fatores de carga baixos a moderados, ele pode fornecer um desempenho muito alto. No entanto, em comparação com algumas outras estratégias de endereçamento aberto, seu desempenho se degrada mais rapidamente em altos fatores de carga por causa do clustering primário , uma tendência de uma colisão causar mais colisões próximas. Além disso, obter um bom desempenho com este método requer uma função hash de qualidade superior do que para alguns outros esquemas de resolução de colisão. Quando usado com funções hash de baixa qualidade que falham em eliminar não uniformidades na distribuição de entrada, a análise linear pode ser mais lenta do que outras estratégias de endereçamento aberto, como hash duplo , que testa uma sequência de células cuja separação é determinada por uma segunda função hash, ou sondagem quadrática , onde o tamanho de cada etapa varia dependendo de sua posição dentro da sequência da sonda.

Análise

Usando a análise linear, as operações de dicionário podem ser implementadas em tempo constante esperado . Em outras palavras, as operações de inserção, remoção e pesquisa podem ser implementadas em O (1) , desde que o fator de carga da tabela hash seja uma constante estritamente menor que um.

Em mais detalhes, o tempo para qualquer operação específica (uma pesquisa, inserção ou exclusão) é proporcional ao comprimento do bloco contíguo de células ocupadas no qual a operação começa. Se todas as células iniciais forem igualmente prováveis, em uma tabela hash com $N$ células, então um bloco máximo de $k$ células ocupadas terá probabilidade $k / N$ de conter a localização inicial de uma pesquisa e levará tempo $O (k)$ sempre que for o local de partida. Portanto, o tempo esperado para uma operação pode ser calculado como o produto desses dois termos, $O (k 2 / N)$ , somado a todos os blocos máximos de células contíguas na tabela. Uma soma semelhante de comprimentos de bloco quadrados dá o limite de tempo esperado para uma função hash aleatória (em vez de uma localização inicial aleatória em um estado específico da tabela hash), somando todos os blocos que poderiam existir (em vez dos que realmente existem em um determinado estado da tabela), e multiplicando o termo para cada bloco potencial pela probabilidade de que o bloco esteja realmente ocupado. Ou seja, definindo $Bloco (i, k)$ como o evento em que existe um bloco contíguo máximo de células ocupadas de comprimento $k$ começando no índice $i$ , o tempo esperado por operação é

{\ displaystyle E [T] = O (1) + \ sum _ {i = 1} ^ {N} \ sum _ {k = 1} ^ {n} O (k ^ {2} / N) \ operatorname { Pr} [\ operatorname {Bloco} (i, k)].}

Esta fórmula pode ser simplificada substituindo $Block (i, k)$ por uma condição necessária mais simples $Full (k)$ , o evento em que pelo menos $k$ elementos têm valores de hash que estão dentro de um bloco de células de comprimento $k$ . Após essa substituição, o valor dentro da soma não depende mais de $i$ , e o fator $1 / N$ cancela os $N$ termos da soma externa. Essas simplificações levam ao limite

{\ displaystyle E [T] \ leq O (1) + \ sum _ {k = 1} ^ {n} O (k ^ {2}) \ operatorname {Pr} [\ operatorname {Full} (k)]. }

Mas pela forma multiplicativa do limite de Chernoff , quando o fator de carga é afastado de um, a probabilidade de que um bloco de comprimento $k$ contenha pelo menos $k$ valores hash é exponencialmente pequena em função de $k$ , fazendo com que essa soma seja limitada por uma constante independente de $n$ . Também é possível realizar a mesma análise usando a aproximação de Stirling em vez do limite de Chernoff para estimar a probabilidade de que um bloco contenha exatamente $k$ valores hash.

Em termos do fator de carga $α$ , o tempo esperado para uma pesquisa bem-sucedida é $O (1 + 1 / (1 - α))$ , e o tempo esperado para uma pesquisa malsucedida (ou a inserção de uma nova chave) é $O (1 + 1 / (1 - α) 2)$ . Para fatores de carga constantes, com alta probabilidade, a sequência de teste mais longa (entre as sequências de teste para todas as chaves armazenadas na tabela) tem comprimento logarítmico.

Escolha da função hash

Como a análise linear é especialmente sensível a valores de hash distribuídos de maneira desigual, é importante combiná-la com uma função de hash de alta qualidade que não produza tais irregularidades.

A análise acima assume que o hash de cada chave é um número aleatório independente dos hashes de todas as outras chaves. Essa suposição não é realista para a maioria das aplicações de hashing. No entanto, valores de hash aleatórios ou pseudo - aleatórios podem ser usados ao fazer hash de objetos por sua identidade em vez de por seu valor. Por exemplo, isso é feito usando análise linear pela classe IdentityHashMap da estrutura de coleções Java . O valor hash que essa classe associa a cada objeto, seu identityHashCode, tem garantia de permanecer fixo durante o tempo de vida de um objeto, mas, de outra forma, é arbitrário. Como o identityHashCode é construído apenas uma vez por objeto e não precisa ser relacionado ao endereço ou valor do objeto, sua construção pode envolver cálculos mais lentos, como a chamada para um gerador de número aleatório ou pseudo-aleatório. Por exemplo, o Java 8 usa um gerador de números pseudo-aleatórios Xorshift para construir esses valores.

Para a maioria das aplicações de hashing, é necessário computar a função hash para cada valor sempre que ele é hash, em vez de uma vez quando seu objeto é criado. Em tais aplicações, números aleatórios ou pseudoaleatórios não podem ser usados como valores hash, porque então objetos diferentes com o mesmo valor teriam hashes diferentes. E as funções hash criptográficas (que são projetadas para serem computacionalmente indistinguíveis das funções verdadeiramente aleatórias) são geralmente muito lentas para serem usadas em tabelas hash. Em vez disso, outros métodos para construir funções hash foram concebidos. Esses métodos calculam a função hash rapidamente e podem funcionar bem com sondagem linear. Em particular, a sondagem linear foi analisada a partir da estrutura de hashing independente de $k$ , uma classe de funções hash que são inicializadas a partir de uma pequena semente aleatória e que têm a mesma probabilidade de mapear qualquer $k$ -tuple de chaves distintas para qualquer $k$ -tuple de índices. O parâmetro $k$ pode ser considerado uma medida da qualidade da função hash: quanto maior for $k$ , mais tempo levará para calcular a função hash, mas ela se comportará de forma mais semelhante a funções completamente aleatórias. Para a análise linear, a independência 5 é suficiente para garantir o tempo esperado constante por operação, enquanto algumas funções hash 4 independentes têm um desempenho ruim, levando até tempo logarítmico por operação.

Outro método de construir funções hash com alta qualidade e velocidade prática é o hash de tabulação . Neste método, o valor hash de uma chave é calculado usando cada byte da chave como um índice em uma tabela de números aleatórios (com uma tabela diferente para cada posição de byte). Os números dessas células da tabela são então combinados por um exclusivo bit a bit ou operação. As funções hash construídas dessa maneira são apenas 3 independentes. No entanto, o teste linear usando essas funções hash leva um tempo esperado constante por operação. Tanto o hash de tabulação quanto os métodos padrão para gerar funções de hash independentes de 5 são limitados a chaves com um número fixo de bits. Para lidar com strings ou outros tipos de chaves de comprimento variável, é possível compor uma técnica de hash universal mais simples que mapeia as chaves para valores intermediários e uma função hash de qualidade superior (5 independentes ou tabulação) que mapeia os valores intermediários para a tabela de hash índices.

Em uma comparação experimental, Richter et al. descobriram que a família Multiply-Shift de funções hash (definida como ) era "a função hash mais rápida quando integrada com todos os esquemas de hash, ou seja, produzindo os maiores rendimentos e também de boa qualidade", enquanto o hash de tabulação produzia "o menor rendimento". Eles ressaltam que cada consulta de tabela requer vários ciclos, sendo mais cara do que operações aritméticas simples. Eles também descobriram que MurmurHash é superior ao hashing de tabulação: "Ao estudar os resultados fornecidos por Mult e Murmur, pensamos que a compensação por tabulação (...) é menos atraente na prática". ${\ displaystyle h_ {z} (x) = (x \ cdot z {\ bmod {2}} ^ {w}) \ div 2 ^ {wd}}$

História

A ideia de uma matriz associativa que permite que os dados sejam acessados por seu valor e não por seu endereço remonta a meados da década de 1940 na obra de Konrad Zuse e Vannevar Bush , mas as tabelas hash não foram descritas até 1953, em um memorando da IBM por Hans Peter Luhn . Luhn usou um método de resolução de colisão diferente, encadeamento, em vez de sondagem linear.

Knuth ( 1963 ) resume a história inicial da sondagem linear. Foi o primeiro método de endereçamento aberto e originalmente era sinônimo de endereçamento aberto. De acordo com Knuth, foi usado pela primeira vez por Gene Amdahl , Elaine M. McGraw (nascida Boehme) e Arthur Samuel em 1954, em um programa assembler para o computador IBM 701 . A primeira descrição publicada de sondagem linear é de Peterson (1957) , que também credita Samuel, Amdahl e Boehme, mas acrescenta que "o sistema é tão natural que muito provavelmente pode ter sido concebido independentemente por outros antes ou depois daquela época " Outra publicação inicial desse método foi do pesquisador soviético Andrey Ershov , em 1958.

A primeira análise teórica de sondagem linear, mostrando que leva tempo constante esperado por operação com funções hash aleatórias, foi dada por Knuth. Sedgewick chama o trabalho de Knuth de "um marco na análise de algoritmos". Desenvolvimentos posteriores significativos incluem uma análise mais detalhada da distribuição de probabilidade do tempo de execução e a prova de que a sondagem linear é executada em tempo constante por operação com funções hash utilizáveis na prática, em vez das funções aleatórias idealizadas assumidas pela análise anterior.

Languages

In other projects