The performance of hash tables is analyzed in a parallel context. Assuming that a hash table of fixed size is allocated in the shared memory of a PRAM with n processors, a Ph-step is defined as a PRAM computation, in which each processor searches or inserts a key in the table. It is shown that, in the case of uniformhashing, the average duration of a Ph-step for all insertions (worst case) in (View the MathML source) and (View the MathML source), where α and α′ are the load factors of the table before and after the execution of the Ph-step.
Analysis of parallel uniform hashing
PIETRACAPRINA, ANDREA ALBERTO;PUCCI, GEPPINO
1991
Abstract
The performance of hash tables is analyzed in a parallel context. Assuming that a hash table of fixed size is allocated in the shared memory of a PRAM with n processors, a Ph-step is defined as a PRAM computation, in which each processor searches or inserts a key in the table. It is shown that, in the case of uniformhashing, the average duration of a Ph-step for all insertions (worst case) in (View the MathML source) and (View the MathML source), where α and α′ are the load factors of the table before and after the execution of the Ph-step.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
