Tempo di esecuzione per inserire n elementi in una tabella hash vuota

Question

Le persone dicono che ci vuole O (1) ammortizzato per mettere in una tabella hash. Pertanto, inserendo n elementi deve essere O (n). Questo non è vero per n grande, tuttavia, poiché come ha detto un risponditore, "Tutto ciò che serve per soddisfare il previsto ammortamento O (1) è espandere la tabella e ripassare tutto con una nuova funzione di hash casuale ogni volta che c'è una collisione." ;

Quindi: qual è il tempo di esecuzione medio dell'inserimento di n elementi in una tabella hash? Mi rendo conto che probabilmente dipende dall'implementazione, quindi menziona il tipo di implementazione di cui stai parlando.

Ad esempio, se ci sono (log n) collisioni equidistanti e ogni collisione richiede O (k) per risolvere, dove k è la dimensione corrente dell'hashtable, allora avresti questa relazione di ricorrenza:

T(n) = T(n/2) + n/2 + n/2

(ovvero, si prende il tempo per inserire n / 2 elementi, quindi si ha una collisione, si prende n / 2 per risolvere, quindi si eseguono i rimanenti n / 2 inserimenti senza una collisione). Questo finisce per essere O (n), quindi yay. Ma è ragionevole?

Answer 1

Dipende completamente da quanto sia inefficiente il tuo rimodellamento. In particolare, se riesci a stimare correttamente la dimensione prevista della tua hashtable la seconda volta, il tuo runtime si avvicina ancora a O (n). In effetti, devi specificare quanto è inefficiente il tuo calcolo delle dimensioni di rehash prima di poter determinare l'ordine previsto.

Answer 2

  

La gente dice che ci vuole O (1) ammortizzato per metterlo in una tabella hash.

Da un punto di vista teorico, è previsto O ammortizzato (1).

Le tabelle hash sono fondamentalmente una struttura di dati randomizzata, nello stesso senso in cui quicksort è un algoritmo randomizzato. Devi generare le tue funzioni hash con una certa casualità, oppure esistono input patologici che non sono O (1).

Puoi ottenere O (1) ammortizzato atteso usando hash perfetto dinamico :

L'idea ingenua che ho pubblicato in origine era di ripassare con una nuova funzione di hash casuale su ogni collisione. (Vedi anche funzioni hash perfette ) Il problema è che questo richiede O (n ^ 2 ) spazio, dal paradosso del compleanno.

La soluzione è avere due tabelle hash, con la seconda tabella per le collisioni; risolvere le collisioni su quella seconda tabella ricostruendola. Quella tabella avrà elementi O (\ sqrt {n}), quindi crescerà alla dimensione O (n).

In pratica spesso usi semplicemente una funzione hash fissa perché puoi assumere (o non preoccuparti se) che il tuo input sia patologico, proprio come spesso fai quickort senza pre-randomizzare l'input.

Answer 3

Tutto ciò che O (1) sta dicendo è che l'operazione viene eseguita in un tempo costante ed è non dipendente dal numero di elementi nella struttura dei dati.

In parole semplici, ciò significa che dovrai pagare lo stesso costo, non importa quanto sia grande la tua struttura di dati.

In termini pratici ciò significa che strutture di dati semplici come gli alberi sono generalmente più efficaci quando non è necessario archiviare molti dati. Nella mia esperienza trovo alberi più veloci fino a ~ 1k elementi (numeri interi a 32 bit), quindi le tabelle hash prendono il sopravvento. Ma come al solito YMMW.

Answer 4

Perché non eseguire solo alcuni test sul tuo sistema? Forse se pubblichi la fonte, possiamo tornare indietro e testarli sui nostri sistemi e potremmo davvero trasformarlo in una discussione molto utile.

Non è solo l'implementazione, ma anche l'ambiente che decide quanto tempo impiega l'algoritmo. Puoi comunque verificare se sono disponibili campioni di benchmarking o meno. Il problema con cui pubblicherò i miei risultati non sarà di alcuna utilità poiché le persone non hanno idea di cos'altro sia in esecuzione sul mio sistema, di quanta RAM sia libera in questo momento e così via. Puoi solo avere un'idea generale. E questo è buono quanto quello che ti dà il big-O.