Concurrent Hash Maps Under Pressure: Revisiting the Separate Chaining Mechanism with Linked Lists and Dynamic Arrays

Ana Castro, Miguel Areias and Ricardo Rocha

September 2025

---

Abstract

Hash maps are a widely used and efficient data structure for storing and accessing data. 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 analysis 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.

Bibtex

@InProceedings{castro-inforum25,
  author =    {A. Castro, M. Areias and R. Rocha},
  title =     {{Concurrent Hash Maps Under Pressure: Revisiting the Separate Chaining Mechanism
               with Linked Lists and Dynamic Arrays}},
  booktitle = {16th INForum - Simpósio de Informática (INForum 2025)},
  editor =    {F. Araújo and E. Ribeiro},
  month =     {September},
  year =      {2025},
  address =   {Évora, Portugal},
}

Download Paper

PDF file