{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T16:49:57Z","timestamp":1766076597165,"version":"3.48.0"},"reference-count":143,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T00:00:00Z","timestamp":1766016000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006595","name":"Executive Unit for Financing Higher Education, Research, Development and Innovation (UEFISCDI), Romania","doi-asserted-by":"publisher","award":["39PTE\/2025"],"award-info":[{"award-number":["39PTE\/2025"]}],"id":[{"id":"10.13039\/501100006595","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Hash tables embody a paradox of deterministic structure that emerges from controlled randomness. They have evolved from simple associative arrays into algorithmic engines that operate near the physical and probabilistic limits of computation. This review unifies five decades of developments across universal and perfect hashing, collision-resolution strategies, and concurrent and hardware-aware architectures. The synthesis shows that modern hash tables act as thermodynamic regulators of entropy, able to transform stochastic mappings into predictable constant-time access. Recent advances in GPU and NUMA-aware designs, lock-free and persistent variants, and neural or quantum-assisted approaches further expand their capabilities. The analysis presents hash tables as models that evolve order within randomness and expand their relevance from classical computation to quantum and neuromorphic frontiers.<\/jats:p>","DOI":"10.3390\/a18120804","type":"journal-article","created":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T16:42:05Z","timestamp":1766076125000},"page":"804","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Hash Tables as Engines of Randomness at the Limits of Computation: A Unified Review of Algorithms"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9350-1530","authenticated-orcid":false,"given":"Paul A.","family":"Gagniuc","sequence":"first","affiliation":[{"name":"Faculty of Engineering in Foreign Languages, National University of Science and Technology Politehnica Bucharest, 060042 Bucharest, Romania"}]},{"given":"Mihai","family":"Togan","sequence":"additional","affiliation":[{"name":"Faculty of Information Systems and Cyber Security, Military Technical Academy \u201cFerdinand I\u201d, 050141 Bucharest, Romania"}]}],"member":"1968","published-online":{"date-parts":[[2025,12,18]]},"reference":[{"key":"ref_1","unstructured":"Knuth, D.E. (1973). The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley."},{"key":"ref_2","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press."},{"key":"ref_3","unstructured":"Aho, A., Lam, M., Sethi, R., and Ullman, J. (2006). Compilers: Principles, Techniques, and Tools, Pearson."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1327452.1327492","article-title":"MapReduce: Simplified data processing on large clusters","volume":"51","author":"Dean","year":"2008","journal-title":"Commun. ACM"},{"key":"ref_5","unstructured":"Merkle, R.C. (1989). A certified digital signature. Advances in Cryptology\u2014CRYPTO \u201989 Proceedings, Springer."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Mirrokni, A.V., Thorup, M., and Zadimoghaddam, M. (2018, January 7\u201310). Consistent hashing with bounded loads. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201918), New Orleans, LA, USA.","DOI":"10.1137\/1.9781611975031.39"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1145\/1773912.1773922","article-title":"Cassandra: A decentralized structured storage system","volume":"44","author":"Lakshman","year":"2010","journal-title":"ACM SIGOPS Oper. Syst. Rev."},{"key":"ref_8","unstructured":"Herlihy, M., and Shavit, N. (2012). The Art of Multiprocessor Programming, Morgan Kaufmann."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Ashkiani, M., Farach-Colton, M., and Owens, J.D. (2017, January 21\u201325). A dynamic hash table for the GPU. Proceedings of the IEEE International Parallel and Distributed Processing Symposium, Vancouver, BC, Canada.","DOI":"10.1109\/IPDPS.2018.00052"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1561\/0400000014","article-title":"Algorithms and Data Structures for External Memory","volume":"2","author":"Vitter","year":"2008","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Celis, P., Larson, P., and Munro, J.I. (1985, January 21\u201323). Robin Hood hashing. Proceedings of the IEEE Annual Symposium on Foundations of Computer Science, Portland, OR, USA.","DOI":"10.1109\/SFCS.1985.48"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Oukid, I., Lasperas, J., Nica, A., Willhalm, T., and Lehner, W. (July, January 26). FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory. Proceedings of the 2016 International Conference on Management of Data (SIGMOD \u201916), San Francisco, CA, USA.","DOI":"10.1145\/2882903.2915251"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/nmeth.1923","article-title":"Fast gapped-read alignment with Bowtie 2","volume":"9","author":"Langmead","year":"2012","journal-title":"Nat. Methods"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Ramakrishna, M.V., and Zobel, J. (1997, January 13\u201315). Performance in practice of string hashing functions. Proceedings of the ACM SIGMOD International Conference on Management of Data, Tucson, AZ, USA.","DOI":"10.1142\/9789812819536_0023"},{"key":"ref_15","first-page":"302","article-title":"Uniform Hashing in Constant Time and Optimal Space","volume":"35","author":"Pagh","year":"2006","journal-title":"SIAM J. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/978-3-540-25937-4_24","article-title":"Cryptographic hash-function basics: Definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance","volume":"Volume 3017","author":"Roy","year":"2004","journal-title":"Fast Software Encryption"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Motwani, R., and Raghavan, P. (1995). Randomized Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"ref_18","unstructured":"Mehta, D.P., and Sahni, S. (2018). Handbook of Data Structures and Applications, Chapman & Hall\/CRC."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Skiena, S.S. (2020). The Algorithm Design Manual, Springer. [3rd ed.].","DOI":"10.1007\/978-3-030-54256-6"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","article-title":"Universal classes of hash functions","volume":"18","author":"Carter","year":"1979","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_21","unstructured":"Botelho, F.C., Pagh, R., and Ziviani, N. (2007, January 15\u201317). Simple and space-efficient minimal perfect hash functions. Proceedings of the ACM WADS, Halifax, NS, Canada."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Belazzougui, M., Botelho, F.C., and Dietzfelbinger, M. (2009, January 7\u20139). Hash, displace, and compress. Proceedings of the 17th Annual European Symposium, Copenhagen, Denmark.","DOI":"10.1007\/978-3-642-04128-0_61"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Krawczyk, N., Bellare, M., and Canetti, R. (1997). HMAC: Keyed-Hashing for Message Authentication, Internet Engineering Task Force (IETF). IETF RFC 2104.","DOI":"10.17487\/rfc2104"},{"key":"ref_24","unstructured":"Dahlgaard, S., Knudsen, M.B.T., and Thorup, M. (2017, January 4\u20139). Practical hash functions for similarity estimation and dimensionality reduction. Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS\u201917), Long Beach, CA, USA."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/s13389-015-0110-5","article-title":"Faster 64-bit universal hashing using carry-less multiplications","volume":"6","author":"Lemire","year":"2016","journal-title":"J. Cryptogr. Eng."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"\u00d8stlin, A., and Pagh, R. (2002). Simulating Uniform Hashing in Constant Time and Optimal Space, University of Aarhus. BRICS Report Series, RS-02-27.","DOI":"10.7146\/brics.v9i27.21743"},{"key":"ref_27","unstructured":"Cooper, K., and Torczon, L. (2011). Engineering a Compiler, Morgan Kaufmann. [2nd ed.]."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"B\u00f6ther, M., Benson, L., Klimovic, A., and Rabl, T. (September, January 28). Analyzing Vectorized Hash Tables Across CPU Architectures. Proceedings of the VLDB 2023, Vancouver, BC, Canada.","DOI":"10.14778\/3611479.3611485"},{"key":"ref_29","unstructured":"Tucker, A.B. (2014). Computer Science Handbook, Chapman & Hall\/CRC. [3rd ed.]."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Robert, C.P., and Casella, G. (2004). Monte Carlo Statistical Methods, Springer.","DOI":"10.1007\/978-1-4757-4145-2"},{"key":"ref_31","unstructured":"Kuszmaul, W., and Xi, Z. (2024, January 8\u201312). A partial analysis of quadratic probing. Proceedings of the 2024 International Colloquium on Automata, Languages, and Programming (ICALP), Tallinn, Estonia."},{"key":"ref_32","unstructured":"Sedgewick, R., and Wayne, K. (2011). Algorithms, Addison-Wesley. [4th ed.]."},{"key":"ref_33","unstructured":"Mitzenmacher, M., and Upfal, E. (2017). Probability and Computing, Cambridge University Press."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1017\/S0963548318000408","article-title":"Analysis of Robin Hood and other hashing algorithms under the random probing model, with and without deletions","volume":"28","author":"Poblete","year":"2019","journal-title":"Comb. Probab. Comput."},{"key":"ref_35","unstructured":"Kirsch, A., and Mitzenmacher, M. (2010, January 6\u20138). The power of Robin Hood hashing revisited. Proceedings of the 18th Annual European Symposium, Liverpool, UK."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Shavit, N., and Tzafrir, M. (2008, January 18\u201321). Hopscotch hashing. Proceedings of the ACM Symposium on Principles of Distributed Computing, Toronto, ON, Canada.","DOI":"10.1007\/978-3-540-87779-0_24"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","article-title":"Cuckoo hashing","volume":"51","author":"Pagh","year":"2004","journal-title":"J. Algorithms"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s00224-004-1195-x","article-title":"Space efficient hash tables with worst case constant access time","volume":"38","author":"Fotakis","year":"2005","journal-title":"Theory Comput. Syst."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Le Scouarnec, N. (2018, January 23\u201324). Cuckoo++ Hash Tables: High-Performance Hash Tables for Networking Applications. Proceedings of the 2018 Symposium on Architectures for Networking and Communications Systems (ANCS \u201918), Ithaca, NY, USA.","DOI":"10.1145\/3230718.3232629"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1543","DOI":"10.1137\/080728743","article-title":"More robust hashing: Cuckoo hashing with a stash","volume":"39","author":"Kirsch","year":"2009","journal-title":"SIAM J. Comput."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1094","DOI":"10.1109\/71.963420","article-title":"The power of two choices in randomized load balancing","volume":"12","author":"Mitzenmacher","year":"2001","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_42","first-page":"1475","article-title":"Fast algorithms for adaptive rehashing","volume":"44","author":"Bentley","year":"2014","journal-title":"Softw. Pract. Exp."},{"key":"ref_43","unstructured":"Harris, T.L., Fraser, K., and Pratt, I.A. (2002, January 28\u201330). A Practical Multi-Word Compare-and-Swap Operation. Proceedings of the 16th International Symposium on Distributed Computing (DISC \u201902), Toulouse, France."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1145\/46157.330532","article-title":"Dynamic hashing schemes","volume":"20","author":"Enbody","year":"1988","journal-title":"ACM Comput. Surv."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Fatourou, P., Kallimanis, N.D., and Ropars, T. (2018, January 16\u201318). An efficient wait-free resizable hash table. Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Vienna, Austria.","DOI":"10.1145\/3210377.3210408"},{"key":"ref_46","unstructured":"Lamping, J., and Veach, E. (2014). A fast, minimal memory, consistent hash algorithm. arXiv."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., and Vogels, W. (2007, January 14\u201317). Dynamo: Amazon\u2019s highly available key-value store. Proceedings of the ACM Symposium on Operating Systems Principles, Stevenson, WA, USA.","DOI":"10.1145\/1294261.1294281"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Cooper, B.F., and Silberstein, A. (2010, January 10\u201311). Benchmarking cloud serving systems with YCSB. Proceedings of the ACM Symposium on Cloud Computing, Indianapolis, IN, USA.","DOI":"10.1145\/1807128.1807152"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Michael, M.M. (2002, January 11\u201313). High performance dynamic lock-free hash tables and list-based sets. Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), Winnipeg, MB, Canada.","DOI":"10.1145\/564879.564881"},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Harris, T.L. (2001, January 3\u20135). A pragmatic implementation of non-blocking linked-lists. Proceedings of the International Symposium on Distributed Computing, Lisbon, Portugal.","DOI":"10.1007\/3-540-45414-4_21"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/11561927_10","article-title":"Non-blocking hashtables with open addressing","volume":"Volume 3724","author":"Fraigniaud","year":"2005","journal-title":"Distributed Computing"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/78969.78972","article-title":"Linearizability: A correctness condition for concurrent objects","volume":"12","author":"Herlihy","year":"1990","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"ref_53","first-page":"30","article-title":"RCU usage in the Linux kernel: One decade later","volume":"15","author":"McKenney","year":"2017","journal-title":"ACM Queue"},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Sanchez, D., and Kozyrakis, C. (2010, January 4\u20138). The ZCache: Decoupling ways and associativity. Proceedings of the IEEE International Symposium on Microarchitecture, Atlanta, GA, USA.","DOI":"10.1109\/MICRO.2010.20"},{"key":"ref_55","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., and Ramachandran, S. (1999, January 17\u201319). Cache-oblivious algorithms. Proceedings of the IEEE Symposium on Foundations of Computer Science, New York, NY, USA."},{"key":"ref_56","unstructured":"Shahrokhi, H., and Shaikhha, A. (2023, January 17\u201321). An Efficient Vectorized Hash Table for Batch Computations. Proceedings of the 37th European Conference on Object-Oriented Programming (ECOOP 2023), Seattle, WA, USA."},{"key":"ref_57","unstructured":"Qureshi, M.K., Thompson, D., and Patt, Y.N. (2005, January 4\u20138). The V-Way cache: Demand-based associativity via global replacement. Proceedings of the 32nd International Symposium on Computer Architecture (ISCA\u201905), Madison, WI, USA."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1145\/2814328","article-title":"Challenges of memory management on modern NUMA systems","volume":"58","author":"Gaud","year":"2015","journal-title":"Commun. ACM"},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/978-3-540-75476-3_34","article-title":"FPGA-Based Cuckoo Hashing for Pattern Matching in NIDS\/NIPS","volume":"Volume 4773","author":"Tran","year":"2007","journal-title":"Managing Next Generation Networks and Services; Lecture Notes in Computer Science"},{"key":"ref_60","doi-asserted-by":"crossref","unstructured":"Fan, B., Andersen, D.G., Kaminsky, M., and Mitzenmacher, M.D. (2014, January 2\u20135). Cuckoo Filter: Practically Better Than Bloom. Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies (CoNEXT \u201914), Sydney, Australia.","DOI":"10.1145\/2674005.2674994"},{"key":"ref_61","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M., Johnson, R., Kuszmaul, B.C., Medjedovic, D., Montes, P., Shetty, P., Spillane, R.P., and Zadok, E. (2012, January 27\u201331). Don\u2019t thrash: How to cache your hash on flash. Proceedings of the ACM VLDB, Istanbul, Turkey.","DOI":"10.14778\/2350229.2350275"},{"key":"ref_62","first-page":"358","article-title":"Fast scalable construction of (minimal perfect) hash functions","volume":"65","author":"Genuzio","year":"2022","journal-title":"Comput. J."},{"key":"ref_63","doi-asserted-by":"crossref","unstructured":"Izraelevitz, J., Yang, J., and Swanson, S. (2016, January 2\u20136). Failure-Atomic Persistent Memory Updates via JUSTDO Logging. Proceedings of the 21st International Conference Architectural Support for Programming Languages and Operating Systems (ASPLOS \u201916), Atlanta, GA, USA.","DOI":"10.1145\/2872362.2872410"},{"key":"ref_64","doi-asserted-by":"crossref","unstructured":"Lee, S.K., Mohan, J., Kashyap, S., Kim, T., and Chidambaram, V. (2019, January 27\u201330). RECIPE: Converting Concurrent DRAM Indexes to Persistent-Memory Indexes. Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP \u201919), Huntsville, ON, Canada.","DOI":"10.1145\/3341301.3359635"},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"1226","DOI":"10.14778\/2809974.2809984","article-title":"Mega-KV: A Case for GPUs to Maximize the Throughput of In-Memory Key-Value Stores","volume":"8","author":"Zhang","year":"2015","journal-title":"Proc. VLDB Endow."},{"key":"ref_66","unstructured":"Gray, J., and Reuter, A. (1993). Transaction Processing: Concepts and Techniques, Morgan Kaufmann."},{"key":"ref_67","unstructured":"DeWitt, D.J., and Gerber, R. (1985, January 21\u201323). Multiprocessor hash-based join algorithms. Proceedings of the VLDB, Stockholm, Sweden."},{"key":"ref_68","unstructured":"Garcia-Molina, H., Ullman, J.D., and Widom, J. (2008). Database Systems: The Complete Book, Pearson."},{"key":"ref_69","unstructured":"Zhang, B., and Du, D.H. (2021, January 14\u201316). NVLSM: A Persistent Memory Key-Value Store Using Log-Structured Merge Trees. Proceedings of the 2021 USENIX Annual Technical Conference (USENIX ATC \u201921), Santa Clara, CA, USA."},{"key":"ref_70","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1145\/2934664","article-title":"Apache Spark: A unified engine for big data processing","volume":"59","author":"Zaharia","year":"2016","journal-title":"Commun. ACM"},{"key":"ref_71","doi-asserted-by":"crossref","unstructured":"Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., and Balakrishnan, H. (2001, January 27\u201331). Chord: A scalable peer-to-peer lookup service for Internet applications. Proceedings of the ACM SIGCOMM, San Diego, CA, USA.","DOI":"10.1145\/964723.383071"},{"key":"ref_72","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1145\/2656877.2656890","article-title":"P4: Programming protocol-independent packet processors","volume":"44","author":"Bosshart","year":"2014","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_73","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1145\/1355734.1355746","article-title":"OpenFlow: Enabling innovation in campus networks","volume":"38","author":"McKeown","year":"2008","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_74","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1365815.1365816","article-title":"Bigtable: A Distributed Storage System for Structured Data","volume":"26","author":"Chang","year":"2008","journal-title":"ACM Trans. Comput. Syst."},{"key":"ref_75","doi-asserted-by":"crossref","first-page":"4047","DOI":"10.1016\/j.comnet.2013.09.003","article-title":"Bloom filter applications in network security: A state-of-the-art survey","volume":"57","author":"Geravand","year":"2013","journal-title":"Comput. Netw."},{"key":"ref_76","unstructured":"Anderson, P., and Zhang, L. (2010, January 7\u201312). Fast and secure laptop backups with encrypted de-duplication. Proceedings of the USENIX Conference on Large Installation System Administration, San Jose, CA, USA."},{"key":"ref_77","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A Method for Obtaining Digital Signatures and Public-Key Cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_78","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1093\/bioinformatics\/bts635","article-title":"STAR: Ultrafast universal RNA-seq aligner","volume":"29","author":"Dobin","year":"2013","journal-title":"Bioinformatics"},{"key":"ref_79","doi-asserted-by":"crossref","first-page":"764","DOI":"10.1093\/bioinformatics\/btr011","article-title":"A fast, lock-free approach for efficient parallel counting of occurrences of k-mers","volume":"27","author":"Kingsford","year":"2011","journal-title":"Bioinformatics"},{"key":"ref_80","unstructured":"Broder, A. (1997, January 13). On the resemblance and containment of documents. Proceedings of the IEEE Compression and Complexity of SEQUENCES, Salerno, Italy."},{"key":"ref_81","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1186\/s13015-017-0097-9","article-title":"Gerbil: A fast and memory-efficient k-mer counter with GPU support","volume":"12","author":"Erbert","year":"2017","journal-title":"Algorithms Mol. Biol."},{"key":"ref_82","doi-asserted-by":"crossref","unstructured":"Indyk, P., and Motwani, R. (1998, January 23\u201326). Approximate nearest neighbors: Towards removing the curse of dimensionality. Proceedings of the ACM STOC, Dallas, TX, USA.","DOI":"10.1145\/276698.276876"},{"key":"ref_83","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1109\/TBDATA.2019.2921572","article-title":"Billion-scale similarity search with FAISS","volume":"7","author":"Johnson","year":"2021","journal-title":"IEEE Trans. Big Data"},{"key":"ref_84","unstructured":"Li, M., Zhou, L., Yang, Z., Li, A., Xia, F., Andersen, D.G., and Smola, A. (2014, January 6\u20138). Parameter server for distributed machine learning. Proceedings of the USENIX OSDI, Broomfield, CO, USA."},{"key":"ref_85","unstructured":"Kitaev, N., Kaiser, L., and Levskaya, A. (2020, January 26\u201330). Reformer: The efficient transformer. Proceedings of the ICLR, Virtual."},{"key":"ref_86","unstructured":"Mitzenmacher, M., and Vadhan, S. (2008, January 20\u201322). Why simple hash functions work: Exploiting the entropy in data. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, San Fracisco, CA, USA."},{"key":"ref_87","doi-asserted-by":"crossref","unstructured":"Zhang, G., and Sanchez, D. (2019, January 12\u201316). Leveraging Caches to Accelerate Hash Tables and Memoization. Proceedings of the MICRO \u201919: 52nd Annual IEEE\/ACM International Symposium on Microarchitecture, Columbus, OH, USA.","DOI":"10.1145\/3352460.3358272"},{"key":"ref_88","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2220357.2220361","article-title":"The Power of Simple Tabulation Hashing","volume":"59","author":"Patrascu","year":"2012","journal-title":"J. ACM"},{"key":"ref_89","doi-asserted-by":"crossref","first-page":"96","DOI":"10.14778\/2850583.2850585","article-title":"A seven-dimensional analysis of hashing methods and its implications on query processing","volume":"9","author":"Richter","year":"2015","journal-title":"Proc. VLDB Endow"},{"key":"ref_90","doi-asserted-by":"crossref","unstructured":"M\u00f6hring, R., and Raman, R. (2002). External-Memory Breadth-First Search with Sublinear I\/O. Algorithms-ESA 2002, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-45749-6"},{"key":"ref_91","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1145\/114005.102808","article-title":"Wait-free synchronization","volume":"13","author":"Herlihy","year":"1991","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"ref_92","first-page":"13","article-title":"Split-Ordered Lists: Lock-Free Extensible Hash Tables","volume":"54","author":"Shalev","year":"2006","journal-title":"J. ACM"},{"key":"ref_93","doi-asserted-by":"crossref","unstructured":"Sundell, H., and Tsigas, P. (2004, January 15\u201317). Lock-free and practical doubly linked list-based deques using single-word compare-and-swap. Proceedings of the OPODIS, Grenoble, France.","DOI":"10.1007\/11516798_18"},{"key":"ref_94","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1109\/TPDS.2004.8","article-title":"Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects","volume":"15","author":"Michael","year":"2004","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_95","doi-asserted-by":"crossref","unstructured":"Basu, A., Kirman, N., Kirman, M., Chaudhuri, M., and Martinez, J. (2007, January 1\u20135). Scavenger: A New Last Level Cache Architecture with Global Block Priority. Proceedings of the 40th Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO 2007), Chicago, IL, USA.","DOI":"10.1109\/MICRO.2007.4408273"},{"key":"ref_96","unstructured":"Chowdhury, R.A., and Ramachandran, V. (August, January 30). The Cache-Oblivious Gaussian Elimination Paradigm: Theoretical Framework and Parallel Implementation. Proceedings of the SPAA, Cambridge, MA, USA."},{"key":"ref_97","doi-asserted-by":"crossref","unstructured":"J\u00fcnger, A., Kobus, R., M\u00fcller, A., Hundt, C., Xu, K., Liu, W., and Schmidt, B. (2020). WarpCore: A library for fast hash tables on GPUs. arXiv.","DOI":"10.1109\/HiPC50609.2020.00015"},{"key":"ref_98","unstructured":"Tata, N.T. (2017). MicroCuckoo Hash Engine for High-Speed IP Lookup. [Master\u2019s Thesis, Department of Computer Engineering, Virginia Polytechnic Institute and State University]."},{"key":"ref_99","doi-asserted-by":"crossref","first-page":"1107","DOI":"10.1137\/070702278","article-title":"Linear Probing with Constant Independence","volume":"39","author":"Pagh","year":"2009","journal-title":"SIAM J. Comput."},{"key":"ref_100","unstructured":"Fujimoto, R.M. (2001, January 9\u201312). Parallel and distributed simulation systems. Proceedings of the 2001 Winter Simulation Conference, Arlington, VA, USA."},{"key":"ref_101","first-page":"275","article-title":"Lock-Free Bucketized Cuckoo Hashing","volume":"Volume 14100","author":"Cano","year":"2023","journal-title":"Euro-Par 2023: Parallel Processing"},{"key":"ref_102","unstructured":"Eppstein, D. (2016, January 22\u201324). Cuckoo Filter: Simplification and Analysis. Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjav\u00edk, Iceland."},{"key":"ref_103","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., and Schellbach, U. (2009, January 4\u20136). On Risks of Using Cuckoo Hashing with Simple Universal Hash Classes. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), New York, NY, USA.","DOI":"10.1137\/1.9781611973068.87"},{"key":"ref_104","unstructured":"Shor, P.W. (1994, January 20\u201322). Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings of the IEEE Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA."},{"key":"ref_105","doi-asserted-by":"crossref","unstructured":"Grover, L.K. (1996, January 22\u201324). A fast quantum mechanical algorithm for database search. Proceedings of the ACM STOC, Philadelphia, PA, USA.","DOI":"10.1145\/237814.237866"},{"key":"ref_106","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/992287.992296","article-title":"Quantum search algorithms","volume":"35","author":"Ambainis","year":"2004","journal-title":"SIGACT News"},{"key":"ref_107","doi-asserted-by":"crossref","first-page":"160501","DOI":"10.1103\/PhysRevLett.100.160501","article-title":"Quantum random access memory","volume":"100","author":"Giovannetti","year":"2008","journal-title":"Phys. Rev. Lett."},{"key":"ref_108","first-page":"143","article-title":"Fine-grained power modeling for modern processors","volume":"38","author":"Eyerman","year":"2010","journal-title":"ACM SIGARCH Comput. Archit. News"},{"key":"ref_109","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.future.2019.07.035","article-title":"Towards the design of efficient hash-based indexing scheme for growing databases on non-volatile memory","volume":"105","author":"Ma","year":"2020","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_110","doi-asserted-by":"crossref","unstructured":"Yang, Y., Wijeratne, S., Zheng, D., and Prasanna, V.K. (2020, January 22\u201325). FASTHash: FPGA-Based High Throughput Parallel Hash Table. Proceedings of the 2020 International Supercomputing Conference (ISC) Workshops, Virtual Event.","DOI":"10.1007\/978-3-030-50743-5_1"},{"key":"ref_111","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1109\/TC.2022.3158476","article-title":"Towards Thermal-Aware Workload Distribution in Cloud Data Centers Based on Failure Models","volume":"72","author":"Li","year":"2023","journal-title":"IEEE Trans. Comput."},{"key":"ref_112","doi-asserted-by":"crossref","unstructured":"Kraska, A., Beutel, A., Chi, E.H., Dean, J., and Polyzotis, N. (2018, January 10\u201315). The case for learned index structures. Proceedings of the ACM SIGMOD, Houston, TX, USA.","DOI":"10.1145\/3183713.3196909"},{"key":"ref_113","unstructured":"Licks, G.P., and Meneguzzi, F. (2020, January 26\u201330). Automated Database Indexing Using Model-Free Reinforcement Learning. Proceedings of the 2020 International Conference on Automated Planning and Scheduling (ICAPS 2020), Virtual."},{"key":"ref_114","doi-asserted-by":"crossref","unstructured":"Liong, V.E., Lu, J., Wang, G., Moulin, P., and Zhou, J. (2015, January 7\u201312). Deep hashing for compact binary codes learning. Proceedings of the IEEE Computer Vision and Pattern Recognition Conference, Boston, MA, USA.","DOI":"10.1109\/CVPR.2015.7298862"},{"key":"ref_115","doi-asserted-by":"crossref","first-page":"1705","DOI":"10.14778\/3342263.3342644","article-title":"Neo: A Learned Query Optimizer","volume":"12","author":"Marcus","year":"2019","journal-title":"Proc. VLDB Endow"},{"key":"ref_116","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-68697-5_1","article-title":"Keying Hash Functions for Message Authentication","volume":"Volume 1109","author":"Koblitz","year":"1996","journal-title":"Advances in Cryptology-CRYPTO \u201996"},{"key":"ref_117","unstructured":"Bar-Yosef, N., and Wool, A. (2007, January 28\u201331). Remote Algorithmic Complexity Attacks Against Randomized Hash Tables. Proceedings of the Second International Conference on Security and Cryptography, Barcelona, Spain."},{"key":"ref_118","doi-asserted-by":"crossref","first-page":"114762","DOI":"10.1016\/j.tcs.2024.114762","article-title":"Defending hash tables from algorithmic complexity attacks with resource burning","volume":"2014","author":"Chakraborty","year":"2024","journal-title":"Theor. Comput. Sci."},{"key":"ref_119","doi-asserted-by":"crossref","unstructured":"Karger, D., Lehman, E., Leighton, T., Levine, M., Lewin, D., and Panigrahy, R. (1997, January 4\u20136). Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC \u201997), El Paso, TX, USA.","DOI":"10.1145\/258533.258660"},{"key":"ref_120","first-page":"1572","article-title":"MIHash: Online Hashing with Mutual Information","volume":"41","author":"Cakir","year":"2017","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_121","doi-asserted-by":"crossref","first-page":"2204569","DOI":"10.1002\/adma.202204569","article-title":"Probabilistic Neural Computing with Stochastic Devices","volume":"35","author":"Misra","year":"2023","journal-title":"Adv. Mater."},{"key":"ref_122","doi-asserted-by":"crossref","unstructured":"Tapia-Fern\u00e1ndez, S., Garc\u00eda-Garc\u00eda, D., and Garc\u00eda-Hernandez, P. (2022). Key Concepts, Weakness and Benchmark on Hash Table Data Structures. Algorithms, 15.","DOI":"10.3390\/a15030100"},{"key":"ref_123","first-page":"152","article-title":"Collision Resolution Techniques in Hash Table: A Review","volume":"12","author":"Yusuf","year":"2021","journal-title":"Int. J. Adv. Comput. Sci. Appl."},{"key":"ref_124","unstructured":"Lehmann, H.P., Mueller, T., Pagh, R., Pibiri, G.E., Sanders, P., Vigna, S., and Walzer, S. (2025). Modern Minimal Perfect Hashing: A Survey. arXiv."},{"key":"ref_125","unstructured":"Misto, S. (2024). Efficiency in Hash Table Design: A Study of Collision Resolution Strategies and Performance. [Bachelor\u2019s Thesis, Malm\u00f6 University]."},{"key":"ref_126","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1080\/15427951.2004.10129096","article-title":"Network Applications of Bloom Filters: A Survey","volume":"1","author":"Broder","year":"2004","journal-title":"Internet Math."},{"key":"ref_127","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1109\/SURV.2011.031611.00024","article-title":"Theory and Practice of Bloom Filters for Distributed Systems","volume":"14","author":"Tarkoma","year":"2012","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_128","doi-asserted-by":"crossref","unstructured":"Zhao, Y., Dai, W., Wang, S., Xi, L., Wang, S., and Zhang, F. (2023). A Review of Cuckoo Filters for Privacy Protection and Their Applications. Electronics, 12.","DOI":"10.3390\/electronics12132809"},{"key":"ref_129","unstructured":"Zink, T. (2011). A Survey of Hash Tables with Summaries for IP Lookup Applications, University of Konstanz. Technical Report."},{"key":"ref_130","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1109\/TPAMI.2017.2699960","article-title":"A Survey on Learning to Hash","volume":"40","author":"Wang","year":"2018","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_131","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1109\/COMST.2005.1610546","article-title":"A Survey and Comparison of Peer-to-Peer Overlay Network Schemes","volume":"7","author":"Lua","year":"2005","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_132","first-page":"3","article-title":"A Survey on Deep Hashing Methods","volume":"14","author":"Luo","year":"2023","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"ref_133","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1109\/JPROC.2015.2487976","article-title":"Learning to Hash for Indexing Big Data-A Survey","volume":"104","author":"Wang","year":"2016","journal-title":"Proc. IEEE"},{"key":"ref_134","doi-asserted-by":"crossref","first-page":"8912","DOI":"10.1038\/s41598-025-93418-2","article-title":"Structured hashing with deep learning for modality, organ, and disease content sensitive medical image retrieval","volume":"15","author":"Manna","year":"2025","journal-title":"Sci. Rep."},{"key":"ref_135","unstructured":"Menezes, A.J., van Oorschot, P.C., and Vanstone, S.A. (1996). Handbook of Applied Cryptography, CRC Press."},{"key":"ref_136","doi-asserted-by":"crossref","unstructured":"Bellare, M., and Rogaway, P. (1993, January 3\u20135). Random Oracles Are Practical: A Paradigm for Designing Efficient Protocols. Proceedings of the ACM Conference Computer and Communications Security (CCS \u201993), Fairfax, VA, USA.","DOI":"10.1145\/168588.168596"},{"key":"ref_137","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/3507922","article-title":"Nap: Persistent Memory Indexes for NUMA Architectures","volume":"18","author":"Wang","year":"2022","journal-title":"ACM Trans. Storage"},{"key":"ref_138","doi-asserted-by":"crossref","first-page":"2865","DOI":"10.1007\/s10586-022-03766-1","article-title":"Scalable NUMA-aware persistent B+-tree for non-volatile memory devices","volume":"26","author":"Jamil","year":"2023","journal-title":"Clust. Comput."},{"key":"ref_139","doi-asserted-by":"crossref","unstructured":"Coburn, J., Caulfield, A.M., Akel, A., Grupp, L.M., Gupta, R.K., Jhala, R., and Swanson, S. (2011, January 5\u201311). NV-Heaps: Making persistent objects fast and safe with next-generation, non-volatile memories. Proceedings of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS \u201911), Newport Beach, CA, USA.","DOI":"10.1145\/1950365.1950380"},{"key":"ref_140","first-page":"2671","article-title":"Uncertainty-Aware Discrete Hashing for Low-Risk Binary Code Generation","volume":"660","author":"Chang","year":"2025","journal-title":"Inf. Sci."},{"key":"ref_141","unstructured":"Chatzigiannakis, I., and Karydis, I. (2024). Algorithmic Aspects of Distributed Hash Tables on Cloud, Fog, and Edge Computing Applications: A Survey. Algorithmic Aspects of Cloud Computing. ALGOCLOUD 2023, Springer. Lecture Notes in Computer Science."},{"key":"ref_142","doi-asserted-by":"crossref","unstructured":"Balatsouras, C.-P., Karras, A., Karras, C., Karydis, I., and Sioutas, S. (2023). WiCHORD+: A Scalable, Sustainable, and P2P Chord-Based Ecosystem for Smart Agriculture Applications. Sensors, 23.","DOI":"10.3390\/s23239486"},{"key":"ref_143","doi-asserted-by":"crossref","unstructured":"Gagniuc, P.A. (2024). Antivirus Engines: From Methods to Innovations, Design, and Applications, Elsevier Syngress.","DOI":"10.1016\/B978-0-443-32952-4.00018-8"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/12\/804\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T16:44:54Z","timestamp":1766076294000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/12\/804"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,18]]},"references-count":143,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["a18120804"],"URL":"https:\/\/doi.org\/10.3390\/a18120804","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,18]]}}}