Sondagem quadrática - Quadratic probing

A sondagem quadrática é um esquema de endereçamento aberto em programação de computador para resolver colisões hash em tabelas hash . A sondagem quadrática opera tomando o índice hash original e adicionando valores sucessivos de um polinômio quadrático arbitrário até que um slot aberto seja encontrado.

Um exemplo de sequência usando sondagem quadrática é:

${\ displaystyle H + 1 ^ {2}, H + 2 ^ {2}, H + 3 ^ {2}, H + 4 ^ {2}, ..., H + k ^ {2}}$

A sondagem quadrática pode ser um algoritmo mais eficiente em uma tabela de endereçamento aberta , pois evita melhor o problema de agrupamento que pode ocorrer com a sondagem linear , embora não seja imune. Ele também fornece um bom armazenamento em cache de memória porque preserva alguma localidade de referência ; no entanto, a análise linear tem maior localidade e, portanto, melhor desempenho do cache.

Função quadrática

Seja h ( k ) uma função hash que mapeia um elemento k para um inteiro em [0,  m −1], onde m é o tamanho da tabela. Deixe a i- ^ésima posição da sonda para um valor k ser dada pela função

${\ displaystyle h (k, i) = h (k) + c_ {1} i + c_ {2} i ^ {2} {\ pmod {m}}}$

onde c ₂ ≠ 0 (Se c ₂ = 0, então h ( k , i ) se degrada em uma sonda linear ). Para uma determinada tabela hash , os valores de c ₁ e c ₂ permanecem constantes.

Exemplos:

• Se , então, a sequência da sonda será${\ displaystyle h (k, i) = (h (k) + i + i ^ {2}) {\ pmod {m}}}$${\ displaystyle h (k), h (k) + 2, h (k) +6, ...}$
• Para m = 2 ⁿ , uma boa escolha para as constantes são c ₁ = c ₂ = 1/2, pois os valores de h ( k , i ) para i em [0,  m −1] são todos distintos. Isso leva a uma sequência de teste de (os números triangulares ), onde os valores aumentam em 1, 2, 3, ...${\ displaystyle h (k), h (k) + 1, h (k) + 3, h (k) +6, ...}$
• Para primos m > 2, a maioria das escolhas de c ₁ e c ₂ tornará h ( k , i ) distinto para i em [0, ( m −1) / 2]. Essas escolhas incluem c ₁ = c ₂ = 1/2, c ₁ = c ₂ = 1 e c ₁ = 0, c ₂ = 1. No entanto, existem apenas m / 2 sondas distintas para um determinado elemento, exigindo outras técnicas para garantir que as inserções serão bem-sucedidas quando o fator de carga exceder 1/2.
• Pois , onde m , n e p são inteiros maiores ou iguais a 2 (degrada para a sonda linear quando p = 1), então dá o ciclo de todas as sondas distintas. Pode ser calculado em loop como:, e${\ displaystyle m = n ^ {p}}$${\ displaystyle h (k, i) = (h (k) + i + ni ^ {2}) {\ pmod {m}}}$${\ displaystyle h (k, 0) = h (k)}$${\ displaystyle h (k, i + 1) = (h (k, i) + 2in + n + 1) {\ pmod {m}}}$
• Para qualquer m , o ciclo completo com sondagem quadrática pode ser alcançado arredondando-se m para a potência mais próxima de 2, calcule o índice de sondagem: e pule a iteração quando . Há um máximo de iterações ignoradas e essas iterações não se referem à memória, portanto, é uma operação rápida na maioria dos processadores modernos. O arredondamento de m pode ser calculado por:${\ displaystyle h (k, i) = h (k) + ((i ^ {2} + i) / 2) {\ pmod {roundUp2 (m)}}}$${\ displaystyle h (k, i)> = m}$${\ displaystyle roundUp2 (m) -m <m / 2}$

uint64_t roundUp2(uint64_t v){
	v--;
	v |= v >> 1;
	v |= v >> 2;
	v |= v >> 4;
	v |= v >> 8;
	v |= v >> 16;
	v |= v >> 32;
	v++;
	return v;
}

Limitações

Ao usar sondagem quadrática, no entanto (com exceção de casos de números triangulares para uma tabela hash de tamanho ), não há garantia de encontrar uma célula vazia uma vez que a tabela fique mais da metade cheia, ou mesmo antes disso, se o tamanho da tabela for composto , porque as colisões devem ser resolvidas usando metade da tabela, no máximo. ${\ displaystyle 2 ^ {n}}$

O inverso disso pode ser provado como tal: Suponha que uma tabela hash tenha tamanho (um primo maior que 3), com uma localização inicial e duas localizações alternativas e (onde e ). Se esses dois locais apontam para o mesmo espaço-chave, mas , então ${\ displaystyle p}$${\ displaystyle h (k)}$${\ displaystyle h (k) + x ^ {2} {\ pmod {p}}}$${\ displaystyle h (k) + y ^ {2} {\ pmod {p}}}$${\ displaystyle 0 \ leq x}$${\ displaystyle y \ leq p / 2}$${\ displaystyle x \ neq y}$

${\ displaystyle h (k) + x ^ {2} = h (k) + y ^ {2} {\ pmod {p}}}$

${\ displaystyle x ^ {2} = y ^ {2} {\ pmod {p}}}$

${\ displaystyle x ^ {2} -y ^ {2} = 0 {\ pmod {p}}}$

${\ displaystyle (xy) (x + y) = 0 {\ pmod {p}}}$.

Como é um número primo, um ou deve ser divisível por . Uma vez que e são diferentes (módulo ) ,, e uma vez que ambas as variáveis ​​são maiores que zero ,. Assim, por contradição, os primeiros locais alternativos após devem ser únicos e, subsequentemente, um espaço vazio pode sempre ser encontrado, desde que a maioria dos locais seja preenchida (ou seja, a tabela hash não está mais que meio cheia). ${\ displaystyle p}$${\ displaystyle (xy)}$${\ displaystyle (x + y)}$${\ displaystyle p}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle p}$${\ displaystyle (xy) \ neq 0}$${\ displaystyle (x + y) \ neq 0}$${\ displaystyle p / 2}$${\ displaystyle h (k)}$${\ displaystyle p / 2}$

Sinais alternados

Se o sinal do deslocamento é alternado (por exemplo, +1, −4, +9, −16, etc.), e se o número de intervalos é um número primo congruente a 3 módulo 4 (por exemplo, 3, 7, 11, 19 , 23, 31, etc.), então os primeiros deslocamentos serão únicos (módulo ). Em outras palavras, uma permutação de 0 a é obtida e, conseqüentemente, um balde livre sempre será encontrado enquanto houver pelo menos um. ${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle p-1}$

Referências

links externos

• Tutorial / sondagem quadrática