{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:23Z","timestamp":1787337503690,"version":"build-2736575974"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    A hash table is a representation of a set in a linear size data structure that supports constant-time membership queries. We show how to construct a hash table for any given set of n keys in O(lg lg n) parallel time with high probability, using n processors on a weak version of a concurrent-read concurrent-write parallel random access machine (crcw pram). Our algorithm uses a novel approach of hashing by \"oblivious execution\" based on probabilistic analysis. The algorithm is simple and has the following structure:Partition the input set into buckets by a random polynomial of constant degree. For t:= 1 to O(lg lg n) do Allocate M\n                    <jats:sub>t<\/jats:sub>\n                    memory blocks, each of size K\n                    <jats:sub>t<\/jats:sub>\n                    .Let each bucket select a block at random, and try to injectively map its keys into the block using a random linear function. Buckets that fail carry on to the next iteration. The crux of the algorithm is a careful a priori selection of the parameters M\n                    <jats:sub>t<\/jats:sub>\n                    and K\n                    <jats:sub>t<\/jats:sub>\n                    . The algorithm uses only O(lg lg n) random words and can be implemented in a work-efficient manner.\n                  <\/jats:p>","DOI":"10.1137\/s0097539794291580","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1348-1375","source":"Crossref","is-referenced-by-count":3,"title":["Simple Fast Parallel Hashing by Oblivious Execution"],"prefix":"10.1137","volume":"27","author":[{"given":"Joseph","family":"Gil","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yossi","family":"Matias","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Michael Molloy, The probabilistic method, Algorithms Combin., Vol. 16, Springer, Berlin, 1998, 1\u2013351678558","DOI":"10.1007\/978-3-662-12788-9_1"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762122"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"H. Bast and T. Hagerup,\n                      Fast and reliable parallel hashing\n                      , in 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, July 1991, pp. 50\u201361.","DOI":"10.1145\/113379.113384"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65958"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90031-V"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"R. B. Boppana,\n                      Optimal separations between concurrent\u2010write parallel machines\n                      , in Proc. 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 320\u2013326.","DOI":"10.1145\/73007.73037"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Bogdan Chlebus, Krzysztof Diks, Torben Hagerup, Tomasz Radzik, New simulations between CRCW PRAMs, Lecture Notes in Comput. Sci., Vol. 380, Springer, New York, 1989, 95\u201310491a:68055","DOI":"10.1007\/3-540-51498-8_9"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90015-0"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, J. Gil, Y. Matias, and N. Pippenger,\n                      Polynomial hash functions are reliable\n                      , in Proc. 19th International Colloquium on Automata Languages and Programming, Lecture Notes in Comput. Sci. 623, Springer, New York, July 1992, pp. 235\u2013246.","DOI":"10.1007\/3-540-55719-9_77"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194094"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide,\n                      An optimal parallel dictionary\n                      , in 1st Annual ACM Symposium on Parallel Algorithms and Architectures, 1989, pp. 360\u2013368.","DOI":"10.1145\/72935.72974"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Martin Dietzfelbinger, Friedhelm Meyer auf der Heide, A new universal class of hash functions and dynamic hashing in real time, Lecture Notes in Comput. Sci., Vol. 443, Springer, New York, 1990, 6\u2013191076811","DOI":"10.1007\/BFb0032018"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0217037"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(88)90008-8"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"P. B. Gibbons, Y. Matias, and V. L. Ramachandran,\n                      Efficient low\u2010contention parallel algorithms\n                      , in 6th Annual ACM Symposium on Parallel Algorithms and Architectures, June 1994, pp. 236\u2013247.","DOI":"10.1145\/181014.181382"},{"key":"R18","unstructured":"P. B. Gibbons, Y. Matias, and V. L. Ramachandran,\n                      The QRQW PRAM: Accounting for contention in parallel algorithms\n                      , in Proc. 5th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, Jan. 1994, pp. 638\u2013648."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J. Gil,\n                      Fast load balancing on a PRAM\n                      , in Proc. 3rd IEEE Symposium on Parallel and Distributed Computing, Dec. 1991, pp. 10\u201317.","DOI":"10.1109\/SPDP.1991.218302"},{"key":"R20","unstructured":"Joseph Gil, Yossi Matias, Fast hashing on a PRAM\u2014designing by expectation, ACM, New York, 1991, 271\u20132801095842"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00052-2"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0098"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1127"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"J. Gil and Y. Matias,\n                      Simple fast parallel hashing\n                      , in Proc. 21st International Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 820, Springer, New York, 1994, pp. 239\u2013250.","DOI":"10.1007\/3-540-58201-0_72"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Joseph Gil, Yossi Matias, Uzi Vishkin, Towards a theory of nearly constant time parallel algorithms, IEEE Comput. Soc. Press, Los Alamitos, CA, 1991, 698\u20137101177216","DOI":"10.1109\/SFCS.1991.185438"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255722"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"L. A. Goldberg, M. Jerrum, F. T. Leighton, and S. B. Rao,\n                      Doubly logarithmic communication algorithms for optical communication parallel computers\n                      , in 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993, pp. 300\u2013309.","DOI":"10.1145\/165231.166108"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322353"},{"key":"R29","unstructured":"M. T. Goodrich, Y. Matias, and U. Vishkin,\n                      Optimal parallel approximation algorithms for prefix sums and integer sorting\n                      , in Proc. 5th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, Jan. 1994, pp. 241\u2013250."},{"key":"R30","unstructured":"Ronald Graham, Donald Knuth, Oren Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warsaw, 1998, 719\u20130, Translated from the second English (1994) edition by P. Chrz\u0105stowski, A. Czumaj, L. G\u0105sieniec and M. Raczunas99m:68002"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90082-N"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90062-9"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"T. Hagerup and T. Radzik,\n                      Every robust CRCW PRAM can efficiently simulate a Priority PRAM\n                      , in 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990, pp. 117\u2013124.","DOI":"10.1145\/97444.97677"},{"key":"R34","volume-title":"Introduction to parallel algorithms","author":"Xavier C.","year":"1998"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"R. M. Karp, M. Luby, and F. Meyer auf der Heide,\n                      Efficient PRAM simulation on a distributed memory machine\n                      , in Proc. 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 318\u2013326.","DOI":"10.1145\/129712.129743"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"Torben Hagerup, Sorting and searching on the word RAM, Lecture Notes in Comput. Sci., Vol. 1373, Springer, Berlin, 1998, 366\u201339899f:68043","DOI":"10.1007\/BFb0028575"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"Y. Matias and U. Vishkin,\n                      Converting high probability into nearly\u2010constant time\u2014with applications to parallel hashing\n                      , in Proc. 23rd Annual ACM Symposium on Theory of Computing, May 1991, pp. 307\u2013316.","DOI":"10.1145\/103418.103453"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90034-V"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69672-5"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn and A. Tsakalidis,\n                      Data structures\n                      , in Handbook of Theoretical Computer Science, J. van Leeuwen, ed., vol. A, North\u2013Holland, Amsterdam, 1990, pp. 301\u2013341.","DOI":"10.1016\/B978-0-444-88071-0.50011-4"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90008-6"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"A. Siegel,\n                      On universal classes of fast high performance hash functions, their time\u2010space tradeoff, and their applications\n                      , in Proc. 30th IEEE Annual Symposium on Foundation of Computer Science, 1989, pp. 20\u201325.","DOI":"10.1109\/SFCS.1989.63450"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"L. G. Valiant,\n                      General purpose parallel architectures\n                      , in Handbook of Theoretical Computer Science, J. van Leeuwen, ed., vol. A, Elsevier Science Publishers B. V., Amsterdam, 1990, pp. 944\u2013971.","DOI":"10.1016\/B978-0-444-88071-0.50023-0"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794291580","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:18Z","timestamp":1787336058000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794291580"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794291580"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794291580","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}