{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T00:08:39Z","timestamp":1758413319161,"version":"3.44.0"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T00:00:00Z","timestamp":1754092800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T00:00:00Z","timestamp":1754092800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["882500","882500","882500"],"award-info":[{"award-number":["882500","882500","882500"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Karlsruher Institut f\u00fcr Technologie (KIT)"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,11]]},"abstract":"Abstract<\/jats:title>\n A minimal perfect hash function (MPHF) maps a set\u00a0S<\/jats:italic> of n<\/jats:italic> keys to the first n<\/jats:italic> integers without collisions. There is a lower bound of \n \n $$n\\log _2e-\\mathcal {O}(\\log n) \\approx 1.44n$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msub>\n e<\/mml:mi>\n -<\/mml:mo>\n O<\/mml:mi>\n \n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2248<\/mml:mo>\n 1.44<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> bits needed to represent an MPHF. This can be reached by a brute-force<\/jats:italic> algorithm that tries \n \n $$e^n$$<\/jats:tex-math>\n \n \n e<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> hash function seeds in expectation and stores the first seed that leads to an MPHF. The most space-efficient previous algorithms for constructing MPHFs all use such a brute-force approach as a basic building block. In this paper, we introduce ShockHash \u2013 S<\/jats:bold>mall, h<\/jats:bold>eavily o<\/jats:bold>verloaded cuck<\/jats:bold>oo hash<\/jats:bold> tables for minimal perfect hashing. ShockHash uses two hash functions \n \n $$h_0$$<\/jats:tex-math>\n \n \n h<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and \n \n $$h_1$$<\/jats:tex-math>\n \n \n h<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, hoping for the existence of a function \n \n $$f : S \\rightarrow \\{0,1\\}$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n :<\/mml:mo>\n S<\/mml:mi>\n \u2192<\/mml:mo>\n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> such that \n \n $$x \\mapsto h_{f(x)}(x)$$<\/jats:tex-math>\n \n \n x<\/mml:mi>\n \u21a6<\/mml:mo>\n \n h<\/mml:mi>\n \n f<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msub>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is an MPHF on S<\/jats:italic>. It then uses a 1-bit retrieval data structure to store f<\/jats:italic> using \n \n $$n + o(n)$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n +<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\u00a0bits. In graph terminology, ShockHash generates n<\/jats:italic>-edge random graphs until stumbling on a pseudoforest<\/jats:italic> \u2013 where each component contains as many edges as nodes. Using cuckoo hashing, ShockHash then derives an MPHF from the pseudoforest in linear time. We show that ShockHash needs to try only about \n \n $$(e\/2)^n \\approx 1.359^n$$<\/jats:tex-math>\n \n \n \n \n (<\/mml:mo>\n e<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msup>\n \u2248<\/mml:mo>\n 1<\/mml:mn>\n .<\/mml:mo>\n \n 359<\/mml:mn>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> seeds in expectation. This reduces the space for storing the seed by roughly n<\/jats:italic> bits (maintaining the asymptotically optimal space consumption) and speeds up construction by almost a factor of \n \n $$2^n$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> compared to brute-force. Bipartite<\/jats:italic> ShockHash reduces the expected construction time again to about \n \n $$1.166^n$$<\/jats:tex-math>\n \n \n 1<\/mml:mn>\n .<\/mml:mo>\n \n 166<\/mml:mn>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> by maintaining a pool of candidate hash functions and checking all possible pairs. Using ShockHash as a building block within the RecSplit framework we obtain ShockHash-RS, which can be constructed up to 3 orders of magnitude faster than competing approaches. ShockHash-RS can build an MPHF for 10 million keys with 1.489 bits per key in about half an hour. When instead using ShockHash after an efficient k<\/jats:italic>-perfect hash function, it achieves space usage similar to the best competitors, while being significantly faster to construct and query.<\/jats:p>","DOI":"10.1007\/s00453-025-01321-z","type":"journal-article","created":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T03:22:58Z","timestamp":1754104978000},"page":"1620-1668","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["ShockHash: Near Optimal-Space Minimal Perfect Hashing Beyond Brute-Force"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0474-1805","authenticated-orcid":false,"given":"Hans-Peter","family":"Lehmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3330-9349","authenticated-orcid":false,"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6477-0106","authenticated-orcid":false,"given":"Stefan","family":"Walzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,2]]},"reference":[{"issue":"13","key":"1321_CR1","doi-asserted-by":"publisher","first-page":"i169","DOI":"10.1093\/BIOINFORMATICS\/BTY292","volume":"34","author":"Fatemeh Almodaresi","year":"2018","unstructured":"Almodaresi, Fatemeh, Sarkar, Hirak, Srivastava, Avi, Patro, Rob: A space and time-efficient index for the compacted colored de bruijn graph. Bioinform. 34(13), i169\u2013i177 (2018). https:\/\/doi.org\/10.1093\/BIOINFORMATICS\/BTY292","journal-title":"Bioinform."},{"key":"1321_CR2","doi-asserted-by":"publisher","unstructured":"Axtmann Michael, Witt Sascha, Ferizovic Daniel, Sanders Peter.: Engineering in-place (shared-memory) sorting algorithms. ACM Trans. Parallel Comput., 9(1):2:1\u20132:62, 2022. https:\/\/doi.org\/10.1145\/3505286","DOI":"10.1145\/3505286"},{"key":"1321_CR3","doi-asserted-by":"publisher","unstructured":"Belazzougui Djamal, Boldi Paolo, Pagh Rasmus, Vigna Sebastiano.: Fast prefix search in little space, with applications. In ESA (1), volume 6346 of Lecture Notes in Computer Science, pages 427\u2013438. Springer, 2010. https:\/\/doi.org\/10.1007\/978-3-642-15775-2_37","DOI":"10.1007\/978-3-642-15775-2_37"},{"key":"1321_CR4","doi-asserted-by":"publisher","unstructured":"Belazzougui Djamal, Botelho Fabiano\u00a0C., Dietzfelbinger Martin.: Hash, displace, and compress. In ESA, volume 5757 of Lecture Notes in Computer Science, pages 682\u2013693. Springer, 2009. https:\/\/doi.org\/10.1007\/978-3-642-04128-0_61","DOI":"10.1007\/978-3-642-04128-0_61"},{"key":"1321_CR5","doi-asserted-by":"publisher","unstructured":"Belazzougui Djamal, Navarro Gonzalo.: Alphabet-independent compressed text indexing. ACM Trans. Algorithms, 10(4):23:1\u201323:19, 2014.https:\/\/doi.org\/10.1145\/2635816","DOI":"10.1145\/2635816"},{"key":"1321_CR6","doi-asserted-by":"publisher","DOI":"10.1145\/3596453","author":"Piotr Beling","year":"2023","unstructured":"Beling, Piotr: Fingerprinting-based minimal perfect hashing revisited. ACM Journal of Experimental Algorithmics (2023). https:\/\/doi.org\/10.1145\/3596453","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"1321_CR7","doi-asserted-by":"publisher","unstructured":"Bender Michael\u00a0A., Farach-Colton Martin, Goswami Mayank, Johnson Rob, McCauley Samuel, Singh Shikha.: Bloom filters, adaptivity, and the dictionary problem. In FOCS, pages 182\u2013193. IEEE Computer Society, (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00026","DOI":"10.1109\/FOCS.2018.00026"},{"key":"1321_CR8","unstructured":"Bernstein Sergei.: On a modification of chebyshev\u2019s inequality and of the error formula of laplace. Ann. Sci. Inst. Sav. Ukraine, Sect. Math, 1(4):38\u201349, (1924)"},{"key":"1321_CR9","doi-asserted-by":"publisher","unstructured":"Bez Dominik, Kurpicz Florian, Lehmann Hans-Peter, Sanders Peter.: High performance construction of RecSplit based minimal perfect hash functions. In ESA, volume 274 of LIPIcs, pages 19:1\u201319:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2023. https:\/\/doi.org\/10.4230\/LIPICS.ESA.2023.19","DOI":"10.4230\/LIPICS.ESA.2023.19"},{"key":"1321_CR10","doi-asserted-by":"publisher","unstructured":"Botelho Fabiano\u00a0C., Pagh Rasmus, Ziviani Nivio.: Perfect hashing for data management applications. CoRR, abs\/cs\/0702159, 2007. https:\/\/doi.org\/10.48550\/ARXIV.CS\/0702159","DOI":"10.48550\/ARXIV.CS\/0702159"},{"issue":"1","key":"1321_CR11","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/J.IS.2012.06.002","volume":"38","author":"Fabiano C Botelho","year":"2013","unstructured":"Botelho, Fabiano C., Pagh, Rasmus, Ziviani, Nivio: Practical perfect hashing in nearly optimal space. Inf. Syst. 38(1), 108\u2013131 (2013). https:\/\/doi.org\/10.1016\/J.IS.2012.06.002","journal-title":"Inf. Syst."},{"key":"1321_CR12","first-page":"376","volume":"23","author":"Arthur Cayley","year":"1878","unstructured":"Cayley, Arthur: A theorem on trees. Quart. J. Math. 23, 376\u2013378 (1878)","journal-title":"Quart. J. Math."},{"key":"1321_CR13","doi-asserted-by":"publisher","unstructured":"Chapman Jarrod\u00a0A., Ho Isaac, Sunkara Sirisha, Luo Shujun, Schroth Gary\u00a0P., Rokhsar Daniel\u00a0S.: Meraculous: De novo genome assembly with short paired-end reads. PLOS ONE, 6(8):1\u201313, 08 (2011). https:\/\/doi.org\/10.1371\/journal.pone.0023501","DOI":"10.1371\/journal.pone.0023501"},{"key":"1321_CR14","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1186\/1471-2105-14-67","volume":"14","author":"Yupeng Chen","year":"2013","unstructured":"Chen, Yupeng, Schmidt, Bertil, Maskell, Douglas L.: A hybrid short read mapping accelerator. BMC Bioinform. 14, 67 (2013). https:\/\/doi.org\/10.1186\/1471-2105-14-67","journal-title":"BMC Bioinform."},{"issue":"12","key":"1321_CR15","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1093\/BIOINFORMATICS\/BTW279","volume":"32","author":"Rayan Chikhi","year":"2016","unstructured":"Chikhi, Rayan, Limasset, Antoine, Medvedev, Paul: Compacting de bruijn graphs from sequencing data quickly and in low memory. Bioinform. 32(12), 201\u2013208 (2016). https:\/\/doi.org\/10.1093\/BIOINFORMATICS\/BTW279","journal-title":"Bioinform."},{"key":"1321_CR16","doi-asserted-by":"publisher","unstructured":"Dietzfelbinger Martin, Heide Friedhelm\u00a0Meyer auf\u00a0der.: A new universal class of hash functions and dynamic hashing in real time. In ICALP, volume 443 of Lecture Notes in Computer Science, pages 6\u201319. Springer, (1990). https:\/\/doi.org\/10.1007\/BFB0032018","DOI":"10.1007\/BFB0032018"},{"key":"1321_CR17","doi-asserted-by":"publisher","unstructured":"Dietzfelbinger Martin, Rink Michael. Applications of a splitting trick. In Automata, Languages and Programming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I 36, pages 354\u2013365. Springer, (2009). https:\/\/doi.org\/10.1007\/978-3-642-02927-1_30","DOI":"10.1007\/978-3-642-02927-1_30"},{"key":"1321_CR18","doi-asserted-by":"publisher","unstructured":"Dietzfelbinger Martin, Weidling Christoph.: Balanced allocation and dictionaries with tightly packed constant size bins. In ICALP, volume 3580 of Lecture Notes in Computer Science, pages 166\u2013178. Springer, (2005). https:\/\/doi.org\/10.1007\/11523468_14","DOI":"10.1007\/11523468_14"},{"key":"1321_CR19","doi-asserted-by":"publisher","unstructured":"Dillinger Peter\u00a0C., H\u00fcbschle-Schneider Lorenz , Sanders Peter, Walzer Stefan. Fast succinct retrieval and approximate membership using ribbon. In SEA, volume 233 of LIPIcs, pages 4:1\u20134:20. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 2022. https:\/\/doi.org\/10.4230\/LIPICS.SEA.2022.4","DOI":"10.4230\/LIPICS.SEA.2022.4"},{"issue":"2","key":"1321_CR20","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"Peter Elias","year":"1974","unstructured":"Elias, Peter: Efficient storage and retrieval by content and address of static files. J. ACM 21(2), 246\u2013260 (1974). https:\/\/doi.org\/10.1145\/321812.321820","journal-title":"J. ACM"},{"key":"1321_CR21","doi-asserted-by":"publisher","unstructured":"Esposito Emmanuel, Graf Thomas\u00a0Mueller, Vigna Sebastiano. RecSplit: Minimal perfect hashing via recursive splitting. In ALENEX, pages 175\u2013185. SIAM, (2020). https:\/\/doi.org\/10.1137\/1.9781611976007.14","DOI":"10.1137\/1.9781611976007.14"},{"key":"1321_CR22","doi-asserted-by":"publisher","unstructured":"Fan Bin, Andersen David\u00a0G., Kaminsky Michael, Mitzenmacher Michael.: Cuckoo filter: Practically better than bloom. In CoNEXT, pages 75\u201388. ACM, (2014). https:\/\/doi.org\/10.1145\/2674005.2674994","DOI":"10.1145\/2674005.2674994"},{"key":"1321_CR23","unstructured":"Fano Robert\u00a0Mario.: On the number of bits required to implement an associative memory. Technical report, MIT, Computer Structures Group, (1971). Project MAC, Memorandum 61\""},{"issue":"2","key":"1321_CR24","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/S00224-004-1195-X","volume":"38","author":"Dimitris Fotakis","year":"2005","unstructured":"Fotakis, Dimitris, Pagh, Rasmus, Sanders, Peter, Spirakis, Paul G.: Space efficient hash tables with worst case constant access time. Theory Comput. Syst. 38(2), 229\u2013248 (2005). https:\/\/doi.org\/10.1007\/S00224-004-1195-X","journal-title":"Theory Comput. Syst."},{"issue":"6","key":"1321_CR25","doi-asserted-by":"publisher","first-page":"870","DOI":"10.1017\/S0963548315000334","volume":"25","author":"Nikolaos Fountoulakis","year":"2016","unstructured":"Fountoulakis, Nikolaos, Khosla, Megha, Panagiotou, Konstantinos: The multiple-orientability thresholds for random hypergraphs. Combinatorics, Probability & Computing 25(6), 870\u2013908 (2016). https:\/\/doi.org\/10.1017\/S0963548315000334","journal-title":"Combinatorics, Probability & Computing"},{"issue":"3","key":"1321_CR26","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1002\/RSA.20426","volume":"41","author":"Nikolaos Fountoulakis","year":"2012","unstructured":"Fountoulakis, Nikolaos, Panagiotou, Konstantinos: Sharp load thresholds for cuckoo hashing. Random Struct. Algorithms 41(3), 306\u2013333 (2012). https:\/\/doi.org\/10.1002\/RSA.20426","journal-title":"Random Struct. Algorithms"},{"key":"1321_CR27","doi-asserted-by":"publisher","unstructured":"Fox Edward\u00a0A., Chen Qi\u00a0Fan, Heath Lenwood\u00a0S.: A faster algorithm for constructing minimal perfect hash functions. In SIGIR, pages 266\u2013273. ACM, (1992). https:\/\/doi.org\/10.1145\/133160.133209","DOI":"10.1145\/133160.133209"},{"issue":"3","key":"1321_CR28","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"Michael L Fredman","year":"1984","unstructured":"Fredman, Michael L., Koml\u00f3s, J\u00e1nos., Szemer\u00e9di, Endre: Storing a sparse table with 0(1) worst case access time. J. ACM 31(3), 538\u2013544 (1984). https:\/\/doi.org\/10.1145\/828.1884","journal-title":"J. ACM"},{"key":"1321_CR29","doi-asserted-by":"crossref","unstructured":"Frieze Alan, Karo\u0144ski Micha\u0142.: Introduction to random graphs. Cambridge University Press, (2016)","DOI":"10.1017\/CBO9781316339831"},{"key":"1321_CR30","doi-asserted-by":"publisher","unstructured":"Golomb Solomon\u00a0W.: Run-length encodings (corresp.). IEEE Trans. Inf. Theory, 12(3):399\u2013401, (1966). https:\/\/doi.org\/10.1109\/TIT.1966.1053907","DOI":"10.1109\/TIT.1966.1053907"},{"issue":"1","key":"1321_CR31","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1145\/42267.42274","volume":"35","author":"Gaston H Gonnet","year":"1988","unstructured":"Gonnet, Gaston H., Larson, Per-\u00c5ke: External hashing with limited internal storage. J. ACM 35(1), 161\u2013184 (1988). https:\/\/doi.org\/10.1145\/42267.42274","journal-title":"J. ACM"},{"key":"1321_CR32","doi-asserted-by":"publisher","unstructured":"Hagerup Torben, Tholey Torsten.: Efficient minimal perfect hashing in nearly minimal space. In STACS, volume 2010 of Lecture Notes in Computer Science, pages 317\u2013326. Springer, (2001). https:\/\/doi.org\/10.1007\/3-540-44693-1_28","DOI":"10.1007\/3-540-44693-1_28"},{"issue":"1\u20132","key":"1321_CR33","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1002\/rsa.20147","volume":"30","author":"Svante Janson","year":"2007","unstructured":"Janson, Svante, Luczak, Malwina J.: A simple solution to the $$k$$-core problem. Random Struct. Algorithms 30(1\u20132), 50\u201362 (2007). https:\/\/doi.org\/10.1002\/rsa.20147","journal-title":"Random Struct. Algorithms"},{"key":"1321_CR34","doi-asserted-by":"crossref","unstructured":"Johan Ludwig William Valdemar Jensen: Sur les fonctions convexes et les in\u00e9galit\u00e9s entre les valeurs moyennes. Acta mathematica 30(1), 175\u2013193 (1906)","DOI":"10.1007\/BF02418571"},{"issue":"1","key":"1321_CR35","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1214\/aos\/1176346079","volume":"11","author":"Kumar Joag-Dev","year":"1983","unstructured":"Joag-Dev, Kumar, Proschan, Frank: Negative association of random variables with applications. The Annals of Statistics 11(1), 286\u2013295 (1983). https:\/\/doi.org\/10.1214\/aos\/1176346079","journal-title":"The Annals of Statistics"},{"key":"1321_CR36","doi-asserted-by":"publisher","unstructured":"Kurpicz Florian, Lehmann Hans-Peter, Sanders Peter.: PaCHash: Packed and compressed hash tables. In 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pages 162\u2013175. SIAM, (2023). https:\/\/doi.org\/10.1137\/1.9781611977561.ch14","DOI":"10.1137\/1.9781611977561.ch14"},{"key":"1321_CR37","doi-asserted-by":"publisher","unstructured":"Larson Per-\u00c5ke, Ramakrishna M.\u00a0V.: External perfect hashing. In SIGMOD Conference, pages 190\u2013200. ACM Press, (1985). https:\/\/doi.org\/10.1145\/318898.318916","DOI":"10.1145\/318898.318916"},{"key":"1321_CR38","doi-asserted-by":"publisher","unstructured":"Lehmann Hans-Peter, Sanders Peter, Walzer Stefan.: Bipartite ShockHash: Pruning ShockHash search for efficient perfect hashing. CoRR, abs\/2310.14959v1, (2023). https:\/\/doi.org\/10.48550\/ARXIV.2310.14959v1","DOI":"10.48550\/ARXIV.2310.14959v1"},{"key":"1321_CR39","doi-asserted-by":"publisher","unstructured":"Lehmann Hans-Peter, Sanders Peter, Walzer Stefan.: SicHash \u2013 small irregular cuckoo tables for perfect hashing. In ALENEX, pages 176\u2013189. SIAM, (2023). https:\/\/doi.org\/10.1137\/1.9781611977561.CH15","DOI":"10.1137\/1.9781611977561.CH15"},{"key":"1321_CR40","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977929.15","author":"Hans-Peter Lehmann","year":"2024","unstructured":"Lehmann, Hans-Peter., Sanders, Peter, Walzer, Stefan: Shockhash: Towards optimal-space minimal perfect hashing beyond brute-force. In ALENEX. SIAM (2024). https:\/\/doi.org\/10.1137\/1.9781611977929.15","journal-title":"In ALENEX. SIAM"},{"key":"1321_CR41","doi-asserted-by":"publisher","unstructured":"Lelarge Marc.: A new approach to the orientation of random hypergraphs. In Proc. 23rd SODA, pages 251\u2013264, 2012. https:\/\/doi.org\/10.1137\/1.9781611973099.23","DOI":"10.1137\/1.9781611973099.23"},{"key":"1321_CR42","doi-asserted-by":"publisher","unstructured":"Antoine Limasset, Guillaume Rizk, Rayan Chikhi, and Pierre Peterlongo. Fast and scalable minimal perfect hashing for massive key sets. In SEA, volume\u00a075 of LIPIcs, pages 25:1\u201325:16. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 2017. https:\/\/doi.org\/10.4230\/LIPICS.SEA.2017.25","DOI":"10.4230\/LIPICS.SEA.2017.25"},{"key":"1321_CR43","unstructured":"MPHF Experiments \u2013 GitHub. https:\/\/github.com\/ByteHamster\/MPHF-Experiments, 2023"},{"issue":"1","key":"1321_CR44","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1002\/rsa.20061","volume":"27","author":"Michael Molloy","year":"2005","unstructured":"Molloy, Michael: Cores in random hypergraphs and boolean formulas. Random Struct. Algorithms 27(1), 124\u2013135 (2005). https:\/\/doi.org\/10.1002\/rsa.20061","journal-title":"Random Struct. Algorithms"},{"key":"1321_CR45","doi-asserted-by":"publisher","unstructured":"M\u00fcller Ingo, Sanders Peter, Schulze Robert, Zhou Wei.: Retrieval and perfect hashing using fingerprinting. In SEA, volume 8504 of Lecture Notes in Computer Science, pages 138\u2013149. Springer, (2014). https:\/\/doi.org\/10.1007\/978-3-319-07959-2_12","DOI":"10.1007\/978-3-319-07959-2_12"},{"key":"1321_CR46","unstructured":"Newman Mark E.\u00a0J.: Networks: An Introduction. Oxford University Press, (2010)"},{"issue":"1","key":"1321_CR47","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1137\/060658400","volume":"38","author":"Anna Pagh","year":"2008","unstructured":"Pagh, Anna, Pagh, Rasmus: Uniform hashing in constant time and optimal space. SIAM J. Comput. 38(1), 85\u201396 (2008). https:\/\/doi.org\/10.1137\/060658400","journal-title":"SIAM J. Comput."},{"key":"1321_CR48","doi-asserted-by":"publisher","unstructured":"Pagh Anna, Pagh Rasmus, Ruzic Milan.: Linear probing with constant independence. In STOC, pages 318\u2013327. ACM, (2007). https:\/\/doi.org\/10.1145\/1250790.1250839","DOI":"10.1145\/1250790.1250839"},{"key":"1321_CR49","doi-asserted-by":"publisher","unstructured":"Rasmus Pagh and Flemming Friche Rodler: Cuckoo hashing. J. Algorithms 51(2), 122\u2013144 (2004). https:\/\/doi.org\/10.1016\/j.jalgor.2003.12.002","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"1321_CR50","doi-asserted-by":"publisher","unstructured":"Pibiri Giulio\u00a0Ermanno, Trani Roberto.: PTHash: Revisiting FCH minimal perfect hashing. In SIGIR, pages 1339\u20131348. ACM, (2021). https:\/\/doi.org\/10.1145\/3404835.3462849","DOI":"10.1145\/3404835.3462849"},{"key":"1321_CR51","volume-title":"Some practical universal noiseless coding techniques","author":"Robert F Rice","year":"1979","unstructured":"Rice, Robert F.: Some practical universal noiseless coding techniques. JPL Publication, Jet Propulsion Laboratory (1979)"},{"key":"1321_CR52","doi-asserted-by":"crossref","unstructured":"St\u00e9phane Boucheron G\u00e1bor LugosiPascal Massart.:Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press (2013). https:\/\/doi.org\/10.1093\/ACPROF:OSO\/9780199535255.001.0001","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"1321_CR53","unstructured":"ShockHash \u2013 GitHub. https:\/\/github.com\/ByteHamster\/ShockHash, 2023"},{"key":"1321_CR54","doi-asserted-by":"crossref","unstructured":"Stanley Richard\u00a0P.: Enumerative combinatorics volume 1 second edition. Cambridge studies in advanced mathematics, (2011)","DOI":"10.1017\/CBO9781139058520"},{"key":"1321_CR55","unstructured":"Stefan Hermann and Sebastian Kirmayer and Hans-Peter Lehmann and Peter Sanders and Stefan Walzer.: Engineering Minimal k-Perfect Hash Functions, CoRR. abs\/2504.20001. (2025). https:\/\/doi.org\/10.48550\/ARXIV.2504.20001"},{"key":"1321_CR56","unstructured":"Szudzik Matthew.: An elegant pairing function. In Wolfram Research (ed.) Special NKS 2006 Wolfram Science Conference, pages 1\u201312, (2006)"},{"key":"1321_CR57","doi-asserted-by":"publisher","unstructured":"Walzer Stefan.: Peeling close to the orientability threshold \u2013 spatial coupling in hashing-based data structures. In SODA, pages 2194\u20132211. SIAM, (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.131","DOI":"10.1137\/1.9781611976465.131"},{"key":"1321_CR58","doi-asserted-by":"publisher","unstructured":"Walzer Stefan.: The probability to hit every bin with a linear number of balls, (2024). https:\/\/doi.org\/10.48550\/ARXIV.2403.00736","DOI":"10.48550\/ARXIV.2403.00736"},{"key":"1321_CR59","unstructured":"Witten Ian\u00a0H., Moffat Alistair, Bell Timothy\u00a0C.: Managing Gigabytes: Compressing and Indexing Documents and Images, Second Edition. Morgan Kaufmann, (1999)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01321-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01321-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01321-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T20:13:49Z","timestamp":1758399229000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01321-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,2]]},"references-count":59,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["1321"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01321-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,8,2]]},"assertion":[{"value":"21 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"We have no conflicts of interest to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}]}}