Affordable Access

Publisher Website

Analysis of parallel uniform hashing

Authors
Journal
Information Processing Letters
0020-0190
Publisher
Elsevier
Publication Date
Volume
37
Issue
2
Identifiers
DOI: 10.1016/0020-0190(91)90135-5
Keywords
  • Data Structures
  • Parallel Algorithms
  • Analysis Of Algorithms
  • Hash Tables
  • Pram Model

Abstract

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 uniform hashing, the average duration of a Ph-step for all insertions (worst case) in Ω(log 1 α n) and O(log 1 α′ n) , where α and α′ are the load factors of the table before and after the execution of the Ph-step.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Analysis of random probing hashing

on Information Processing Letters Jan 01, 1989

Cuckoo hashing: Further analysis

on Information Processing Letters Jan 01, 2003

The analysis of double hashing

on Journal of Computer and System... Jan 01, 1978
More articles like this..