Parallel Hash Algorithms for Virtual Key Index Tables

概要

論文の詳細を見る
Parallelism is introduced into a hash table organization, called a "virtual key index table", which was originally proposed by Morris. A parallel virtual key index scheme is to be used to perform hashing by parallel hashing hardware with a multi-bank hash table: The hash table is realized with J banks, each having a virtual key and a pointer to the real key. In searching for a given real key k, real keys are accessed only when corresponding virtual keys stored in the index table are matched with the virtual key of k. Basic performance assessment parameters in this scheme, such as the average number of probes in a successful search and an unsuccessful search are calculated in both cases with and without key deletion. The results are compared with those of a parallel direct hash scheme. The number of probes in the key search is slightly increased in the virtual key scheme. However, the virtual key scheme affords a design of a hash table organization independent of data structures for the key representation, larger J with the same transfer width than does the parallel direct hash scheme and a garbage collection scheme which dispenses with time-consuming rehashing of real keys. Design choices between the two parallel hash schemes are also discussed.
一般社団法人情報処理学会の論文
1978-10-30