{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:59:01Z","timestamp":1781078341582,"version":"3.54.1"},"publisher-location":"Berlin\/Heidelberg","reference-count":17,"publisher":"Springer-Verlag","isbn-type":[{"value":"3540528261","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0032018","type":"book-chapter","created":{"date-parts":[[2005,12,11]],"date-time":"2005-12-11T06:05:31Z","timestamp":1134281131000},"page":"6-19","source":"Crossref","is-referenced-by-count":54,"title":["A new universal class of hash functions and dynamic hashing in real time"],"prefix":"10.1007","author":[{"given":"Martin","family":"Dietzfelbinger","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Friedhelm","family":"Meyer auf der Heide","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Aho, H. V., and Lee, D., Storing a dynamic sparse table, Proc. of the 27th IEEE FOCS, 1986, pp. 55\u201360.","DOI":"10.1109\/SFCS.1986.50"},{"key":"2_CR2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D. Angluin","year":"1979","unstructured":"Angluin, D., and Valiant, L. G., Fast probabilistic algorithms for Hamiltonian circuits and matchings, J. Comput. Syst. Sci. 18 (1979), 155\u2013193.","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR3","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0020-0190(88)90210-4","volume":"28","author":"G. Brassard","year":"1988","unstructured":"Brassard, G., and Kannan, S., The generation of random permutations on the fly, IPL 28 (1988) 207\u2013212.","journal-title":"IPL"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E., Dynamic perfect hashing: Upper and lower bounds, Proc. of the 29th IEEE FOCS, 1988, pp. 524\u2013531; also: Tech. Report No. 282, Fachbereich Informatik, Universit\u00e4t Dortmund, 1988.","DOI":"10.1109\/SFCS.1988.21968"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., and Meyer auf der Heide, F., An optimal parallel dictionary, Proc. of ACM Symp. on Parallel Algorithms and Architectures, 1989, pp. 360\u2013368.","DOI":"10.1145\/72935.72974"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Meyer auf der Heide, F., How to distribute a dictionary in a complete network, Proceedings of the 22nd ACM STOC, 1990.","DOI":"10.1145\/100216.100229"},{"issue":"3","key":"2_CR7","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M. L. Fredman","year":"1984","unstructured":"Fredman, M. L., Koml\u00f3s, J., and Szemer\u00e9di, E., Storing a sparse table with O(1) worst case access time, J. ACM 31(3), 1984, 538\u2013544.","journal-title":"J. ACM"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Gil, J., Meyer auf der Heide, F., and Wigderson, A., Not all keys can be hashed in constant time, Proc. of the 22nd ACM STOC, 1990.","DOI":"10.1145\/100216.100247"},{"key":"2_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4800-2","volume-title":"Probabilistic Analysis of Algorithms","author":"M. Hofri","year":"1987","unstructured":"Hofri, M., Probabilistic Analysis of Algorithms, Springer Verlag, New York, 1987."},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Karlin, A., and Upfal, E., Parallel hashing \u2014 an efficient implementation of shared memory, Proc. of the 18th ACM STOC, 1986, pp. 160\u2013168.","DOI":"10.1145\/12130.12146"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Kruskal, C. P., Rudolph, L., and Snir, M., A complexity theory of efficient parallel algorithms, Proc. of 15th ICALP, 1988, pp. 333\u2013346, Springer LNCS 317; also: revised preprint.","DOI":"10.1007\/3-540-19488-6_126"},{"key":"2_CR12","unstructured":"Lipton, R.J., and Naughton, J.G. Clocked adversaries for hashing, Tech. Rep. CS-TR-203-89, Princeton, 1989."},{"key":"2_CR13","volume-title":"Data Structures and Algorithms, Vol. 1","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K., Data Structures and Algorithms, Vol. 1, 1984, Springer Verlag, Berlin."},{"key":"2_CR14","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF00264615","volume":"21","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K., and Vishkin, U., Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memory, Acta Informatica 21, 1984, 339\u2013374.","journal-title":"Acta Informatica"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"Ranade, A. G., How to emulate shared memory, Proc. of the 28th IEEE FOCS, 1987, pp. 185\u2013194.","DOI":"10.1109\/SFCS.1987.32"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Siegel, A., On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications, Proc. of the 30th IEEE FOCS, 1989, pp. 20\u201325.","DOI":"10.1109\/SFCS.1989.63450"},{"issue":"3","key":"2_CR17","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1145\/828.1892","volume":"31","author":"E. Upfal","year":"1984","unstructured":"Upfal, E., Efficient schemes for parallel communication, J. ACM 31(3), 1984, 507\u2013517.","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0032018.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T22:05:29Z","timestamp":1607551529000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0032018"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540528261"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0032018","relation":{},"subject":[]}}