> For the complete documentation index, see [llms.txt](https://sliu583.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sliu583.gitbook.io/blog/specific-work/seminar-and-talk/reading-groups/db-reading-group/hash-maps-overview.md).

# Hash maps overview

Some reference materials:

* <https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/>&#x20;

![](/files/-MbM_g-PyVsjVoVS-nSY)

* Set = map, interchangeably&#x20;

![](/files/-MbM_rGqNaGczlBgPO87)

* Follow at least 2 pointers&#x20;
* Benefit: scan through all the keys by following the linked list&#x20;

![](/files/-MbMaY_dabK9safJeWiN)

* No linked list anymore&#x20;

![](/files/-MbMaq2CboafS5jnNbvU)

![](/files/-MbMatFuQKJ2kAfP-XRX)

* H1: Which bucket should you find&#x20;

![](/files/-MbMbVB_BaU7KqU4v8F2)

* Duplicates: find the next available position to put it in&#x20;
  * Scan&#x20;

![](/files/-MbMboDIvMuCTYJ4CrL5)

![](/files/-MbMbwAgeDLuohe2pk2p)

* Bad performance you can get in C++ without knowing it&#x20;

  * Collisions

\--------------------------------------------------------------------

![](/files/-MbMeHjqR8z83HPNnH39)

![](/files/-MbMeqXSL95RsVrRMGgO)

![](/files/-MbMfF7kvkk9vAZqBzs3)

* Resize only part of the original map (only submap)
  * Prevent all submaps&#x20;

![](/files/-MbMfUYHlS5nFGWR-Tic)

![](/files/-MbMfnD1p0C1avD1LmO0)

* Sub-indexing&#x20;
  * Did it in the top bits&#x20;
  * Pattern in the data itself&#x20;
* Overhead, but it is insignificant&#x20;

![](/files/-MbMgmC8GgEMxCXlvR3z)

* Lock-free concurrency control for insertion-heavy queries&#x20;
* Resize lock&#x20;
  * Enforce a resize policy&#x20;

![](/files/-MbMjO2gjgtoKRyXf-YM)

&#x20;