Risoluzione collisione hashing lineare

0

Quindi ho una breve domanda sul metodo di sondaggio lineare della risoluzione delle collisioni nelle tabelle hash. Quindi per definizione un metodo di sondaggio lineare dovrebbe essere:

while (hashTable[hash] != null)
    hash = (hash(key) + step) % tableSize;

Ma nel mio caso so esattamente quale sarà la dimensione del tavolo, conosco tutte le chiavi, quindi mi chiedo se si tratta di un'implementazione valida valida:

while (hashTable[hash] != null) {
    if (++hash == hashTable.length)
        hash = 0;
}

Mi dispiace se l'ho reso troppo confuso, ma sono un po 'confuso ... Se non riesci a ottenere quello che sto chiedendo, una semplice spiegazione di come il sondaggio lineare sarebbe implementato sarebbe molto utile, e ps: sto lavorando in java. Grazie mille

    
posta crazymao 13.04.2013 - 05:21
fonte

1 risposta

1

Se conosci tutti i tasti, dovresti utilizzare una funzione di hash perfetta; gperf può aiutare con quello. Con un hash perfetto, le collisioni non devono essere gestite, poiché non possono accadere.

Questo non ha senso: "hash = (hash (chiave) + passo)% tableSize" O intendi "hash = (hashFunction (key) + step)% tableSize", che assomiglia al doppio hashing, o intendi "hash = (hash + step)% tableSize", che è in effetti sondaggio lineare.

Il tuo secondo frammento di codice ha senso ed è valido.

Il problema con il sondaggio lineare, in particolare con le dimensioni del passo di uno, è che incoraggia il clustering, quindi le operazioni O (1) degenerano in operazioni O (n) anche a fattori di carico moderati.

    
risposta data 13.04.2013 - 19:46
fonte

Leggi altre domande sui tag