Passando dalla scansione lineare a quadratica Probing (collisioni hash)

Question

Il mio attuale implementazione di una tabella hash sta usando la scansione lineare e ora voglio passare a quadratica Probing (e poi a concatenamento e forse il doppio hashing troppo). Ho letto un paio di articoli, tutorial, Wikipedia, ecc ... Ma io ancora non so esattamente cosa devo fare.

Probing lineare, in fondo, ha un passo di 1 e che è facile da fare. Durante la ricerca, l'inserimento o la rimozione di un elemento dalla tabella hash, ho bisogno di calcolare un hash e per questo faccio questo:

index = hash_function(key) % table_size;

Poi, durante la ricerca, l'inserimento o la rimozione ho scorrere la tabella fino a quando ho trovato un secchio libera, in questo modo:

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + 1) % table_size;
    }
while(/* LOOP UNTIL IT'S NECESSARY */);

Per quanto riguarda quadratica Probing, penso che quello che ho bisogno di fare è cambiare il modo l ' "indice" del passo si calcola, ma questo è quello che non capisco come dovrei farlo. Ho visto vari pezzi di codice, e tutti loro sono un po 'diverso.

Inoltre, ho visto alcune implementazioni di quadratico Probing in cui la funzione di hash viene modificato a accomodato che (ma non tutti). È che il cambiamento davvero necessario o posso evitare di modificare la funzione di hash e usano ancora quadratica Probing?

Modifica Dopo aver letto tutto sottolineato da Eli Bendersky sotto Penso che ho avuto l'idea generale. Ecco parte del codice a http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx :

15   for ( step = 1; table->table[h] != EMPTY; step++ ) {
16     if ( compare ( key, table->table[h] ) == 0 )
17       return 1;
18 
19     /* Move forward by quadratically, wrap if necessary */
20     h = ( h + ( step * step - step ) / 2 ) % table->size;
21   }

Ci sono 2 cose che non capisco ... Dicono che quadratica sondaggio di solito è fatto usando c(i)=i^2. Tuttavia, nel codice qui sopra, che sta facendo qualcosa di più simile c(i)=(i^2-i)/2

ero pronto a implementare questo sul mio codice, ma vorrei semplicemente fare:

index = (index + (index^index)) % table_size;

... e non:

index = (index + (index^index - index)/2) % table_size;

Se non altro, lo farei:

index = (index + (index^index)/2) % table_size;

... perchè io ho visto altri esempi di codice immersioni per due. Anche se io non capisco perché ...

1) Perché è sottraendo il passo?
2) Perché è immersioni entro 2?

Answer 1

Non è necessario modificare la funzione di hash per sondare quadratica. La forma più semplice di quadratica tastatura è in realtà solo aggiungendo conseguenti piazze alla posizione calcolata anziché lineare 1, 2, 3.

C'è una buona risorsa qui . Quanto segue è preso da lì. Questa è la forma più semplice di quadratica sondare quando viene utilizzata la semplice c(i) = i^2 polinomiale:

Nel caso più generale la formula è:

E si può scegliere le costanti.

Tenere, a mente, tuttavia, che quadratica sondaggio è utile solo in determinati casi. Come il Wikipedia stati:

  

quadratica sondaggio fornisce buona memoria   caching perché conserva una certa   frazione di riferimento; tuttavia, lineare   sondaggio ha maggiore frazione e,   in tal modo, migliori prestazioni della cache.   Quadratica sondare meglio evita la   problema di clustering che può verificarsi con   scansione lineare, anche se non è   immunitario.

---

Modifica Come molte cose in informatica, le costanti esatte e polinomi di sondare quadratica sono euristica. Sì, la forma più semplice è i^2, ma si può scegliere qualsiasi altro polinomiale. Wikipedia dà l'esempio con h(k,i) = (h(k) + i + i^2)(mod m).

Pertanto, è difficile rispondere alla sua "perché" questione. L'unica "perché" Ecco perché avete bisogno di sondare quadratica a tutti? Hai problemi con altre forme di sondaggio e trovare un tavolo cluster? O è solo un compito per casa, o auto-apprendimento?

Tenete a mente che di gran lunga la tecnica più comune risoluzione di collisione per le tabelle hash è o incatena o scansione lineare. Quadratica sondaggio è un'opzione euristica disponibile per casi particolari, e se non si sa cosa si sta facendo molto bene, io non consiglierei di usarlo.

Answer 2

C'è un modo particolarmente semplice ed elegante per implementare quadratica sondare se la dimensione della tabella è una potenza di 2:

step = 1;

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + step) % table_size;
        step++;
    }
} while(/* LOOP UNTIL IT'S NECESSARY */);

Invece di guardare offset 0, 1, 2, 3, 4 ... dall'indice originale, questo esaminerà offset 0, 1, 3, 6, 10 ... (I ^th sonda è all'offset (i * (i + 1)) / 2, cioè è quadratica).

Questa è garantito per colpire ogni posizione nella tabella di hash (così si sono garantiti per trovare un secchio vuoto se ce n'è uno) fornito la dimensione della tabella è una potenza di 2.

---

Ecco uno schizzo di una prova:

1. Data una dimensione della tabella di n, vogliamo dimostrare che possiamo ottenere valori distinti di n (i * (i + 1)) / 2 (mod n) con i = 0 ... n-1.
2. Siamo in grado di dimostrare questo per assurdo. Si supponga che ci sono meno di n valori distinti: in tal caso, deve essere almeno due valori interi distinti per i nell'intervallo [0, n-1] tale che (i * (i + 1)) / 2 (mod n ) è la stessa. Chiamare questi p e q, dove p
3. vale a dire. (P * (p + 1)) / 2 = (q * (q + 1)) / 2 (mod n)
4. => (p ² + p) / 2 = (q ² + q) / 2 (mod n)
5. => p ² + p = q ² + q (2n mod)
6. => q ² - p ² + q - p = 0 (2n mod)
7. Fattorizza => (q - p) (p + q + 1) = 0 (2n mod)
8. (q - p). = 0 è il caso banale p = q
9. (p + q + 1) = 0 (2n mod) è impossibile: i nostri valori di p e q sono nell'intervallo [0, n-1], q> p, quindi (p + q + 1) deve essere compreso nell'intervallo [2, 2n-2].
10. Come lavoriamo modulo 2n, dobbiamo anche trattare il caso in cui sia difficile fattori sono non-zero, ma moltiplicare invia 0 (2n mod):
    • Si osservi che la differenza tra i due fattori (q - p) e (p + q + 1) è (2p + 1), che è un numero dispari - così uno dei fattori devono essere ancora, e l'altro deve essere dispari.
    • (q - p) (p + q + 1) = 0 (2n mod) => (q - p) (p + q + 1) è divisibile per 2n. Se n (e quindi 2n) è una potenza di 2 , questo richiede l'anche fattore di essere un multiplo di 2n (perché tutti i fattori primi di 2n sono 2, mentre nessuno dei fattori primi di il nostro fattore dispari sono).
    • Ma (q - p) presenta un valore massimo di n-1, e (p + q + 1) presenta un valore massimo di 2n-2 (come si vede nella fase 9), così non può essere un multiplo di 2n .
    • Quindi questo caso è impossibile pure.
11. Pertanto l'ipotesi che ci sono meno di n valori distinti (nel passaggio 2) deve essere falso.

(Se la dimensione della tabella è non una potenza di 2, questa crolla al passo 10).