Performance Evaluation of Separate Chaining for Concurrent Hash Maps

• Tipo: Artigo em Revista Científica Internacional
• Data: 2025

Autores

Castro, A (Autor) Outra; Miguel Areias (Autor) FCUP; Ricardo Rocha (Autor) FCUP

Revista

Título: Mathematics

Vol. 13

Página Final: 2820

Editora: MDPI

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 19