{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:42:20Z","timestamp":1760060540183,"version":"build-2065373602"},"reference-count":41,"publisher":"MDPI AG","issue":"17","license":[{"start":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T00:00:00Z","timestamp":1756771200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"FCT\u2014Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia, I.P.","award":["UID\/50014\/2023"],"award-info":[{"award-number":["UID\/50014\/2023"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics"],"abstract":"<jats:p>Hash maps are a widely used and efficient data structure for storing and accessing data organized as key-value pairs. Multithreading with hash maps refers to the ability to concurrently execute multiple lookup, insert, and delete operations, such that each operation runs independently while sharing the underlying data structure. One of the main challenges in hash map implementation is the management of collisions. Arguably, separate chaining is among the most well-known strategies for collision resolution. In this paper, we present a comprehensive study comparing two common approaches to implementing separate chaining\u2014linked lists and dynamic arrays\u2014in a multithreaded environment using a lock-based concurrent hash map design. Our study includes a performance evaluation covering parameters such as cache behavior, energy consumption, contention under concurrent access, and resizing overhead. Experimental results show that dynamic arrays maintain more predictable memory access and lower energy consumption in multithreaded environments.<\/jats:p>","DOI":"10.3390\/math13172820","type":"journal-article","created":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T08:23:38Z","timestamp":1756801418000},"page":"2820","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Performance Evaluation of Separate Chaining for Concurrent Hash Maps"],"prefix":"10.3390","volume":"13","author":[{"given":"Ana","family":"Castro","sequence":"first","affiliation":[{"name":"CRACS & INESC TEC and Faculty of Sciences, University of Porto, Rua do Campo Alegre, 1021\/1055, 4169-007 Porto, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1589-3174","authenticated-orcid":false,"given":"Miguel","family":"Areias","sequence":"additional","affiliation":[{"name":"CRACS & INESC TEC and Faculty of Sciences, University of Porto, Rua do Campo Alegre, 1021\/1055, 4169-007 Porto, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4502-8835","authenticated-orcid":false,"given":"Ricardo","family":"Rocha","sequence":"additional","affiliation":[{"name":"CRACS & INESC TEC and Faculty of Sciences, University of Porto, Rua do Campo Alegre, 1021\/1055, 4169-007 Porto, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2025,9,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/356643.356645","article-title":"Hash Table Methods","volume":"7","author":"Maurer","year":"1975","journal-title":"ACM Comput. Surv."},{"key":"ref_2","unstructured":"Aho, A.V., Lam, M.S., Sethi, R., and Ullman, J.D. (2006). Compilers: Principles, Techniques, and Tools, Addison-Wesley Longman. [2nd ed.]."},{"key":"ref_3","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press."},{"key":"ref_4","unstructured":"Lehman, T.J., and Carey, M.J. (1986, January 25\u201328). A Study of Index Structures for Main Memory Database Management Systems. Proceedings of the International Conference on Very Large Data Bases, Kyoto, Japan."},{"key":"ref_5","unstructured":"Tenenbaum, A.M., Langsam, Y., and Augenstein, M.J. (1990). Data Structures Using C, Prentice Hall."},{"key":"ref_6","unstructured":"Knuth, D.E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley Longman. [2nd ed.]."},{"key":"ref_7","unstructured":"Herlihy, M., and Shavit, N. (2012). The Art of Multiprocessor Programming, Revised Reprint, Morgan Kaufmann."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3309206","article-title":"Concurrent Hash Tables: Fast and General(?)!","volume":"5","author":"Maier","year":"2019","journal-title":"ACM Trans. Parallel Comput."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Katsaragakis, M., Baloukas, C., Papadopoulos, L., Kantere, V., Catthoor, F., and Soudris, D. (2022, January 18\u201321). Energy Consumption Evaluation of Optane DC Persistent Memory for Indexing Data Structures. Proceedings of the IEEE International Conference on High Performance Computing, Data, and Analytics, Bengaluru, India.","DOI":"10.1109\/HiPC56025.2022.00022"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"David, H., Gorbatov, E., Hanebutte, U.R., Khanna, R., and Le, C. (2010, January 18\u201320). RAPL: Memory power estimation and capping. Proceedings of the 16th ACM\/IEEE International Symposium on Low Power Electronics and Design, Austin, TX, USA.","DOI":"10.1145\/1840845.1840883"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3177754","article-title":"RAPL in Action: Experiences in Using RAPL for Power Measurements","volume":"3","author":"Khan","year":"2018","journal-title":"ACM Trans. Model. Perform. Eval. Comput. Syst."},{"key":"ref_12","unstructured":"(2025, June 01). perf: Linux Profiling with Performance Counters. Available online: https:\/\/perf.wiki.kernel.org."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Pereira, R., Couto, M., Cunha, J., Melfe, G., Saraiva, J., and Fernandes, J.P. (2023). Paint Your Programs Green: On the Energy Efficiency of Data Structures. Composability, Comprehensibility and Correctness of Working Software, Springer.","DOI":"10.1007\/978-3-031-42833-3_2"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Michanan, J., Dewri, R., and Rutherford, M.J. (2015, January 14\u201316). Predicting data structures for energy efficient computing. Proceedings of the International Green and Sustainable Computing Conference, Las Vegas, NV, USA.","DOI":"10.1109\/IGCC.2015.7393698"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3511094","article-title":"Energy Efficient Computing Systems: Architectures, Abstractions and Modeling to Techniques and Standards","volume":"54","author":"Muralidhar","year":"2022","journal-title":"ACM Comput. Surv."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Lynch, J., Mirano, G.J., and Tyagi, N. (2016, January 14\u201317). Energy-Efficient Algorithms. Proceedings of the ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA.","DOI":"10.1145\/2840728.2840756"},{"key":"ref_17","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 Symposium on Parallelism in Algorithms and Architectures, Vienna, Austria.","DOI":"10.1145\/3210377.3210408"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"3274","DOI":"10.1109\/TPDS.2022.3151499","article-title":"DHash: Dynamic Hash Tables With Non-Blocking Regular Operations","volume":"33","author":"Wang","year":"2022","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Prokopec, A., Bronson, N.G., Bagwell, P., and Odersky, M. (2012, January 25\u201329). Concurrent Tries with Efficient Non-Blocking Snapshots. Proceedings of the ACM Symposium on Principles and Practice of Parallel Programming, New Orleans, LA, USA.","DOI":"10.1145\/2145816.2145836"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1145\/1147954.1147958","article-title":"Split-Ordered Lists: Lock-Free Extensible Hash Tables","volume":"53","author":"Shalev","year":"2006","journal-title":"J. ACM"},{"key":"ref_21","unstructured":"Malakhov, A. (2015). Per-bucket concurrent rehashing algorithms. arXiv."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Scouarnec, N.L. (2018, January 23\u201324). Cuckoo++ hash tables: High-performance hash tables for networking applications. Proceedings of the Symposium on Architectures for Networking and Communications Systems, Ithaca, NY, USA.","DOI":"10.1145\/3230718.3232629"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/s13222-019-00329-4","article-title":"Lock-free Data Structures for Data Stream Processing","volume":"19","author":"Baumstark","year":"2019","journal-title":"Datenbank-Spektrum"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Barnat, J., Ro\u010dkai, P., \u0160till, V., and Weiser, J. (2015). Fast, Dynamically-Sized Concurrent Hash Table. Model Checking Software, Springer.","DOI":"10.1007\/978-3-319-23404-5_5"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/PL00009236","article-title":"On the analysis of linear probing hashing","volume":"22","author":"Flajolet","year":"1998","journal-title":"Algorithmica"},{"key":"ref_26","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_27","doi-asserted-by":"crossref","unstructured":"Celis, P., Larson, P.A., and Munro, J.I. (1985, January 21\u201323). Robin hood hashing. Proceedings of the Annual Symposium on Foundations of Computer Science, Portland, OR, USA.","DOI":"10.1109\/SFCS.1985.48"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Askitis, N., and Zobel, J. (2005, January 2\u20134). Cache-Conscious collision resolution in string hash tables. Proceedings of the International Conference on String Processing and Information Retrieval, Buenos Aires, Argentina.","DOI":"10.1007\/11575832_11"},{"key":"ref_29","unstructured":"Askitis, N., and Sinha, R. (February, January 30). HAT-trie: A cache-conscious trie-based data structure for strings. Proceedings of the Australasian Conference on Computer Science\u2014Volume 62, Ballarat, VIC, Australia."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Farach-Colton, M., Krapivin, A., and Kuszmaul, W. (2024, January 27\u201330). Optimal Bounds for Open Addressing Without Reordering. Proceedings of the Symposium on Foundations of Computer Science, Chicago, IL, USA.","DOI":"10.1109\/FOCS61266.2024.00045"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"60","DOI":"10.2991\/ijndc.2015.3.1.7","article-title":"Comparison of Hash Table Performance with Open Addressing and Closed Addressing: An Empirical Study","volume":"3","author":"Xu","year":"2015","journal-title":"Int. J. Networked Distrib. Comput."},{"key":"ref_32","unstructured":"Triplett, J., McKenney, P.E., and Walpole, J. (2011, January 15\u201317). Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming. Proceedings of the USENIX Annual Technical Conference, Portland, OR, USA."},{"key":"ref_33","unstructured":"Evans, J. (2006, January 12\u201313). A scalable concurrent malloc (3) implementation for FreeBSD. Proceedings of the BSDCan Conference, Ottawa, ON, Canada."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jpdc.2021.04.007","article-title":"On the implementation of memory reclamation methods in a lock-free hash trie design","volume":"155","author":"Moreno","year":"2021","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Moreno, P., Areias, M., and Rocha, R. (2019, January 15\u201318). Memory Reclamation Methods for Lock-Free Hash Tries. Proceedings of the International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD 2019), Campo Grande, Brazil.","DOI":"10.1109\/SBAC-PAD.2019.00039"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Moreno, P., Areias, M., and Rocha, R. (2020, January 24\u201328). A Compression-Based Design for Higher Throughput in a Lock-Free Hash Map. Proceedings of the 26th International European Conference on Parallel and Distributed Computing (Euro-Par 2020), Warsaw, Poland.","DOI":"10.1007\/978-3-030-57675-2_29"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Moreno, P., Areias, M., and Rocha, R. (2024, January 26\u201330). On Exploring Safe Memory Reclamation Methods with a Simplified Lock-Free Hash Map Design. Proceedings of the Euro-Par 2024: Parallel Processing Workshops, Madrid, Spain.","DOI":"10.1007\/978-3-031-90203-1_32"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Cooper, B.F., Silberstein, A., Tam, E., Ramakrishnan, R., and Sears, R. (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_39","unstructured":"Wang, C., Hu, J., Yang, T., Liang, Y., and Yang, M. (2023, January 10\u201312). SEPH: Scalable, Efficient, and Predictable Hashing on Persistent Memory. Proceedings of the USENIX Symposium on Operating Systems Design and Implementation, Boston, MA, USA."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"785","DOI":"10.14778\/3446095.3446101","article-title":"Persistent memory hash indexes: An experimental evaluation","volume":"14","author":"Hu","year":"2021","journal-title":"VLDB Endow."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Ben-David, N., Blelloch, G.E., and Wei, Y. (2022, January 2\u20136). Lock-free locks revisited. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Seoul, Republic of Korea.","DOI":"10.1145\/3503221.3508433"}],"container-title":["Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2227-7390\/13\/17\/2820\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:37:41Z","timestamp":1760035061000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2227-7390\/13\/17\/2820"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,2]]},"references-count":41,"journal-issue":{"issue":"17","published-online":{"date-parts":[[2025,9]]}},"alternative-id":["math13172820"],"URL":"https:\/\/doi.org\/10.3390\/math13172820","relation":{},"ISSN":["2227-7390"],"issn-type":[{"type":"electronic","value":"2227-7390"}],"subject":[],"published":{"date-parts":[[2025,9,2]]}}}