Massively parallel hash algorithms and performance
I‐Ling Yen · 1991
In sequential systems, the hash table yields an almost constant time performance for single element access for implementing the search table abstract data type.Different collision resolution strategies have been studied and the average performance of different algorithms has been analyzed.However, hash algorithms for massively parallel systems have not been studied in as much detail as other parallel algorithms such as sorting.The perfommnce of a hash table with various strategies in massively parallel systems is quite different from that in sequential systems.Also, the massive parallelism can be used to achieve more efficient hash algorithms.In this paper, we investigate new algorithms for various hash strategies and analyze their performance.The performance of these algoritlmls is compared with the parallel version of conventional algorithms and with themselves.We observe that the parallel linear probing hash algorithm has the best performance.Also, its performance is better than the most commonly used parallel sorting algorithms.A nearly O (logN) average time performance is achieved by this hash algorithm for creating a hash table of N elements.