Performance Evaluation of Separate Chaining for Concurrent Hash Maps

• Type: Article in International Scientific Journal
• Date: 2025

Authors

Castro, A (Author) Other; Miguel Areias (Author) FCUP; Ricardo Rocha (Author) FCUP

Journal

Title: Mathematics

Vol. 13

Final page: 2820

Publisher: MDPI

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 0 Citations

Other information

Authenticus ID: P-019-YKT

DOI: 10.3390/math13172820

Abstract (EN): 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-linked lists and dynamic arrays-in 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 19