# A Resizable Concurrent Map

DevFeed: [A Resizable Concurrent Map](<https://devfeed.tech/articles/a-resizable-concurrent-map-21005.md>)

Original publisher: [Read original article](<https://preshing.com/20160222/a-resizable-concurrent-map>)

Author: Jeff Preshing

Published: 2016-02-22T13:05:00Z

Content type: tutorial

Language: en

Sources: [Jeff Preshing](<https://devfeed.tech/sources/jeff-preshing.md>)

Topics: [C++](<https://devfeed.tech/topics/c-plus-plus.md>), [Data structures](<https://devfeed.tech/topics/data-structures.md>), [Java](<https://devfeed.tech/topics/java.md>), [GitHub](<https://devfeed.tech/topics/github.md>)

Tags: [atomic](<https://devfeed.tech/tags/atomic.md>), [c-plus-plus](<https://devfeed.tech/tags/c-plus-plus.md>), [concurrent](<https://devfeed.tech/tags/concurrent.md>), [data](<https://devfeed.tech/tags/data.md>), [github](<https://devfeed.tech/tags/github.md>), [lock-free](<https://devfeed.tech/tags/lock-free.md>), [map](<https://devfeed.tech/tags/map.md>), [memory](<https://devfeed.tech/tags/memory.md>), [migration](<https://devfeed.tech/tags/migration.md>), [root](<https://devfeed.tech/tags/root.md>), [structure](<https://devfeed.tech/tags/structure.md>), [thread](<https://devfeed.tech/tags/thread.md>)

## AI overview

This article explains Junction's Linear map, a C++ concurrent hash map that supports resizing and deletion. It contrasts the Linear map with the simpler Crude map and describes how table migration enables continued concurrent operations.

## Source excerpt

In an earlier post, I showed how to implement the "world's simplest lock-free hash table" in C++. It was so simple that you couldn't even delete entries or resize the table. Well, a few years have passed since then, and I've recently written some concurrent maps without those limitations. You'll find them in my Junction project on GitHub. Junction contains several concurrent maps - even the 'world's simplest' is there, under the name ConcurrentMap_Crude. For brevity, let's call that one the Crude map. In this post, I'll explain the difference between the Crude map and Junction's Linear map. Linear is the simplest Junction map that supports both resize and delete. You can review the original post for an explanation of how the Crude map works. To recap: It's based on open addressing and linear probing. That means it's basically a big array of keys and values using a linear search. When inserting or looking up a given key, you hash the key to determine where to begin the search. Concurrent inserts and lookups are permitted. Junction's Linear map is based on the same principle, except that when the array gets too full, its entire contents are migrated to a new, larger array. When the migration completes, the old table is replaced with the old one. So, how do we achieve that while still allowing concurrent operations? The Linear map's approach is based on Cliff Click's non-blocking hash map in Java, but has a few differences. The Data Structure First, we need to modify our data structure a little bit. The original Crude map had two data members: A pointer m_cells and an integer m_sizeMask. The Linear map instead has a single data member m_root, which points to a Table structure followed by the cells themselves in a single, contiguous memory block. In the Table structure, there's a new shared counter cellsRemaining, initially set to 75% of the table size. Whenever a thread tries to insert a new key, it decrements cellsRemaining first. If it decrements cellsRemaining below