ANALYSIS AND IMPLEMENTATION OF PARALLEL UNIFORM HASHING

作     者：FABRIZIO LUCCIO ANDREA PIETRACAPRINA GEPPINO PUCCI 

作者机构：Department of Computer Science University of Pisa Corso Italia 40 56100 Pisa Italy Department of Computer Science University of Illinois at Urbana-Champaign Urbana IL 61801 USA International Computer Science Institute Berkeley CA 94720 USA 

出 版 物：《International Journal of Foundations of Computer Science》 

年 卷 期：1992年第3卷第1期

页      面：55-63页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Data structures parallel algorithms analysis of algorithms hash tables PRAM model 

摘      要：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 the maximum number of table probes needed for a single key in a Ph-step is Ω( log 1/α n ) and O( log 1/α′ n ) with high probability, where α and α′ are the load factors before and after the execution of the Ph-step. However, a clever implementation of a Ph-step is proposed, which runs in time O(( log 1/α′ n) 1/2 ) with high probability. The algorithm exploits the fact that operations relative to different keys have different durations; hence, the processors in charge of shorter operations, once finished, are used to perform part of the longer ones.