Our parallel dictionary structure of Theorem REF  is based on the dynamic perfect hashing structure of Dietzfelbinger et al. [1]}. This is a two-level data structure similar to the classic static perfect hashing structure of Fredman et al. [2]}. At the first level, a universal hash function partitions the input into smaller subsets, each of which are then resolved at the second level using another universal hash function mapping the elements into sufficiently large tables. The structure supports (sequential) membership queries in worst-case constant time by evaluating the hash functions and navigating the structure accordingly. Updates are supported in amortized expected constant time by carefully rebuilding and rehashing the structure during execution. At any point in time the structure never uses more than \(O(n)\)  space. We show how to parallelize the evaluation of a universal hash function (the simple and practically efficient multiply-shift hash function). Then, using the scattered memory access operations, we show how to access the corresponding entries in the structure in parallel.
Our technique requires only small changes to the structure of Dietzfelbinger et al. [1]} and we are able directly apply their update operations to our solution. Thus, we are able to parallelize the worst-case constant time sequential membership query while maintaining the amortized expected constant update time bound of Dietzfelbinger et al. [1]}, leading to the bounds of Theorem REF .
