An Optimal Parallel Dictionary

AbstractA parallel dictionary is implemented on a randomized CRCW PRAM with p processors in such a way that n instructions (Insert, Delete, Lookup), n/p read in by each processor, can be executed in optimal expected time O(n/p). Further, the response time of each lookup is worst case constant. The construction is inspired by the sequential dynamic hashing strategy due to Dietzfelbinger et al. (in "Proceedings, 29th IEEE Symposium on Foundations of Computer Science," pp. 524-531), which in turn is based on the perfect hashing scheme due to Fredman et al. (1984, J. Assoc. Comput. Mach.31, 538-544)