> 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;

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbM_g-PyVsjVoVS-nSY%2Fimage.png?alt=media\&token=768f5234-705a-4c96-b39d-d4cd841a6d98)

* Set = map, interchangeably&#x20;

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbM_rGqNaGczlBgPO87%2Fimage.png?alt=media\&token=b93b4a9d-f1cd-4447-887f-4346c88f783a)

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

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbMaY_dabK9safJeWiN%2Fimage.png?alt=media\&token=159f73c5-5b1b-4283-a0b1-e87cf640055e)

* No linked list anymore&#x20;

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbMaq2CboafS5jnNbvU%2Fimage.png?alt=media\&token=98586562-cb24-413a-bc05-7c940e3cb2eb)

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbMatFuQKJ2kAfP-XRX%2Fimage.png?alt=media\&token=5c1161a9-c73a-4b3f-90c2-c547f8536bf3)

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

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbMbVB_BaU7KqU4v8F2%2Fimage.png?alt=media\&token=e258818c-a2b9-4007-a6bc-d313a794ccc4)

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

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbMboDIvMuCTYJ4CrL5%2Fimage.png?alt=media\&token=b8253813-0073-45e9-91c7-ea35f6b813f5)

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbMbwAgeDLuohe2pk2p%2Fimage.png?alt=media\&token=24d8e480-d340-4a74-a7f6-fc7d0a621f18)

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

  * Collisions

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

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbMeHjqR8z83HPNnH39%2Fimage.png?alt=media\&token=55621600-0d00-4f96-a42f-f71fc093fd20)

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbMeqXSL95RsVrRMGgO%2Fimage.png?alt=media\&token=d56a7671-23ee-48f7-a68b-21b4c927cff3)

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbMfF7kvkk9vAZqBzs3%2Fimage.png?alt=media\&token=c8a253aa-fb6e-4fc2-ab85-6d03e0b2a4d6)

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

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbMfUYHlS5nFGWR-Tic%2Fimage.png?alt=media\&token=d4abae96-e31d-4d1c-a3bc-74b806902745)

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbMfnD1p0C1avD1LmO0%2Fimage.png?alt=media\&token=b5f4d2d1-67fc-4280-9cc7-fa0ebb394aca)

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

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbMgmC8GgEMxCXlvR3z%2Fimage.png?alt=media\&token=0bec3d8a-c570-4e45-8c15-fc830147d0f2)

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

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MbMY7VWEotwlFXi6v3V%2F-MbMjO2gjgtoKRyXf-YM%2Fimage.png?alt=media\&token=6c8ecba2-9a6a-439b-b36a-2404c795b3ff)

&#x20;