{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:37:36Z","timestamp":1787495856001,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540554882","type":"print"},{"value":"9783540471035","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55488-2_31","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T05:07:31Z","timestamp":1330232851000},"page":"250-269","source":"Crossref","is-referenced-by-count":2,"title":["High performance universal hashing, with applications to shared memory simulations"],"prefix":"10.1007","author":[{"given":"Martin","family":"Dietzfelbinger","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Friedhelm Meyer","family":"Heide","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"13_CR1","unstructured":"R. J. Anderson and G. L. Miller. Optical communication for pointer based algorithms. Technical Report CRI 88-14, University of Southern California, Comp. Sci. Dept., 1988."},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"H. Bast and T. Hagerup. Fast and reliable parallel hashing. In Proc. of the 3rd Ann. ACM Symp. on Parallel Algorithms and Architectures, pages 50\u201361, 1991.","DOI":"10.1145\/113379.113384"},{"key":"13_CR3","unstructured":"H. Bast and T. Hagerup. Personal communication. 1991."},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J. L. Carter","year":"1979","unstructured":"J. L. Carter and M. N. Wegman. Universal classes of hash functions. J. Comput. Syst. Sci., 18:143\u2013154, 1979.","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR5","unstructured":"M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. Technical Report 77, Universit\u00e4t-GH-Paderborn, Fachbereich Mathematik\/Informatik, Jan. 1991. Revised Version of the paper of the same title that appeared in Proc. of the 29th IEEE Ann. Symp. on Foundations of Computer Science, pages 524\u2013531, 1988."},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. An optimal parallel dictionary. In Proc. of the 1989 ACM Symp. on Parallel Algorithms and Architectures, pages 360\u2013368, 1989. (Revised version to appear in Information and Computation).","DOI":"10.1145\/72935.72974"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. How to distribute a dictionary in a complete network. In Proc. of the 22nd Ann. ACM Symp. on Theory of Computing, pages 117\u2013127, 1990.","DOI":"10.1145\/100216.100229"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In M. S. Paterson, editor, Proceedings of 17th ICALP, pages 6\u201319. Springer, 1990. Lecture Notes in Computer Science 443.","DOI":"10.1007\/BFb0032018"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. Dynamic hashing in real time. To appear, 1992.","DOI":"10.1007\/978-3-322-95233-2_7"},{"issue":"3","key":"13_CR10","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M. L. Fredman","year":"1984","unstructured":"M. L. Fredman, J. Koml\u00f3s, and E. Szemer\u00e9di. Storing a sparse table with (O(1) worst case access time. J. Assoc. Comput. Mach., 31(3):538\u2013544, July 1984.","journal-title":"J. Assoc. Comput. Mach."},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"J. Gil, Y. Matias, and U. Vishkin. Towards a theory of nearly constant time parallel algorithms. In Proc. of the 32nd IEEE Ann. Symp. on Foundations of Computer Science, pages 698\u2013710, 1991.","DOI":"10.1109\/SFCS.1991.185438"},{"issue":"2","key":"13_CR12","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1145\/322248.322254","volume":"28","author":"G. H. G\u00f6nnet","year":"1981","unstructured":"G. H. G\u00f6nnet. Expected length of the longest probe sequence in hash code searching. J. Assoc. Comput. Mach., 28(2):289\u2013304, Apr. 1981.","journal-title":"J. Assoc. Comput. Mach."},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"T. Hagerup. Constant-time parallel integer sorting. In Proc. of the 23rd Ann. ACM Symp. on Theory of Computing, pages 299\u2013306, 1991.","DOI":"10.1145\/103418.103452"},{"key":"13_CR14","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"W. Hoeffding. Probability inequalites for sums of bounded random variables. J. Am. Stat. Ass., 58:13\u201330, 1963.","journal-title":"J. Am. Stat. Ass."},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"R. M. Karp, M. Luby, and F. Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. In Preparation, 1991.","DOI":"10.1145\/129712.129743"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Y. Matias and U. Vishkin. Converting high probability into nearly-constant time-with applications to parallel hashing. In Proc. of the 23rd Ann. ACM Symp. on Theory of Computing, pages 307\u2013316, 1991.","DOI":"10.1145\/103418.103453"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"C. McDiarmid. On the method of bounded differences. In J. Siemons, editor, Surveys in Combinatorics, 1989, pages 148\u2013188. Cambridge University Press, 1989. London Math. Soc. Lecture Note Series 141.","DOI":"10.1017\/CBO9781107359949.008"},{"key":"13_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structures and Algorithms 1: Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. Springer-Verlag, Berlin, 1984."},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/BF00264615","volume":"21","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn and U. Vishkin. Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories. Acta Informatica, 21:339\u2013374, 1984.","journal-title":"Acta Informatica"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"A. Siegel. On universal classes of fast high performance hash functions, their timespace tradeoff, and their applications. In Proc. of the 30th IEEE Ann. Symp. on Foundations of Computer Science, pages 20\u201325, 1989. Revised Version.","DOI":"10.1109\/SFCS.1989.63450"},{"key":"13_CR21","first-page":"943","volume-title":"Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, chapter 18","author":"L. G. Valiant","year":"1990","unstructured":"L. G. Valiant. General purpose parallel architectures. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, chapter 18, pages 943\u2013971. Elsevier, Amsterdam, 1990."}],"container-title":["Lecture Notes in Computer Science","Data structures and efficient algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55488-2_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:59:12Z","timestamp":1605628752000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55488-2_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540554882","9783540471035"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-55488-2_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]}}}