Hash Table: Devo aumentare il numero di elemento su collisioni?

Question

In questo momento le mie tabelle hash contare il numero di ogni elemento inserito nella tabella hash. Io uso questo conteggio, con la dimensione totale tabella hash, per calcolare il fattore di carico e quando raggiunge come il 70%, ho rimaneggiamento esso.

ho pensato che forse devo contare solo gli elementi inseriti con riempimenti uno slot vuoto invece di tutti loro. Causa il metodo di collisione che sto utilizzando è concatenazioni separate. Il fattore di carico continua ad aumentare, ma se non ci può essere un paio di collisioni lasciando un sacco di slot vuoti sulla tabella di hash.

Probabilmente state pensando che se ho che molte collisioni, forse sto non si utilizza il metodo migliore di hashing. Ma non è questo il punto, sto utilizzando uno degli algoritmi di hashing conoscenze là fuori, ho provato 3 di loro i miei dati di esempio e selezionati colui che ha prodotto meno collisioni.

La mia domanda rimane. Devo mantenere contando ogni elemento inserito, o solo quelle che riempiono uno slot vuoto nella tabella hash?

Answer 1

Rehashing ha lo scopo di ridurre la probabilità di collisioni, in modo sistematico ignorando le collisioni di decidere quando rimaneggiamento sembra autolesionista.

Best potrebbe essere se hai tenuto con ogni voce il valore originale di hash completo (una collisione di corso è invece determinato dal cancelletto con modulo la dimensione corrente) e contava solo le collisioni che sono a causa del funzionamento modulo - implicitamente riconoscendo che se una collisione è a causa di valori di hash pieni identici per gli articoli differenti, non c'è niente di rimaneggiamento può fare per aiutare (se non per "rimasticare" si implicano anche il passaggio a una funzione di hash diversa, ma non sembra che questo che intende qui; -).

Mantenere i valori completi hash significa anche rimaneggiamento più conveniente dal momento che non è necessario eseguire nuovamente la funzione di hash (come rilevante è che dipende da come costosa la funzione di hash è quello di calcolare, ovviamente).